Паліндром парної довжини має вигляд \(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\).
Спершу треба розглянути тривіальні випадки: круги не перетинаються або один круг міститься в іншому.
На рисунках зображені варіанти розташування кіл. Застосувавши теорему косинусів до трикутника \(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\) (формула для площі сегмента з Вікіпедії). Площу іншого сегмента знаходимо так само.
Скористаємося підходом динамічного програмування. Якщо ви не знаєте, що це, то радимо прослухати відеолекцію.
Станом динаміки \(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)\).
Нехай \(s_i=\sum_{j=1}^{i-1} a_j\). Пересунути фішку з позиції \(x\) у позицію \(y\) коштує \(|s_y-s_x|\).
Тепер задачу можна переформулювати так. Задано \(n\) точок на прямій, \(i\)-а точка має координату \(s_i\). Починаємо з точки \(s_1=0\). Хочемо відвідати всі та мінімізувати відстань, яку пройдемо.
Очевидно, що оптимально піти до найлівішої точки, потім — до найправішої, або навпаки.
Складність розв’язку: \(O(n)\).