BdOI 2013 National Problem 5
Posted: Wed Jan 15, 2014 12:09 pm
You are given a stick of length $N$. You want to break it in three pieces such that it can form a
triangle. How many distinct triangles can you make? Two triangles are equal if all the side
lengths are same when sorted in ascending order of length. So $(1, 3, 2)$ is same to $(3, 1, 2)$
because their side lengths are same if we sort them, which is $(1, 2, 3)$. But $(1, 3, 4) $is not
same with $(1, 2, 3)$. Suppose the lengths of three pieces are $ X, Y, Z (X <= Y <= Z) $ respectively.
Following constraints should be maintained:
$
1. X, Y, Z > 0. $
$2. X, Y, Z $ is an integer.
$3. X + Y >= Z$
$4. X + Y + Z = N
$
For example if $ N = 14 $, then there are $7$ triangles: $(1, 6, 7), (2, 5, 7), (2, 6, 6), (3, 4, 7), (3, 5, 6),
(4, 4, 6), (4, 5, 5)$.
INPUT
First line will give you the number of test cases,$ T (T<=100) $. Then each line will have an
integer $ N (0< N <= 300000) $
OUTPUT
For each test case, print the test case number starting from $1$ and an integer denoting the
number of distinct triangles possible.
SAMPLE INPUT
SAMPLE OUTPUT
triangle. How many distinct triangles can you make? Two triangles are equal if all the side
lengths are same when sorted in ascending order of length. So $(1, 3, 2)$ is same to $(3, 1, 2)$
because their side lengths are same if we sort them, which is $(1, 2, 3)$. But $(1, 3, 4) $is not
same with $(1, 2, 3)$. Suppose the lengths of three pieces are $ X, Y, Z (X <= Y <= Z) $ respectively.
Following constraints should be maintained:
$
1. X, Y, Z > 0. $
$2. X, Y, Z $ is an integer.
$3. X + Y >= Z$
$4. X + Y + Z = N
$
For example if $ N = 14 $, then there are $7$ triangles: $(1, 6, 7), (2, 5, 7), (2, 6, 6), (3, 4, 7), (3, 5, 6),
(4, 4, 6), (4, 5, 5)$.
INPUT
First line will give you the number of test cases,$ T (T<=100) $. Then each line will have an
integer $ N (0< N <= 300000) $
OUTPUT
For each test case, print the test case number starting from $1$ and an integer denoting the
number of distinct triangles possible.
SAMPLE INPUT