BUYINT - Buying Integers
Let's assume that you have n integers, A1, A2, A3 ... An.
Let's define:
- E = Number of pairs (i, j) such that i < j and (Ai + Aj) are even.
- O = Number of pairs (i, j) such that i < j and (Ai + Aj) are odd.
- D = | E-O | (That means, D = (E-O) if (E-O) ≥ 0, -(E-O) otherwise.)
Unfortunately, you do have n but those n integers are lost. You will have to buy them again. Before going to the market, you have decided that you will buy n integers in such a way that the value of D will be as small as possible, as you will have to pay D golden coins to buy them.
Now, you are wondering, what that minimum D will be. (Let's call it Dmin).
Input
First line of the input file will contain the number of test cases, T ≤ 1000000, followed by T lines, each containing an integer n (1 ≤ n ≤ 109).
Output
For each case, print the case number starting from 1 and Dmin for the value of n in that particular case. See the sample output for exact formatting.
Example
Input: 3 3 4 5 Output: Case 1: 1 Case 2: 0 Case 3: 2
Warning: Input file is huge, please use faster input and output methods (e.g. printf and scanf in C++).
Problem Setter: Momontho Mashak Monmoy
Special Thanks: Muhammad Ridowan
hide comments
slothsphereoj:
2024-02-28 07:21:22
Beautiful problem, but, please just output a newline for every case, for example printf("Case %d: %lld\n",ti+1,res). Costed me 2 wrong answers just because I skipped a newline "\n" character at the end of my presentations. |
|
Shashank Tiwari:
2015-12-12 22:54:46
@Bhavik , Numbers can be same or even 0 or negative. But they will be integers always. |
|
Labib666:
2014-01-02 17:54:35
Is exact formatting as the sample output maintained for judge results?
|
|
Bhavik:
2014-01-02 08:24:36
can numbers be same?? i mean can we choose numbers 1,1,2,2 or they need to be different? Last edit: 2014-07-08 16:55:51 |
|
shiv prasad chabarval:
2014-01-02 08:24:36
@ahmad faiyaz :: if we took all d numbers in descending order then always D=0 :D |
Added by: | Faiyaz |
Date: | 2013-12-24 |
Time limit: | 1.277s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |