We have two buckets A and B and some balls. Each bucket has a weight limit and each ball has a weight. Now we need to put the balls one by one into buckets, and we must make sure that the total weight of balls in a bucket does not exceed the weight limit of that bucket. We will report the the remaining capacity of two buckets after we put each ball into a bucket.
The balls can be put into the bucket according to either of the following two rules.
First fit. We first try to place the ball into A, if it does not fit then we try B. If B still does not fit then we discard the ball.
Best fit. We try to put the ball into the bucket that has the smallest remaining capacity after putting the ball. If no bucket can hold this ball then we discard the ball. Note that if both A and B has the same remaining capacity, then we put the ball into A.
Let us illustrate the task with two examples. We are given N, M, and W, where N, M are positive integers indicating the weight limits of A and B respectively, and W is a sequence of positive integer indicating the weight of balls. If N = 5, M = 5, W = {2, 4, 1, 3} and we try first fit, the program should do the following.
Iteration 1 puts the first ball of weight 2 into A because A has room for it. Now N becomes 3 and M remains to be 5.
Iteration 2 puts the second ball of weight 4 into B since only B has enough room. Now N remains to be 3 and M becomes 1.
Iteration 3 puts the third ball of weight 1 into A. Now N becomes 2 and M remains to be 1.
Iteration 4 discards the fourth ball of weight 3 since neither A nor B has room for it. N and M remain the same.
Use the same N, M and W. Let’s try best fit, the program should do the following.
Iteration 1 puts the first ball of weight 2 into A because the remaining capacity of both A and B are equal. Now N becomes 3 and M remains to be 5.
Iteration 2 puts the second ball of weight 4 into B since only B has enough room. Now N remains to be 3 and M becomes 1.
Iteration 3 puts the third ball of weight 1 into B because B has smaller remaining room. Now N remains to be 3 and M becomes 0.
Iteration 4 puts the fourth ball of weight 3 into A because only A has enough room. Now N becomes 0 and M remains to be 0.
Input Format
There are two lines in input file. The first line contains three integers N, M and an integer R indicating the rule. Use first fit when R is 0, and use best fit when R 1. The second line has the weights of the balls.
Output Format
Each line contains two numbers indicating the remaining capacity of A and B after you attempt to put a ball into a bucket.
Subtask
20 points: Weight limit of B is 0 and we will test first fit only.
40 points: We will test first fit only.
40 points: We will test best fit only.
Note that one input can test only one method. If you want to get 100 points you need to implement both methods, and determine which one to use based on the input R (the third parameter in the first line).
Write a program to put balls into two buckets.
Task Description
We have two buckets A and B and some balls. Each bucket has a weight limit and each ball has a weight. Now we need to put the balls one by one into buckets, and we must make sure that the total weight of balls in a bucket does not exceed the weight limit of that bucket. We will report the the remaining capacity of two buckets after we put each ball into a bucket.
The balls can be put into the bucket according to either of the following two rules.
First fit. We first try to place the ball into A, if it does not fit then we try B. If B still does not fit then we discard the ball. Best fit. We try to put the ball into the bucket that has the smallest remaining capacity after putting the ball. If no bucket can hold this ball then we discard the ball. Note that if both A and B has the same remaining capacity, then we put the ball into A.
Let us illustrate the task with two examples. We are given N, M, and W, where N, M are positive integers indicating the weight limits of A and B respectively, and W is a sequence of positive integer indicating the weight of balls. If N = 5, M = 5, W = {2, 4, 1, 3} and we try first fit, the program should do the following.
Use the same N, M and W. Let’s try best fit, the program should do the following.
Input Format
There are two lines in input file. The first line contains three integers N, M and an integer R indicating the rule. Use first fit when R is 0, and use best fit when R 1. The second line has the weights of the balls.
Output Format
Each line contains two numbers indicating the remaining capacity of A and B after you attempt to put a ball into a bucket.
Subtask
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2