Розбір
Автор задачі: | Роман Білий |
Задачу підготував: | Роман Білий |
Розбір написав: | Роман Білий |
Назвемо однією операцією сумарний хід Аліси та Боба. Якщо вони вибирають всі 4 купки різні, то вони фактично вибирають 4 числа та змінюють їх на . А якщо купки збігаються, то нехай Аліса вибрала , то щоб Боб міг взяти одну з купок, яку взяла Аліса, потрібно, щоб було . В результаті вийде, що з утворились купки .
Тобто є 2 можливі операції:
.
Тепер ми хочемо зробити якнайбільше операцій цих 2 типів і якщо в кінці залишаться хоча б 2 ненульові купки, то Аліса зможе зробити ще 1 свій хід.
Блок 1
У блоці 1 можна зробити повний перебір всіх можливих операцій. Щоб зменшити кількість станів, будемо тримати масив розмірів купок посортованим.
Блок 2
Розіб'ємо всі значення на пари. Нехай ми робимо операції тільки першого типу. За одну операцію можна вибрати 2 пари та зменшити їх на 1. Така задача розв'язується наступним чином. Нехай — значення в парах, — кількість пар(в даному блоці . Посортуємо їх по спаданню, тобто — найбільше значення. Якщо , то ми зможемо всі пари звести до 0, крім можливо одної, яка буде рівна 1, залежно від парності. Інакше ми можемо звести всі пари до 0, а найбільшу до .
З цього також слідує, що використовувати операцію 2 типу не вигідно. Якщо є пари та і жодна з них не найбільша, то ми тільки зменшимо . Якщо пара — найбільша, то і операціями першого типу ми отримаємо найкращий результат.
Блоки 3-5
З опису операцій видно, що операції виконуються з парами. Тому якщо є непарна кількість значень , то одне з них таким ж і залишиться. Назвемо такі купки стоячими. Після цього знову розіб'ємо всі інші купки на пари. Як і в розв'язку до попереднього блоку поганий є випадок, коли . Тепер спробуємо використати стоячі купки і 2 операцію. 2 операцію вигідно використовувати тільки для найбільшої купки. Тобто якщо зараз найбільша купка рівна і є стояче значення , то перестрибнемо найбільшою купкою через це стояче значення і найбільша купка тепер буде рівна . Тобто знайдемо, яке кінцеве найменше значення зможе мати найбільша купка. Спочатку вона буде рівна . Далі будемо пробувати перестрибувати через стоячі купки. Якщо є стояча купка в межах , то через неї можна перестрибнути і зменшити на 2. Але не можна перестрибнути через стоячі купки з сусідними значеннями, тобто через та . У блоці 3 таких сусідних значень бути не могло.
Тобто розв'язок такий:
Розіб'ємо всі значення на пари.
Якщо , то у всіх парах залишиться максимум одна пара зі значеннями 1 залежно від парності.
Інакше знайдемо значення найбільшої купки, яке ми можемо отримати використовуючи тільки операції 1 типу . Посортуємо всі стоячі купки до спаданню і спробуємо перестрибувати через них. Але перестрибувати через дві стоячі купки з сусідніми значеннями не можна.
Знайдемо, чи залишились 2 непусті купки і в такому разі Аліса може зробити ще 1 хід.
Складність розв'язку .