Вода (Розбір)

Якщо обсяг деякої каністри більше $k$, то всю воду забрати додому неможливо, виводимо "Impossible".

Відсортуємо каністри за зростанням обсягу. Спробуємо віднести найбільшу каністру разом з найменшою. Якщо це неможливо, то найбільшу каністру слід нести додому одну. Якщо можливо, то видаляємо з розгляду найбільшу і найменшу каністру, після чого вирішуємо задачу для решти каністр аналогічно.

Приклад

Розглянемо приклад з умови задачі. Обсяги наявних каністр: 1, 2, 3, 3. За один раз Сергій може нести не більше k = 4 літрів води. Сума обсягів найменшої і найбільшої каністри дорівнює 1 + 3 = 4, що не більше $k$. Отже, в перший раз Сергій перенесе ці дві каністри.

Залишилися каністри $2$ і $3$. Сума обсягів найменшої і найбільшої каністри дорівнює 2 + 3 = 5, що більше $k$. Отже, вдруге найбільшу каністру слід нести додому одну.

Втретє Сергій забере додому останню каністру обсягом $2$ літра.

Реалізація алгоритму

Обсяги каністр зберігаємо в масиві $m$.

vector<int> m;

Читаємо вхідні дані.

v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Сортуємо обсяги каністр.

sort(v.begin(), v.end());

Кількість ходок за водою підраховуємо у змінній $res$.

res = 0;

Встановимо два вказівники: $а$ на початок масиву, $b$ — на кінець.

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

Якщо найбільша каністра більше $k$, то забрати всю воду неможливо.

if (v[b] > k)
{
  printf("Impossible\n"); return 0;
}

Переносимо воду.

while (a <= b)
{

Якщо сума найменшої і найбільшої каністри більше $k$, то за один раз можна забрати тільки найбільшу каністру.

  if (v[a] + v[b] > k) b--;

Інакше несемо дві каністри: найменшу і найбільшу.

  else { a++; b--; }

Плюс одна ходка за водою.

  res++;
}

Виводимо відповідь.

printf("%d\n", res);

Python реалізація

import sys

Читаємо вхідні дані.

n, k = map(int, input().split())
v = list(map(int, input().split()))

Сортуємо обсяги каністр.

v.sort()

Кількість ходок за водою підраховуємо у змінній $res$.

res = 0

Встановимо два вказівники: $а$ на початок масиву, $b$ — на кінець.

a = 0
b = len(v) – 1

Якщо найбільша каністра більше $k$, то забрати всю воду неможливо.

if v[b] > k:
  print("Impossible")
  sys.exit(0)

Переносимо воду.

while a <= b:

Якщо сума найменшої і найбільшої каністри більше $k$, то за один раз можна забрати тільки найбільшу каністру.

  if v[a] + v[b] > k:
    b -= 1
  else:

Інакше несемо дві каністри: найменшу і найбільшу.

    a += 1
    b -= 1

Плюс одна ходка за водою.

  res += 1

Виводимо відповідь.

print(res)