YAXS - Yet Another Xor Sequence
Fizz have an array A of n integers which ranges between [1, 5] inclusive. Let f(i) denote number of times i occurs in the array.
Fizz wants to maximize the value of max(f(1), f(2), f(3), f(4), f(5)). To achieve it, he can perform one operation in the array as many time as he likes.
In each step Fizz can choose two integers Ai and Aj such that:
- i != j
- 1 <= (Ai ⊕ Aj) <= 5, where ⊕ is the symbol for bitwise xor.
After choosing the integers, Fizz will remove them from the array and he will insert a new element (Ai ⊕ Aj).
Fizz is very good in cricket but not so in programming, so please help him to find the maximum possible value of max(f(1), f(2), f(3), f(4), f(5)).
Input Format
First line will contain an integer T(1 <= T <= 3000) denoting number of testcases. Each test case will contain two lines. First line will consist n (1 <= n <= 1000) and second line will consist n space separated integers between 1 to 5.
Output Format:
For each case, print the case number and the expected answer.
Sample
8 2 3 4 2 3 5 1 2 Output Case 1: 5
hide comments
zbillion_:
2020-05-29 21:57:03
Note:
|
|
vivek_dwivedi:
2018-06-18 03:46:36
easiest problem i solved on spoj ! Just kidding. ;) |
|
Shafaet:
2016-10-27 20:49:41
I have fixed the sample. the dataset is correct. |
|
:D:
2016-10-25 13:24:31
I'm pretty sure alfa_razra is correct here. I've wrote a basic brute force that verifies this:
|
|
alfa_razra1505:
2016-10-24 15:41:13
why the sample test case give answer 4 ? i can make it have answer 5 :
|
Added by: | Shafaet |
Date: | 2016-10-24 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |
Resource: | Own problem, Bangladesh National Collegiate Contest Preliminery Round |