Обласна олімпіада 2018 (розбір) | Статті

A. Гра в карти

Паліндром парної довжини має вигляд $s+r$, а непарної — $s+c+r$, де $s$ — деякий рядок, $r$ — розвернутий $s$, $c$ — деякий символ.

Кожен символ зустрічається однакову кількість разів в $s$ і $r$. Якщо символ зустрічається на $a$ картах, то додамо його $\left\lfloor \frac{a}{2} \right\rfloor$ входжень до рядка $s$. Якщо існує символ $c$, який зустрічається на непарній кількості карт, то виведемо паліндром $s+c+r$, інакше — $s+r$.

Код розв’язку C++

Код розв’язку Python

B. Земля й Місяць

Спершу треба розглянути тривіальні випадки: круги не перетинаються або один круг міститься в іншому.

На рисунках зображені варіанти розташування кіл. Застосувавши теорему косинусів до трикутника $O_1AO_2$, отримаємо $r_2^2=d^2+r_1^2-2 d r_1 \cos \alpha_1$, $r_1^2=d^2+r_2^2-2 d r_2 \cos \alpha_2$. Звідси можемо знайти кути $\alpha_1$ і $\alpha_2$.

Площа перетину кругів — це сума площ двох сегментів. Центральний кут сегмента першого круга — $\angle AO_1B=2\alpha_1$, площа цього сегмента — $\left(\alpha_1 - \frac{\sin 2 \alpha_1}{2}\right)r_1^2$ (формула для площі сегмента з Вікіпедії). Площу іншого сегмента знаходимо так само.

Код розв’язку C++

Код розв’язку Python

C. Сходи до Місяця

Скористаємося підходом динамічного програмування. Якщо ви не знаєте, що це, то радимо прослухати відеолекцію.

Станом динаміки $dp$ є трійка чисел $(i, mn, mx)$, де $i$ — скільки сходинок уже подолав Зеник, $mn$ і $mx$ — найкоротший і найдовший кроки. Значенням динаміки є кількість способів потрапити в такий стан.

Ініціалізуємо значення $dp[i][i][i] = 1$ — Зеник зробив один крок на $i$ сходинок. Зі стану $(i, mn, mx)$ є переходи в стани $(i+j, \min\{mn, j\}, \max\{mx, j\})$, де $j$ — довжина нового кроку.

Відповіддю на задачу буде сума $dp[n][mn][mx]$ для всіх $mn, mx$, що задовольняють умову $mx - mn \le k$.

Складність розв’язку: $O(n^4)$.

Код розв’язку C++

Код розв’язку Python

D. Гра на прямiй

Нехай $s_i=\sum_{j=1}^{i-1} a_j$. Пересунути фішку з позиції $x$ у позицію $y$ коштує $|s_y-s_x|$.

Тепер задачу можна переформулювати так. Задано $n$ точок на прямій, $i$-а точка має координату $s_i$. Починаємо з точки $s_1=0$. Хочемо відвідати всі та мінімізувати відстань, яку пройдемо.

Очевидно, що оптимально піти до найлівішої точки, потім — до найправішої, або навпаки.

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

Код розв’язку C++

Код розв’язку Python