Аналіз алгоритму

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

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

Приклад

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

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

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

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

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

vector<int> m;

// Читаємо вхідні дані.
m.resize(n);
for (i = 0; i < n; i++)
    scanf("%d", &m[i]);

// Сортуємо об'єми каністр.
sort(m.begin(), m.end());

// Кількість ходок за водою підраховуємо в змінній `res`.
res = 0;

// Встановимо два вказівники: `a` на початок масиву, `b` – на кінець.
a = 0; b = m.size() - 1;

// Якщо найбільша каністра більше `k`, то занести всю воду неможливо.
if (m[b] > k) {
    printf("Impossible\n"); 
    return 0;
}

// Переносимо воду.
while (a <= b) {
    // Якщо сума найменшої та найбільшої каністри більше `k`, то за один раз можна занести тільки найбільшу каністру.
    if (m[a] + m[b] > k) b--;
    // Інакше несемо дві каністри: найменшу та найбільшу.
    else { a++; b--; }
    res++;
}

// Виводимо відповідь.
printf("%d\n", res);