ADABLOOM - Ada and Bloom
As you might already know, Ada the Ladybug is a farmer. She grows many beautiful flowers. Each of the flowers has something called "blooming value". As long as Ai < Ai ⊕ Aj < Aj (where ⊕ stands for binary XOR, and A stands for "blooming value") is true for any pair of flowers (in any order), then those flowers-pair might bloom into a wonderful blossom, if they are replanted into same box (at most 2 flowers can be put into one box).
Ada wants to maximize the number of blossoms - can you find it?
Input
The first line of input contains 1 ≤ T ≤ 500 test-cases.
The first line of each test-case contains N 1 ≤ N ≤ 5000
The next line contains N integers 0 < Ai ≤ 1018, the blooming value of flower.
NOTE: The number of test-cases varies depending on size of array (the longest array won't be a single file more than once).
Output
For each test-cases, print the maximal number of blossoms Ada can achieve.
Example Input 1
6 7 8 5 4 8 4 9 11 6 9 9 12 12 4 6 3 7 7 4 4 10 6 9 1 8 11 4 12 3 1 2 1 10 4 12 2 5 2
Example Output 1
0 2 0 1 4 1
All possible pairs 1
Test-case 1: Test-case 2: 4 < 8 < 12 4 < 8 < 12 6 < 10 < 12 6 < 10 < 12 Test-case 3: Test-case 4: 1 < 8 < 9 Test-case 5: 1 < 2 < 3 1 < 10 < 11 1 < 2 < 3 1 < 10 < 11 2 < 8 < 10 2 < 9 < 11 3 < 9 < 10 3 < 8 < 11 4 < 8 < 12 Test-case 6: 5 < 9 < 12
Example Input 2
1 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Example Output 3
7
hide comments
div_12345:
2020-05-25 14:22:32
plz post the solution .
|
|
wisfaq:
2017-08-26 22:06:50
Thanks, Miloslav. Last edit: 2017-08-26 22:14:18 |
|
morass:
2017-08-25 23:23:26
@wisfaq: Try to submit again (in pypy - it is faster) ... I've increased Time-Limit drasticali so it shall pass now (I guess). Your algo shall be right, yet python seems to be very slow :'( |
|
morass:
2017-08-25 01:07:09
@wisfaq: One integer only - thank you - I'll update |
|
wisfaq:
2017-08-24 13:56:58
The first line of each test-case contains two integers N 1 ≤ N ≤ 5000?? |
Added by: | Morass |
Date: | 2017-08-24 |
Time limit: | 7s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |