Editorial

Назвемо однією операцією сумарний хід Аліси та Боба. Якщо вони вибирають всі 4 купки різні, то вони фактично вибирають 4 числа $(x,x,y,y)$ та змінюють їх на $(x-1,x-1,y-1,y-1)$. А якщо купки збігаються, то нехай Аліса вибрала $(x,y)$, то щоб Боб міг взяти одну з купок, яку взяла Аліса, потрібно, щоб було $y=x-1$. В результаті вийде, що з $(x,x,x-1)$ утворились купки $(x-2,x-2,x-1)$.

Тобто є 2 можливі операції:

• $(x,x,y,y)\to (x,x,y,y)$

• $(x,x,x-1)\to (x-2,x-2,x-1)$

.

Тепер ми хочемо зробити якнайбільше операцій цих 2 типів і якщо в кінці залишаться хоча б 2 ненульові купки, то Аліса зможе зробити ще 1 свій хід.

Блок 1

У блоці 1 можна зробити повний перебір всіх можливих операцій. Щоб зменшити кількість станів, будемо тримати масив розмірів купок посортованим.

Блок 2

Розіб'ємо всі значення на пари. Нехай ми робимо операції тільки першого типу. За одну операцію можна вибрати 2 пари та зменшити їх на 1. Така задача розв'язується наступним чином. Нехай $b_i$ — значення в парах, $k$ — кількість пар(в даному блоці $k=n/2)$. Посортуємо їх по спаданню, тобто $b_1$ — найбільше значення. Якщо $b_1\le {\sum }_{i=2}^k{b}_i$, то ми зможемо всі пари звести до 0, крім можливо одної, яка буде рівна 1, залежно від парності. Інакше ми можемо звести всі пари до 0, а найбільшу до $b_1-{\sum }_{i=2}^k{b}_i$.

З цього також слідує, що використовувати операцію 2 типу не вигідно. Якщо є пари $x$ та $x-1$ і жодна з них не найбільша, то ми тільки зменшимо ${\sum }_{i=2}^k{b}_i$. Якщо пара $x$ — найбільша, то і операціями першого типу ми отримаємо найкращий результат.

Блоки 3-5

З опису операцій видно, що операції виконуються з парами. Тому якщо є непарна кількість значень $x$, то одне з них таким ж і залишиться. Назвемо такі купки стоячими. Після цього знову розіб'ємо всі інші купки на пари. Як і в розв'язку до попереднього блоку поганий є випадок, коли $b_1>{\sum }_{i=2}^k{b}_i$. Тепер спробуємо використати стоячі купки і 2 операцію. 2 операцію вигідно використовувати тільки для найбільшої купки. Тобто якщо зараз найбільша купка рівна $x$ і є стояче значення $x-1$, то перестрибнемо найбільшою купкою через це стояче значення і найбільша купка тепер буде рівна $x-2$. Тобто знайдемо, яке кінцеве найменше значення зможе мати найбільша купка. Спочатку вона буде рівна $r=b_1-{\sum }_{i=2}^k{b}_i$. Далі будемо пробувати перестрибувати через стоячі купки. Якщо є стояча купка в межах $[r-1,b_1-1]$, то через неї можна перестрибнути і зменшити $r$ на 2. Але не можна перестрибнути через стоячі купки з сусідними значеннями, тобто через $y$ та $y-1$. У блоці 3 таких сусідних значень бути не могло.

Тобто розв'язок такий:

• Розіб'ємо всі значення на пари.

• Якщо $b_1\le {\sum }_{i=2}^k{b}_i$, то у всіх парах залишиться максимум одна пара зі значеннями 1 залежно від парності.

• Інакше знайдемо значення найбільшої купки, яке ми можемо отримати використовуючи тільки операції 1 типу $r=b_1-{\sum }_{i=2}^k{b}_i$. Посортуємо всі стоячі купки до спаданню і спробуємо перестрибувати через них. Але перестрибувати через дві стоячі купки з сусідніми значеннями не можна.

• Знайдемо, чи залишились 2 непусті купки і в такому разі Аліса може зробити ще 1 хід.

Складність розв'язку $O(n\log (n))$.