Three Boxes solution codechef
Chef hasboxes of sizes , , and respectively. He puts the boxes in bags of size ( ). Find the minimum number of bags Chef needs so that he can put each box in a bag. A bag can contain more than one box if the sum of sizes of boxes in the bag does not exceed the size of the bag.
Three Boxes solution codechef – Input Format
- The first line contains denoting the number of test cases. Then the test cases follow.
- Each test case contains four integers , , , and on a single line denoting the sizes of the boxes and bags.
Three Boxes solution codechef – Output Format
For each test case, output on a single line the minimum number of bags Chef needs.
Three Boxes solution codechef – Constraints
Three Boxes solution codechef – Subtasks
Subtask 1 (100 points): Original constraints
Sample Input 1
3 2 3 5 10 1 2 3 5 3 3 4 4
Sample Output 1
1 2 3
Three Boxes solution codechef – Explanation
Test case: The sum of sizes of boxes is which is equal to the size of a bag. Hence Chef can put all three boxes in a single bag.
Test case: Chef can put boxes of size and in one bag and box of size in another bag.
Test case: Chef puts all the boxes in separate bags as there is no way to put more than one box in a single bag.