Автор: Тимур Дегтярі
Роздробник: Тимур Дегтярі
Розбір підготовано: Тимур Дегтярі, Костянтин Денисов
Ми стверджуємо, що відповідь . Дійсно, розглянемо наступний жадібний підхід:
проходимо через сім'ї, призначаємо поточну сім'ю команді найменшого розміру. Розглянемо, як змінюються найменший і найбільший розміри команди:
нехай буде мінімумом, а — максимумом. Припустимо, що y-x \le 3. Тоді після призначення поточної сім'ї найменшій команді новий мінімум становить принаймні , а новий максимум — \max(x+3, y) \le x+3. Отже, ця властивість зберігається протягом усього процесу призначення.
Отже, відповідь завжди одна з 0, 1, 2, 3.
Нехай — це кількість сімей з пінгвінами, — з пінгвінами, а — з пінгвіном. Нехай S = 3 \cdot x + 2 \cdot y + z.
Ствердження: якщо (x\ \%\ k) > 0 і (x\ \%\ k) + y + z < k, відповідь дорівнює .
Нехай t = \lfloor \frac{x}{3} \rfloor. Спочатку зауважимо, що в оптимальному призначенні принаймні одна команда матиме пінгвінів. Оскільки (x\ \%\ k) + y + z < k, за принципом Діріхле принаймні одна команда міститиме лише сім'ї з пінгвінами. Якщо ця команда має розмір 3t+3, тоді, щоб відповідь не була , всі інші команди повинні мати розміри \ge 3t+1, тому кожна з них повинна містити або принаймні одну сім'ю розміру , або , або принаймні t+1 сімей розміру , отже, (x\ \%\ k) + y + z \ge k-1. Водночас команда, яку ми розглядаємо, також має t+1 сімей з , отже, (x\ \%\ k) + y + z \ge k, що є суперечністю.
Якщо ця команда має розмір не більше 3t-3, тоді за принципом Діріхле найбільша команда має розмір принаймні \frac{S}{k} > 3t, що дає відповідь , суперечність. Отже, завжди є принаймні одна команда з розміром .
Більше того, це єдиний випадок, коли відповідь дорівнює . Припустимо, що (x\ \%\ k) + y + z \geq k. Спочатку рівномірно розподіліть сім'ї з між командами, так що команд мають 3t+3 пінгвінів, а решта команди мають пінгвінів. Тепер розподіліть достатньо сімей з і пінгвінами, щоб усі команди мали розміри між 3t+1 і 3t+3. Оскільки залишилися лише сім'ї з і , а різниця в розмірах становить не більше , ми можемо зберігати її не більше , жадібно додаючи нову сім'ю до найменшої команди, отже, оптимальна відповідь не перевищує .
Крім того, якщо (x\ \%\ k) + y + z < k, але (x\ \%\ k) = 0, очевидно, що відповідь дорівнює , якщо y > 0; , якщо y=0, z>0, і , якщо y=z=0.
Отже, тепер нам потрібно лише розрізнити, чи відповідь дорівнює або .
Цілі для відповідей 0 і 1.
Перевірка ans=0. Якщо S\bmod k\ne 0, тоді ans=0 неможливо. В іншому випадку всі команд повинні мати однаковий розмір T=S/k.
Перевірка ans=1. Нехай L=\lfloor S/k\rfloor, U=L+1, а x=S-kL. Тоді точно команд повинні мати розмір , а решта k-x команд повинні мати розмір .
В обох випадках ми запускаємо ту ж процедуру перевірки TryBuild, яка намагається побудувати команди з необхідними цільовими розмірами, використовуючи доступні сім'ї.
Жадібна процедура перевірки TryBuild.
Нам дано мультимножину цільових розмірів команд (або всі , або k-x копій і копій ). Ми також підтримуємо залишкові кількості (c_1,c_2,c_3) і намагаємося побудувати кожну команду незалежно.
Перший прохід (жадібний на основі шаблону). Для кожного цільового розміру (обробляємо цілі в невисхідному порядку) ми намагаємося заповнити одну команду з загальною сумою точно за наступними пріоритетами:
Якщо непарне, розмістіть одну сім'ю розміру , якщо це можливо; в іншому випадку розмістіть одну сім'ю розміру . Зменшіть на або відповідно. Якщо жоден з них недоступний, цей прохід зазнає невдачі.
Поки це можливо, розміщуйте пари (віднімемо від ), поки t\ge 6.
Потім, поки це можливо, розміщуйте пари (віднімемо ), але лише після завершення етапу .
Потім розмістіть якомога більше сімей з (віднімемо щоразу).
Нарешті, розмістіть пари (віднімемо ).
Якщо нам вдасться зменшити кожну цільову до , перший прохід успішний; в іншому випадку він зазнає невдачі.
Другий прохід (найбільша сім'я в найменшу команду). Якщо перший прохід зазнає невдачі, ми починаємо з початкових кількостей і запускаємо ще один жадібний:
Зберігайте команд з їхніми поточними сумами (спочатку всі ) у структурі, яка може повертати команду з найменшою сумою.
Постійно беріть найбільшу залишкову сім'ю (надаючи перевагу розміру , потім , потім ) і додавайте її до найменшої команди.
Після того, як усі сім'ї призначені, ми сортуємо отримані суми команд і порівнюємо їх з необхідною цільовою мультимножиною. Якщо вони збігаються, другий прохід успішний.
Складність.
Підрахунок c_1,c_2,c_3 — це . Другий жадібний прохід можна реалізувати за допомогою пріоритетної черги над командами і виконується за O(n\log k). Загальна складність на тестовий випадок становить O(n\log k).