Processing math: 100%

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

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

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

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

Одним із розв’язків x2i+y2i=2(a2i+b2i) є xi=aibi та yi=ai+bi.

Переконаємось у правильності цього розв’язку: x2i+y2i=(aibi)2+(ai+bi)2=a2i2aibi+b2i+a2i+2aibi+b2i=2(a2i+b2i).

Оскільки нам необхідно знайти пару xi,yi0, тому візьмемо xi=|aibi|, що не змінює правильність розв’язку.

С. Дві купки

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

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

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

  • a<b та bab2 — у цьому стані першому необхідно забрати ba камінців з купки другого. Перший гравець може забрати не більше ніж b2, отже він зможе зробити дві купки рівними.

  • a<b та ba>b2 — у цьому стані по аналогії до попереднього випадку перший гравець не зможе своїм першим ходом зробити дві купки рівні, після його ходу буде і надалі виконуватись умова a<b. Тобто перший перейде у такий стан в якому другий має виграшну стратегію, аналогічно до другого випадку.

Узагальнюючи усі умови можна сказати, що перший гравець виграє якщо 2ab та ab.

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

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

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

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

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

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

Для пошуку рівнобедреного трикутника використаємо двійковий пошук кута між двома рівними сторонами трикутника 2α, у випадку α=0 (вироджений трикутник) відношення rP дорівнює нулю, а у випадку α=30 (рівносторонній трикутник) відношення максимальне. Отже, нам усього лише необхідно вивести формулу відношення — f(α).

image

P=2rctg(α)+4rctg(45α2)rP=(2ctg(α)+4ctg(45α2))1.

image

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

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

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

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

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

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

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

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

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

Ми вибираємо p з k+12s позицій Cpk+12s способами.

Зауважимо, що ця формула не залежить від розташування чисел у шерензі, отже відповідь буде рівна добутку значень Cpk+12s для всіх можливих x.

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

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

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

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

image

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

Тоді можна розділити нашу кімнату на частини з такими розмірами: 7×7, (n7)×7, 7×(m7) та (n7)×(m7). Зауважимо, що n7 та m7 парні, тому ми зможемо покрити кожну з частин.