[Solved] Three Boxes codechef solution

October Challenge 2021 Division 3 (Rated) - CodeChef

Three Boxes codechef solution

Chef has 33 boxes of sizes AABB, and CC respectively. He puts the boxes in bags of size DD (ABCDA≤B≤C≤D). 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 codechef solution

Input Format

  • The first line contains TT denoting the number of test cases. Then the test cases follow.
  • Each test case contains four integers AABBCC, and DD on a single line denoting the sizes of the boxes and bags.

Three Boxes codechef solution

Output Format

For each test case, output on a single line the minimum number of bags Chef needs.

Three Boxes codechef solution

Constraints

  • 1T1001≤T≤100
  • 1ABCD1001≤A≤B≤C≤D≤100

Three Boxes codechef solution

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 codechef solution

Explanation

Test case 11: The sum of sizes of boxes is 2+3+5=102+3+5=10 which is equal to the size of a bag. Hence Chef can put all three boxes in a single bag.

Test case 22: Chef can put boxes of size 11 and 33 in one bag and box of size 22 in another bag.

Test case 33: Chef puts all the boxes in separate bags as there is no way to put more than one box in a single bag.


Updating Soon…


Three Boxes codechef solution

Counting Tuples codechef solution

 

Leave a Comment