BdOI 2013 National Problem 5

Discuss everything related to IOI here. For more general or advanced topics use CS forum.

Moderators: bristy1588, Labib

User avatar
bristy1588
Posts: 92
Joined: Sun Jun 19, 2011 10:31 am

BdOI 2013 National Problem 5

Unread post by bristy1588 » 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

Code: Select all

3
3
6
14
SAMPLE OUTPUT

Code: Select all

Case 1: 1
Case 2: 2
Case 3: 7
Bristy Sikder

Post Reply