You are given \(N\) types of blocks.
There are \(A[i]\) blocks of the type \(i\) \((0 \leq i \leq N-1)\) .
You have to make groups of size \(K\), such that no group has more than \(floor(K/2)\) blocks of the same type.
Find the maximum number of groups that you can make.
Input Format:
- The first line contains an integer \(T\), denoting the number of test cases.
-
The first line of each test case contains two space separated integers \(N\) and \(K\) which denotes the length of the array \(A\) and the size of the group.
-
The second line of each test case contains \(N\) space separated positive integers, denoting elements of array \(A\)
Output Format:
- An integer denoting the maximum number of groups that you can make satisfying the given condition.
Constraints:
- \(1 \leq T \leq10\)
- \(1 \leq N \leq 10^5 \)
- \(2 \leq K \leq N\)
- \(1 \leq A[i] \leq 10^6 \)
- The sum of \(N\) over all test cases does not exceed \(3*10^5\)
2 2 2 3 3 5 7 6 10 12 7 4
3 5
In the first test case:-
There are 2 types of blocks and the size of group that you have to make is also 2;
so each group can have maximum \(\lfloor \frac{K}{2} \rfloor\) = 2/2=1 block of each type.
As we have 3 blocks of each type say type 1 and type 2.
we can make maximum 3 groups.
Here is an example of how you can create the three groups:-
group 1 - 1 block of type 1 and 1 block of type 2.
group 2 - 1 block of type 1 and 1 block of type 2.
group 3 - 1 block of type 1 and 1 block of type 2.
In the second test case:-
The size of the group is 7 and we cannot take more than floor(7/2)=3 blocks of the same type in a group.
so we can form maximum 5 groups satisfying the constraints.
One way to make the 5 groups is as follows:-
1112223 , 1112223, 2223334, 2333444, 3334445
Here i represents the block of type i ( for example 1 represents block of type 1).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor