TASK: HEAVY BAGS (NATIONAL INFORMATICS COMPETITION, 7TH GRADE) - SOLUTION
Two little travellers have four heavy bags in total. Each traveller can carry at most two bags, one in each hand.
All bags are shared and any traveller can carry any bag. If the bags are too heavy for them,
our travellers want to use as little help from others as possible.
The weight of every bag is known, as well as the largest load each traveller can carry.
Find the smallest total weight of the bags they cannot carry.
Input
The first line of standard input contains four natural numbers separated by single spaces, the weights of the bags.
The second line contains two natural numbers separated by one space, the weights the little travellers can carry.
All numbers are less than 1000.
Output
Print one unsigned integer to standard output, the smallest total weight of the bags for which the travellers need help.
Example 1
Input
1 2 3 4
5 6
Output
0
Explanation
One traveller can carry the bags of weights 1 and 4, and the other the bags of weights 2 and 3, so they do not need help.
Example 2
Input
2 3 4 5
5 6
Output
3
Explanation
One traveller can carry the bag of weight 5, and the other the bags of weights 2 and 4, so they need help with the bag of weight 3.
Example 3
Input
12 20 15 17
17 14
Output
35
99 56 34 22
3 4
211
Example 4
7 5 4 2
7 9
Output 2
Example 5
1 1 1 1
1 1
Output 2
Example 6
99 99 99 99
1 1
Output 396
Example 7
99 45 44 99
144 99
Output 44
Example 8
6 7 8 9
5 10
Output 21
Example 9
11 11 11 11
44 44
Output 0
Example 10
11 11 11 11
10 44
Output 22
The complete solution is shown below:
#include <iostream>
#include <algorithm>
#include <stdint.h>
using namespace std;
/* global array that stores the number of bags taken by the travellers, initially set to zeros */
int number_of_bags[2] = {0};
/* Recursive function that finds the smallest remaining weight that the travellers could not carry
* parameters:
* rest - the weight of the bags that remained up to that moment
*/
uint64_t find_smaller(uint64_t &rest, int i, uint64_t &first, uint64_t &second, uint64_t arr[], bool swapped)
{
/* If the depth of the recursive call has passed the last level, the recursion goes back and returns the remaining weight at the end of the recursion */
if (i >= 4)
{
return rest;
}
cout << "Calling find_smaller with i=" << i << ", rest=" << rest << ", first=" << first << ", second=" << second << endl;
uint64_t a1 = first; // 5,1,3,1 by recursion depth for example 1
uint64_t b1 = second; // 6,6,1,1
uint64_t a2 = second; // 6,6,1,1
uint64_t b2 = first; // 5,1,3,1
uint64_t rest1 = rest;
uint64_t rest2 = rest;
bool took1 = false;
int ind1 = swapped ? 1 : 0;
// cout << "First: i=" << i << ", number of bags: " << number_of_bags[ind1] << endl;
if (a1 >= arr[i] && number_of_bags[ind1] < 2) // considers that b will give a smaller rest until the end
{
a1 = a1 - arr[i]; /* If the first traveller, who can still carry a1 (5 kg at level i=0 in the first option), took the next bag from the array, arr[i], we reduce the weight that this same traveller can carry later. For example 1: 1=5-4, 1=3-2, 0=1-1 and 6 */
rest1 = rest1 - arr[i]; // Recomputes the total remaining weight of the bags. 6=10-4
number_of_bags[ind1]++;
// cout << "first: bag taken by traveller " << a1 << ", i=" << i << ", number of bags: " << number_of_bags[ind1] << endl;
took1 = true;
}
/* cout << "Considering first at i=" << i << ", rest1=" << rest1 << ", a=" << a1 << " for a bag of weight " << arr[i] << " and number of bags " << number_of_bags[ind1] << endl; */
rest1 = find_smaller(rest1, i + 1, a1, b1, arr, swapped);
if (took1)
{
number_of_bags[ind1]--;
// cout << "Since the first one took (" << a1 << "), reducing the number of bags to " << number_of_bags[ind1] << endl;
}
/** End of considering the first traveller in the i-th iteration **/
// cout << "End of considering the first one in iteration " << i << ", where rest1= " << rest1 << endl;
bool took2 = false;
int ind2 = swapped ? 0 : 1;
// cout << "Second: i=" << i << ", number of bags for weight " << a2 << " is " << number_of_bags[ind2] << endl;
if (a2 >= arr[i] && number_of_bags[ind2] < 2) // considers that b will give a smaller rest until the end
{
a2 = a2 - arr[i]; /* If the traveller who can still carry a2 (6 kg at level i=0 in the first option) took the next bag from the array, arr[i], we reduce the weight that this same traveller can carry later. For example 1: 2=6-4 */
rest2 = rest2 - arr[i]; // Recomputes the total remaining weight of the bags. 6=10-4
number_of_bags[ind2]++;
// cout << "second: bag taken by traveller: " << a2 << ", i=" << i << ", number of bags: " << number_of_bags[ind2] << endl;
took2 = true; // The bag was taken
}
// cout << "Considering second at i=" << i << ", rest2=" << rest2 << ", b=" << b2 << " for a bag of weight " << arr[i] << endl;
swapped = !swapped; // changes the logical value for the new call of the recursive function
rest2 = find_smaller(rest2, i + 1, a2, b2, arr, swapped); // New call of the recursive function
if (took2)
{
number_of_bags[ind2]--;
// cout << "Since the second one took (" << a2 << "), reducing the number of bags to " << number_of_bags[ind2] << endl;
}
/* End of considering the second traveller in the i-th iteration */
// cout << "End of considering the second one in iteration " << i << ", where rest2= " << rest2 << endl;
uint64_t x = min(rest1, rest2);
// cout << "Returning " << x << " for i=" << i << endl;
return x;
}
int main()
{
uint64_t arr[4], x, y; /* Array of bag weights, x - weight the first traveller can carry, y - weight the second traveller can carry */
uint64_t rest = 0;
/* Reading the bag weights and storing them in the array */
for (uint8_t i = 0; i < 4; i++)
{
cin >> arr[i];
rest += arr[i]; /* Computes the total remaining weight at the start */
}
cin >> x >> y;
uint64_t min = x, max = y;
if (x > y)
{
min = y;
max = x;
}
sort(arr, arr + 4, greater<int>()); /* Sorts the bag weights in descending order */
/* for(int i=0;i<4;i++){
cout<<arr[i]<<endl;
} */
rest = find_smaller(rest, 0, max, min, arr, false);
cout << rest << endl;
return 0;
}
The comments that are commented out (
// cout ...) refer to the code for debugging. With the debug line
cout << "Calling find_smaller ..." active, if we test e.g. example 1 (input 1 2 3 4 and 5 6), we run the application and get the following output:
Calling find_smaller with i=0, rest=10, first=6, second=5
Calling find_smaller with i=1, rest=6, first=2, second=5
Calling find_smaller with i=2, rest=6, first=2, second=5
Calling find_smaller with i=3, rest=4, first=0, second=5
Calling find_smaller with i=3, rest=4, first=3, second=2
Calling find_smaller with i=2, rest=3, first=2, second=2
Calling find_smaller with i=3, rest=1, first=0, second=2
Calling find_smaller with i=3, rest=1, first=0, second=2
Calling find_smaller with i=1, rest=6, first=1, second=6
Calling find_smaller with i=2, rest=6, first=1, second=6
Calling find_smaller with i=3, rest=6, first=1, second=6
Calling find_smaller with i=3, rest=4, first=4, second=1
Calling find_smaller with i=2, rest=3, first=3, second=1
Calling find_smaller with i=3, rest=1, first=1, second=1
Calling find_smaller with i=3, rest=3, first=1, second=3
0
Output 1: Task Heavy bags - output for example 1
Here you can follow the recursion as it goes through several calls deeper down to level 4 and back through the recursion. The value i=0 means that this is the starting level of the recursion. From there we have two branches, because there are two options that compute rest 1 and rest 2, and the smaller of these two values is returned from that level. You can further follow the recursion at higher levels, e.g. for i=1, i=2 and i=3. For i=4, the process of returning the rest back through the levels begins.Through the levels you should also follow how many bags have been picked up by both travellers up to that level, and if that value reaches 2, that traveller cannot take any more bags. If you uncomment the other debug lines (for example the ones that print "first: bag taken by traveller", "Returning ..." and the number of bags), you can see these values in the rest of the execution.
When passing the number of bags through the levels of the recursion and reading these values for the first and the second traveller, you must take into account from which option, the first or the second, the recursive function was called, because this determines whether the number of bags carried by e.g. the first traveller should be read from position 0 or from position 1 of the array number_of_bags[], since during the recursion the order changes between the traveller considered as traveller 1 (a1 and a2) and the traveller considered as traveller 2 (b1 or b2). For this purpose the logical variable "swapped" was introduced.
Figure 1: Task Heavy bags - output for example 1 - part 1
Figure 2: Task Heavy bags - output for example 1 - part 2
Figure 3: Task Heavy bags - output for example 1 - part 3
