Make Max Groups

★★★★★

1.5

4 votes

Math, Algorithms, Binary Search,

Details

Problem

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:

Sample Input

2
2 2 
3 3
5 7
6 10 12 7 4

Sample Output

3
5

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

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).

Contributers: