SPCJ - Gopu and Create Collections Part Two
Little Gopu likes to play very much. As you know he only plays with numbers. So he is given n numbers. Now he tries to group the numbers into collections where each collection contains exactly two numbers. He can form the collection of two numbers a and b (a ≤ b), if and only if b is either 2 × a or 2 × a + 1.
Note that you can not use a single number in forming of more than one collections. Eg. 1, 2, 4 He can divide the numbers into a single collection only either [1, 2] or [2, 4] because each collection requires exactly two numbers, and each number has to be used only once in a group.
Given n numbers, Find out how many maximum number of collections he can form ?
Input
T: number of test cases.
For each test case, First line will contain n: (1 ≤ n ≤ 105)
Then next line will contain n numbers single space separated. Range of each number will be between 1 and 1018.
Sum of n over all the tests will be at most 106. So number of test cases are decided on this criteria.
Output
For each test case, output maximum number of collections that can be formed.
Example
Input:
4
2
1 2
3
1 2 4
4
1 2 4 8
2
4 4 Output:
1
1
2
0
hide comments
Arpit Gupta:
2016-09-15 11:44:58
@d14214 @:.Mohib.:
|
|
Anant Upadhyay:
2016-01-22 19:37:01
Nice One :) |
|
Ankit:
2015-09-22 11:40:21
nice greedy :)
|
|
:.Mohib.::
2015-06-14 12:30:55
Nice que...!!!
|
|
Archit Kapoor:
2015-01-13 12:25:10
I am getting NZEC, but I have tested my code for various test cases and it is running well. I have tested my code on Ideone also, checked for wild conditions as well. Can anyone help? |
Added by: | praveen123 |
Date: | 2013-12-23 |
Time limit: | 10s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | IITK ACA CSE online judge |