Короткий розбір The Algo Battles 2023 - Етап 4 | Articles

A. Змагання від Зеника

Зеник розіб’є \(k\) задач на 2, а \(n - k\) задач він не змінюватиме, отже в нього буде \((2 \cdot k) + (n - k) = n + k\) задач. Тому в задачі достатньо перевірити чи це число не більше ніж 26.

B. Подвоєна сума квадратів

Одним із розв’язків \(x_i^2 + y_i^2 = 2 \cdot (a_i^2 + b_i^2)\) є \(x_i = a_i - b_i\) та \(y_i = a_i + b_i\).

Переконаємось у правильності цього розв’язку: \(x_i^2 + y_i^2 = (a_i - b_i)^2 + (a_i + b_i)^2 = a_i^2 - 2 \cdot a_i \cdot b_i + b_i^2 + a_i^2 + 2 \cdot a_i \cdot b_i + b_i^2 = 2 \cdot (a_i^2 + b_i^2)\).

Оскільки нам необхідно знайти пару \(x_i, y_i \ge 0\), тому візьмемо \(x_i = |a_i - b_i|\), що не змінює правильність розв’язку.

С. Дві купки

Розглянемо декілька станів гри:

  • \(a = b\) — в такому стані виграє другий, бо він завжди може зробити симетричний хід і повернутись до цього ж стану, але з меншою кількістю камінців і стан \(a = b = 0\) програшний.

  • \(a > b\) — перший гравець може зробити дві купки рівні і тоді другий гравець буде у програшному стані

  • \(a < b\) та \(b - a \le \lfloor \frac{b}{2} \rfloor\) — у цьому стані першому необхідно забрати \(b - a\) камінців з купки другого. Перший гравець може забрати не більше ніж \(\lfloor \frac{b}{2} \rfloor\), отже він зможе зробити дві купки рівними.

  • \(a < b\) та \(b - a > \lfloor \frac{b}{2} \rfloor\) — у цьому стані по аналогії до попереднього випадку перший гравець не зможе своїм першим ходом зробити дві купки рівні, після його ходу буде і надалі виконуватись умова \(a < b\). Тобто перший перейде у такий стан в якому другий має виграшну стратегію, аналогічно до другого випадку.

Узагальнюючи усі умови можна сказати, що перший гравець виграє якщо \(2 a \ge b\) та \(a \ne b\).

D. Зарозумілий Зеник

У рівнянні \(f(k) = m\) ми знаємо, що існує \(p\) таке, що \(k + p = m\) та \(k\) ділиться на \(p\), отже і \(m\) теж ділиться на \(p\). Отже, кандидатами на розв’язок є числа \(k = m - p\), де \(p\) є простим дільником \(m\). Для того аби мати хоча б \(n\) кандидатів на розв’язок, необхідно аби число \(m\) містило хоча б \(n\) різних простих.

Тому розглянемо число \(m = 2 \cdot 3 \cdot 5 \cdot ...\) — добуток перших \(n > 1\) простих чисел. Це число є найменшим числом, для якого рівняння \(f(k) = m\) має хоча б \(n\) кандидатів на розв’язок.

Розглянемо один із його простих дільників \(p\), тоді доведемо, що \(f(m - p) = m\). Для цього нам потрібно довести, що немає такого простого дільника \(q < p\), що \(m - p\) ділиться на \(q\). Припустимо, що такий дільник існує, оскільки ми вибрали число \(m\) як добуток перших \(n\) простих чисел, то й серед цих простих чисел є \(q\). Отже, \(q \mid m\), оскільки \(p\) просте то \(q \nmid p\), отже \(q \nmid (m - p)\). Отримали суперечність, отже ми довели що \(f(m - p) = m\), оскільки різних \(p\) є \(n\) отже рівняння \(f(k) = m\) має хоча б \(n\) розв’язків.

E. Віднови трикутник

Будемо шукати відповідь у вигляді рівнобедреного трикутника.

