Зеник розіб’є \(k\) задач на 2, а \(n - k\) задач він не змінюватиме, отже в нього буде \((2 \cdot k) + (n - k) = n + k\) задач. Тому в задачі достатньо перевірити чи це число не більше ніж 26.
Одним із розв’язків \(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\).
У рівнянні \(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\) розв’язків.
Будемо шукати відповідь у вигляді рівнобедреного трикутника.
Для пошуку рівнобедреного трикутника використаємо двійковий пошук кута між двома рівними сторонами трикутника \(2 \cdot \alpha\), у випадку \(\alpha = 0\) (вироджений трикутник) відношення \(\frac{r}{P}\) дорівнює нулю, а у випадку \(\alpha = 30^{\circ}\) (рівносторонній трикутник) відношення максимальне. Отже, нам усього лише необхідно вивести формулу відношення — \(f(\alpha)\).
\(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}\).
Графік цієї функції зображено на рисунку. Бачимо, що функція монотонна, отже можна скористатися двійковим пошуком.
Якщо в несправедливій шерензі залишити тільки числа більші за деяке число \(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\).
Почнімо з простішої версії. Розглянемо випадок, коли \(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\) можна покрити так:
Тут поле \(2 \times 2\) покриваємо описаним раніше способом, а кожну іншу L-троміно ставимо тричі.
Тоді можна розділити нашу кімнату на частини з такими розмірами: \(7 \times 7\), \((n - 7) \times 7\), \(7 \times (m - 7)\) та \((n - 7) \times (m - 7)\). Зауважимо, що \(n - 7\) та \(m - 7\) парні, тому ми зможемо покрити кожну з частин.