Chopsticks
View as PDFThere are ~n~ bamboo sticks with lengths ~a_1, a_2, \ldots, a_n~ as positive integers. You are allowed to perform the following operation zero or multiple times:
- Choose any stick, break it into two smaller sticks with positive integer lengths, such that the two new sticks have unequal lengths.
After performing the operation, you use the sticks to form pairs of chopsticks. A pair of chopsticks is formed from two sticks with equal lengths. Find the maximum number of pairs of chopsticks that can be formed after performing the operation.
Input
The input consists of multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \le t \le 10\,000~) which is the number of test cases. The description of each test case is as follows.
The first line contains an integer ~n~ (~1 \le n \le 2 \cdot 10^5~) — the number of bamboo sticks.
The second line contains ~n~ integers ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~) — the lengths of the bamboo sticks.
The sum of ~n~ in all test cases is guaranteed not to exceed ~2 \cdot 10^5~.
Output
For each test case, output a single integer denoting the maximum number of pairs of chopsticks that can be formed.
Scoring
| Subtask | Score | Constraints |
|---|---|---|
| 1 | ~250~ | ~a_i \le 3~ |
| 2 | ~250~ | No additional constraints |
| Total | ~500~ |
Sample Input 1
2
7
1 1 1 2 2 2 2
4
2 3 3 2
Sample Output 1
3
3
Sample Input 2
2
1
4
10
3 1 4 1 5 9 2 6 5 3
Sample Output 2
1
15
Notes
In the first test case in the first example, we have ~3~ bamboo sticks of length ~1~, and ~4~ bamboo sticks of length ~2~. We cannot break any stick into two smaller sticks with different lengths. From these sticks, we can create ~1~ pair of chopsticks from two sticks of length ~1~, and add ~2~ more pairs from the sticks of length ~2~. Thus, the maximum number of pairs of chopsticks that can be formed is ~1 + 2 = 3~.
Note that there is one stick of length ~1~ left unused.
In the second test case in the first example, we can break the stick of length ~3~ into two smaller sticks of length ~1~ and ~2~. Thus, we will have ~1~ pair of chopsticks from the stick of length ~1~, and ~2~ pairs from the stick of length ~2~. Therefore, we still obtain ~1 + 2 = 3~ pairs of chopsticks.
In the first test case in the second example, we have only one bamboo stick of length ~4~. Initially, we can break this stick into sticks of length ~1~ and ~3~. Then we can break the stick of length ~3~ into sticks of length ~1~ and ~2~. From here, we can create a pair of chopsticks from two sticks of length ~1~.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.