Достатньо перевірити чи \((n - 7 \times i) \mod 4 = 0\) для \(0 \leq i \leq 3\).
B. Дорожня гра з аркушем паперу
Якщо \(n=m\) або \(n \mod 2 = 1\) і \(m \mod 2 = 1\), то гра закінчується в нічию. Адже для будь-якого ходу першого гравця другий може зробити симетричний хід, що принесе таку ж кількість балів. Можна показати, що в іншому випадку, у Зеника завжди існує виграшна стратегія. Наприклад, якщо обидва значення парні, тобто на обидвох сторонах можна провести непарну кількість прямих, то можна показати, що перемагає учасник у кого більша кількість прямих на меншій стороні. Перший учасник може собі це гарантувати, якщо буде проводити прямі по меншій стороні, поки це можливо.
Розглянемо стрічки \(i\) та \(i+1\) для \(1 \leq i \leq n -1\). Подивимося на першу букву, яка відрізняється. Нехай відрізняється символ на позиції j, тоді додамо ребро з \(s[i][j]\) до \(s[i+1][j]\). Тепер подивимося, чи в побудованому орієнтованому графі є цикл. Якщо так, то відповідь No, інакше Yes.
Відповідь не більша 4, адже ми можемо додати по одній точці в кожен кут прямокутника мінімального розміру, в який можливо вмістити усі точки.
Давайте для кожного кута окремо знайдемо, чи можна не додавати точку в цьому куті. Нехай це лівий нижній кут. Знайдемо найлівішу точку, серед таких найнижчу. Далі будемо дивитись на точки зліва направо і якщо точка є найнижчою з розглянутих, то вона повинна бути в маршруті, а також точка, щоб повернути від попередньої точки вниз.
Таким чином для кожного кута, якщо для нього не додавати додаткової точки, можна знайти набір точок, які будуть на маршруті.
Також якщо для декількох кутів ми використаємо однакову точку, то маршрут вийде вироджений, що нам не підходить. Тому можна перебрати, для яких з кутів ми не будемо додавати точки та перевірити, чи маршрути цих кутів не мають спільних точок.
Іншим розв’язком буде навпаки перебирати, які точки на кутах ми додаємо, та перевірити, чи можна побудувати валідний маршрут. В такому випадку потрібно окремо розглянути випадки, коли всі точки у вхідних даних лежать на одній вертикалі чи горизонталі, що не було потрібно у попередньому розв’язку.
Нехай \(a_1, \ldots, a_n\) — послідовність складностей підйому, на основі якої Зеник записав у своєму зошиті послідовність \(c_1, \ldots c_n\). Розглянемо найправішу позицію, де знаходиться мінімальний елемент у послідовності \(a\), і позначимо її \(m_1\). Очевидно, що на цій позиції у послідовності Зеника має бути нуль \(c_{m_1} = 0\), а правіше від неї усі елементи мають бути додатними \(c_{m_1+1} > 0, \ldots, c_{n} > 0\). Отже, ми можемо легко знайти \(m_1\) як позицію найправішого нуля послідовності \(c\).
Якщо нулів немає взагалі, то Зеник припустився помилки у своїх записах, а кількість послідовностей, що їм відповідають, рівна нулю. Інакше запишемо у позиції \(m_1\) мінімально можливе значення \(a_{m_1} = 1\), видалимо \(a_{m_1}\) та \(c_{m_1}\) і перейдемо до меншої підзадачі. Видалення елементу \(a_{m_1}\) результуватиме у зменшення на одиницю усіх елементів \(c\), що знаходяться після позиції \(m_1\). Зауважте, що всі вони після такої операції залишаться невід’ємними.
Далі кожного разу будемо аналогічно знаходити найправішу позицію мінімального елемента \(m_j\) і будемо присвоювати \(a_{m_j}\) мінімально можливе значення. Якщо позиція є більшою за попередню \(m_j > m_{j-1}\), то ми маємо використати значення принаймні на одиницю більше ніж попереднє \(a_{m_j} = a_{m_{j - 1}} + 1\), інакше можемо використати таке ж \(a_{m_j} = a_{m_{j - 1}}\).
Нехай ми успішно знайшли усі позиції \(m_1, \ldots, m_n\). Якщо останнє найбільше використане значення \(a_{m_n}\) є більшим ніж \(k\), то ми не можемо побудувати жодної послідовності \(a\), оскільки щоразу використовували мінімально можливі значення. Інакше ми маємо залишок \(r = k - a_{m_n} \ge 0\) котрий можна розподілити у певний спосіб серед \(n\) позицій послідовності \(a\). Скажімо значення найправішого мінімального елемента \(a_{m_1}\) замість 1 можна обирати більшим, наприклад, 47. Це призведе до автоматичного збільшення на 46 усіх інших елементів \(a\). Легко бачити, що кількість способів розподілити залишок r повністю чи частково між \(n\) позиціями рівна кількості комбінацій з повтореннями з \(n+1\) по \(r\).
Операції пошуку найправішого нуля та зміни елементів послідовності \(c\) можна реалізувати за \(O(\log n)\), наприклад, використавши дерева відрізків. У такий спосіб загальна складність розв’язку буде \(O(n \cdot \log n)\).
Якщо після першого ходу Зеника Марічка не матиме змоги побити жодну фігуру Зеника, то він виграє. Тут показано один з можливих списків ходів для тесту A5 G5 H5.
В іншому випадку, матимемо нічию. Зеник не зможе зробити такий хід, якщо всі три фігури Зеника розташовані на одній вертикалі або горизонталі, король знаходить між турами, при цьому жодні дві фігури не торкаються одна одної аналіз такої позиції.
Також існують винятки, коли Зеник таки перемагає. Аналіз позицій, разом з поясненнями за посиланнями:
Тож можливо було або розглянути усі випадки, або перебрати усі перші ходи та перевірити, чи чорний король не може нічого побити.
G. Гірський спостережний пункт
Спочатку без видалення одного з кабелів для усіх веж знайдемо мінімальні кількості каменюк \(c_1, \ldots, c_n\), що потрібні для побудови. Це можна зробити опрацьовуючи вежі по черзі так, щоб кожного разу для поточної вежі усі, з якими вона з’єднана блакитним кінцем кабелю, вже були опрацьовані раніше. Тоді для поточної вежі ми можемо зафіксувати кількість каменюк і оновити такі кількості для усіх, з якими вона з’єднана жовтим кінцем кабелю.
Для вежі \(k\) розглянемо множину кабелів \(s_k\), що приєднані до неї жовтим кінцем та множину відповідних веж \(t_k\), до яких вони ведуть. Кількість каменюк для вежі \(k\) можна зменшити тільки якщо ми видалимо серед кабелів \(s_k\) той, що веде до вершини з найбільшою кількістю каменюк серед \(t_k\). Назвемо такий кабель важким, а вежу, до якої він веде назвемо батьківською. Кількість каменюк, яку вдасться зекономити на побудові вежі \(k\) видаливши важкий кабель, позначимо \(d_k\). Зауважимо, що \(d_k\) можна легко знайти врахувавши вежі з найбільшою та другою найбільшою кількістю каменюк серед \(t_k\). Також варто окремо врахувати випадки коли множина \(t_k\) порожня або містить тільки одну вежу.
Розглянемо набір кореневих дерев, що утворені важкими кабелями. Очевидно, що є сенс видалити одне з ребер в одному з цих дерев. Нехай ми видаляємо ребро, що веде з вежі \(k\) до її батьківської вежі. Тоді для вежі \(m\) кількість каменюк може змінитись тільки якщо \(m\) знаходиться у піддереві вежі \(k\). Легко бачити, що на побудові вежі \(m\) можна буде зекономити кількість каменюк, що рівна мінімуму зі значень \(d\) на шляху від \(m\) до \(k\).
Далі будемо розглядати усі важкі кабелі у порядку від менших \(d\) до більших. Нехай поточний важкий кабель з’єднує вежу \(k\) з її батьком. Тоді у піддереві вежі \(k\) усі вершини отримають покращення \(d_k\). Нехай розмір піддерева \(k\) рівний \(v_k\), тоді до значення \(d_k \cdot v_k\) можна додати до результату покращення усіх важких кабелів на шляху від \(k\) до кореня. Потім видаляємо поточний важкий кабель і у такий спосіб від’єднуємо вежу \(k\) від піддерева її батька.
Результатом буде сума \(c_1, \ldots, c_n\) мінус максимальне з результатів покращень важких кабелів. Описані операції можна реалізувати, наприклад, використовуючи дерева відрізків побудовані на обході дерев важких кабелів.