Editorial
If the volume of some canister is more than , then it is impossible to take all the water home, print "Impossible".
Sort the canisters in ascending order of volume. Let’s try to carry the largest canister together with the smallest one. If this is not possible, then the largest canister should be carried home alone. If it is possible, then remove the largest and the smallest canisters from consideration and solve the problem for the remaining canisters in the same way.
Example
Consider an example from the problem statement. The volumes of available cans are: . Sergey can carry no more than liters of water at a time. The sum of the volumes of the smallest and the largest canisters is , which is no more than . Therefore, for the first time Sergey will transfer these two cans.
Canisters and remain. The sum of the volumes of the smallest and the largest canisters is , which is more than . Therefore, for the second time, the largest canister should be carried home alone.
For the third time, Sergey will take home the last canister with a volume of liters.
Algorithm realization
Store the volumes of canisters in the array .
vector<int> m;
Read the input data.
v.resize(n); for (i = 0; i < n; i++) scanf("%d", &v[i]);
Sort the volumes of the cans.
sort(v.begin(), v.end());
Count the number of trips for water in the variable .
res = 0;
Set two pointers: at the beginning of the array, at the end.
a = 0; b = v.size() - 1;
If the largest canister is greater than , then it is impossible to take all the water.
if (v[b] > k) { printf("Impossible\n"); return 0; }
Transfer the water.
while (a <= b) {
If the sum of the smallest and largest canisters is greater than , then only the largest canister can be carried at once.
if (v[a] + v[b] > k) b--;
Otherwise, carry two canisters: the smallest and the largest.
else { a++; b--; }
Plus one trip for water.
res++; }
Print the answer.
printf("%d\n", res);
Python realization
import sys
Read the input data.
n, k = map(int, input().split()) v = list(map(int, input().split()))
Sort the volumes of the cans.
v.sort()
Count the number of trips for water in the variable .
res = 0
Set two pointers: at the beginning of the array, at the end.
a = 0 b = len(v) – 1
If the largest canister is greater than , then it is impossible to take all the water.
if v[b] > k: print("Impossible") sys.exit(0)
Transfer the water.
while a <= b:
If the sum of the smallest and largest canisters is greater than , then only the largest canister can be carried at once.
if v[a] + v[b] > k: b -= 1 else:
Otherwise, carry two canisters: the smallest and the largest.
a += 1 b -= 1
Plus one trip for water.
res += 1
Print the answer.
print(res)