Для пошуку рівнобедреного трикутника використаємо двійковий пошук кута між двома рівними сторонами трикутника \(2 \cdot \alpha\), у випадку \(\alpha = 0\) (вироджений трикутник) відношення \(\frac{r}{P}\) дорівнює нулю, а у випадку \(\alpha = 30^{\circ}\) (рівносторонній трикутник) відношення максимальне. Отже, нам усього лише необхідно вивести формулу відношення — \(f(\alpha)\).

image

\(P = 2 \cdot r \cdot ctg(\alpha) + 4 \cdot r \cdot ctg(45^{\circ} - \frac{\alpha}{2}) \implies \frac{r}{P} = (2 ctg(\alpha) + 4 ctg(45^{\circ} - \frac{\alpha}{2}))^{-1}\).

image

Графік цієї функції зображено на рисунку. Бачимо, що функція монотонна, отже можна скористатися двійковим пошуком.

F. Несправедлива шеренга

Якщо в несправедливій шерензі залишити тільки числа більші за деяке число \(x\), то шеренга залишиться несправедливою для будь-якого \(x\).

Розглянемо вигляд шеренги якщо залишити усі числа строго більші за \(x\), нехай таких чисел \(k\). Після цього подивимось, скільки є способів вставити числа, що рівні \(x\) у цю шеренгу. Для чисел \(x\) є \(k+1\) позиція, куди їх можна вставити.

Назвемо числа \(y\) з шеренги, що задовольняють \(y < 2 x\) малими.

У несправедливій шерензі не могли стояти поруч два малих числа, бо тоді вони б порушували умову несправедливості.

Число \(x\) не можна ставити в шеренгу поруч (ні ліворуч, ні праворуч) з малим числом, бо знов тоді порушимо умову несправедливості.

Позначимо кількість малих чисел \(s\). Залишається \(k+1-2s\) позицій, куди можна вставити числа \(x\), бо кожне мале число забороняє дві позиції: ліворуч і праворуч від себе.

Нехай \(p\) — кількість чисел \(x\), які потрібно вставити.

Ми вибираємо \(p\) з \(k + 1 - 2 \cdot s\) позицій \(C^{p}_{k+1 - 2 s}\) способами.

Зауважимо, що ця формула не залежить від розташування чисел у шерензі, отже відповідь буде рівна добутку значень \(C^{p}_{k+1 - 2 s}\) для всіх можливих \(x\).

G. Дивна плитка

Почнімо з простішої версії. Розглянемо випадок, коли \(n\) і \(m\) парні. Тоді ми можемо розділити нашу кімнату на ділянки з розміром \(2 \times 2\), і замостити кожну таку ділянку. Для того щоб замостити ділянку з розміром \(2 \times 2\) можна поставити по одному L-троміно кожного з чотирьох типів. Тоді кожна клітинка буде покрита тричі.

Тепер розглянемо випадок, коли \(n\) або \(m\) непарне. Без втрати загальності вважатимемо, що \(n\) — непарне. Тоді ми можемо розділити кімнату на дві частини з розмірами \(3 \times m\) та \((n - 3) \times m\). Оскільки \(n\) непарне, то \((n - 3)\) парне, отже ми можемо покрити частину з розміром \((n - 3) \times m\) описаним раніше способом. Щоб покрити ділянку з розміром \(3 \times m\), розділимо її на частини з розміром \(3 \times 2\). Покрити таку частину можна двома L-троміно. Оскільки клітинки з іншої частини ми покрили тричі, то частинки з розміром \(3 \times 2\) потрібно також покрити тричі.

Тепер перейдімо до складнішої версії. Єдиний випадок, який ми ще не розглянули, коли \(n\) і \(m\) непарні. Зауважимо, що кімнату з розміром \(7 \times 7\) можна покрити так:

image

Тут поле \(2 \times 2\) покриваємо описаним раніше способом, а кожну іншу L-троміно ставимо тричі.

Тоді можна розділити нашу кімнату на частини з такими розмірами: \(7 \times 7\), \((n - 7) \times 7\), \(7 \times (m - 7)\) та \((n - 7) \times (m - 7)\). Зауважимо, що \(n - 7\) та \(m - 7\) парні, тому ми зможемо покрити кожну з частин.