609. Water

Recently Sergey went to the well for water but did not return. He took n cans with him, each of which he filled completely with water. Now Sergey wants to deliver them to his country house. This is where the problem lies. At one time Sergey can carry no more than 2 cans because he has only two hands. Moreover, he can carry no more than k liters of water.

Now Sergey stands at the well and thinks about the minimum number of times he can take all the water home, and whether he can do it at all. Help him solve this problem.

Input. The first line contains two integers n and k (1 ≤ n ≤ 10⁵). The second line contains n integers – the volumes of canisters in liters. All input numbers are positive and do not exceed 10⁹.

Output. If Sergey cannot take all the water home, print “Impossible”. Otherwise, print one number – the minimum required number of trips.

Sample input	Sample output
4 4 1 2 3 3	3

SOLUTION

greedy

Algorithm analysis

If the volume of some canister is more than k, 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: 1, 2, 3, 3. Sergey can carry no more than k = 4 liters of water at a time. The sum of the volumes of the smallest and the largest canisters is 1 + 3 = 4, which is no more than k. Therefore, for the first time Sergey will transfer these two cans.

Canisters 2 and 3 remain. The sum of the volumes of the smallest and the largest canisters is 2 + 3 = 5, which is more than k. 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 2 liters.

Algorithm implementation

Store the volumes of canisters in the array m.

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.

res = 0;

Set two pointers: a at the beginning of the array, b at the end.

a = 0; b = v.size() - 1;

If the largest canister is greater than k, 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 k, 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 implementation

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.

res = 0

Set two pointers: a at the beginning of the array, b at the end.

a = 0

b = len(v) – 1

If the largest canister is greater than k, 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 k, 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)