Catamarans#381

Catamarans (Editorial)

Автор задачі:

Микола Арзубов

Задачу підготував:

Павло Цікалишин

Розбір написав:

Костянтин Денисов

Поділимо всі ваги на . Тоді у нас є ваги , , , , , а максимальна вага, яку витримує катамаран, — .

Для зручного зберігання кількості людей із кожною вагою можна використовувати масив .

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

  1. Для кожної людини з вагою потрібно виділити окремий катамаран. Після цього залишаються люди з вагами , , , .

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

  3. Людину з вагою можна об'єднати або з людиною вагою , або з двома людьми вагою . Вигідніше спершу об'єднувати з , оскільки з двох одиничок можна утворити , але навпаки — ні. Тому формуємо групи 3+2, а коли людей вагою не залишиться, групуємо 3+1+1 (або менше одиничок, якщо їх не вистачає). Після цього залишаються люди з вагами та .

  4. Далі компонування відбувається у такій пріоритетності:

    • 2+2+1 (оскільки дозволяє ефективно використовувати вагу);

    • 2+2 (якщо одиничок немає);

    • 2+1+1+1 (щоб заповнити катамаран повністю);

    • 2+1+1, 2+1, (у міру зменшення можливих комбінацій).

  5. Коли залишаються лише люди з вагою , їх групуємо по п'ятеро в один катамаран. Якщо кількість не ділиться на , додаємо ще один катамаран для решти.

Такий підхід гарантує мінімальну кількість катамаранів для перевезення всієї групи.

Складність алгоритму: (через зчитування).