Для розв’язання задачі необхідно просимулювати процес описаний в умові, пройшовши по всіх елементах електричної лінії зліва направо.
Можна довести, що оптимальний для кота розв’язок досягається коли він спочатку стоятиме половину часу, а потім бігтиме другу половину часу. Це пояснюється наступним чином. Нехай кіт доганяє мишу на \(T\) секунд. Тоді, незалежно від чергування режимів, кіт сумарно стоятиме і бігтиме по \(\frac{T}{2}\) секунд. Шукатимемо відповідь у вигляді описаному в першому реченні.
Тоді, існує два випадки:
Кіт почне наздоганяти мишу до того як вона стане в діаметрально протилежну точку кола. Це рівноцінно ситуації, в якій кіт весь час біжить зі швидкістю \(\frac{a}{2}\). Тоді відповідь рівна \(\frac{d}{0.5 \cdot a - b}\). Цей випадок допустимий лише якщо \(0.5 \cdot a > b\).
Поки кіт збирає достатньо енергії, миша стає в діаметрально протилежну точку відносно кота і чекає. Тоді відповідь рівна \(2 \cdot \frac{0.5 \cdot l}{a - b}\).
Відповіддю на задачу буде мінімум серед допустимих випадків.
Для малих n (\(n \le 11\)) можна перебрати всі варіанти за \(O((n-1)!)\).
При \(n > 11\) відповідь завжди буде рівною 3. Це можна довести побудувавши загальні послідовності ходів для випадків \(n = 3 \cdot k\), \(n = 3 \cdot k + 1\) і \(n = 3 \cdot k + 2\).
Нехай в розв’язку \(k\) хороших клітин. Тоді за умовою задачі \(k \ge 0.774 \cdot n \cdot m\). Формулу можна перезаписати як \(k \ge \frac{4}{5} \cdot (1 - \epsilon) \cdot n \cdot m\), де \(\epsilon\) це якесь маленьке число. Множник \(\frac{4}{5}\) означає, що для кожної клітини, в яку покладено міну, всі 4 сусідні клітинки повинні бути заміновані лише нею. Інакше не вийде досягнути бажаної щільності. Множник \((1 - \epsilon)\) дозволяє неефективності замінування на краю поля.
Задачу можна розв’язати використовуючи патерн показаний на зображенні нижче:
Більш формально, міну можна покласти в кожну клітину для якої виконується \(x + 2y \equiv 0 \; (\text{mod } 5)\).
Будемо репрезентувати дороги — як ребра графа, а міста — як вершини. Тоді згідно з умовою граф — це дерево.
Помітимо що шлях буде повністю визначений тим в якому порядку ми йдемо в дітей кожної вершини (вершин, що є сусідами певної вершини та не лежать на шляху від кореня до даної вершини)
Нехай \(dp_v\) — це відповідь на задачу якби Зеник ходив тільки по піддереву вершини \(v\), тобто обхід піддерева який мінімізує втомленість.
\(dp_1\) — буде відповіддю на задачу.
Назвемо суму \(A_i\) в піддереві вершини \(v\) — \(W_i\).
Назвемо кількість вершин в піддереві вершини \(v\) — \(SZ_i\).
Нехай ми знаємо оптимальний порядок, в якому будемо йти з вершини \(v\) в її дітей. Тоді для якоїсь дитини, назвемо її \(to\), нехай \(pref\) — це сума усіх значень \(W_i\) інших дітей вершини \(v\), яких ми обійдемо швидше за \(to\).
Порахуємо скільки втомленості Зеник отримає пройшовши по піддереву \(to\) як частині оптимального обходу піддерева \(v\). Помітимо що до кожного ребра ми додамо вагу \(pref\) якщо порівнювати з оптимальним обходом виключно піддерева \(to\). Іншими словами на інтервалі від заходу до виходу з \(to\) втомленість буде — \(dp_{to}+pref*(SZ_{to}-1)*2\) тобто ми додамо до \(SZ_{to}-1\) ребер \(pref\) по два рази, бо ми пройдемо по кожному ребру в сторону від кореня і потім назад. Для ребер що йдуть безпосередньо в дітей теж можна порахувати таке значення, бо ми знаємо вагу скарбу на вході та на виході в цю вершину.
Тепер залишилось навчитись знаходити оптимальний порядок. Можна уявити піддерева як пари \((w,sz)\) і їх потрібно упорядкувати так, щоб \(\sum_{i<j}w_i*sz_j\) була мінімальною.
Якщо всі \(sz\) дорівнюють \(1\) то це зробити легко, потрібно посортувати їх по вагах. Щоб узагальнити, помітимо, що \(sz\) — цілі і якщо розбити пару \((w,sz)\) на \(sz\) пар по \((\frac{w}{sz},1)\) то вони йтимуть в оптимальному порядку поспіль як один елемент.
Таким чином при розбитті на одиниці оптимальний порядок не зміниться. Тому можна посортувати пари по \(\frac{w}{sz}\) і отримати оптимальний порядок.
Краще не ділити явно, а порівнювати дроби як пари.
Складність \(O(n*log(n))\) (від сортування).
Давайте кожну кульку \(p_i\) з’єднаємо з двома іншими кульками \(q_i\) і \(q_j\) (\(q_j\) така, що значення на ній таке ж, як на \(p_i\)). Отримаємо якусь кількість циклів парного розміру. Надалі розглядатимемо цикли в яких 4 і більше кульок.
Два цикли довжинами \(2n\) і \(2m\) можна розставити за \(n + m\) кроків наступним чином. Позначимо індекси обох циклів як \(i_1, i_2, \ldots, i_n\) та \(j_1, j_2, \ldots, j_m\). Індекси розташовані в порядку обходу циклу. Наприклад, \(p_{i_1} = q_{i_2}\), \(p_{i_2} = q_{i_3}\) і так далі. Спочатку виконаємо \(m\) свапів вигляду \((p_{i_1}, q_{j_k})\) для \(k = 1, 2, \ldots, m\). Далі виконаємо \(n\) свапів вигляду \((p_{i_k}, q_{j_1})\) для \(k = n, n-1, \ldots, 1\).
Якщо кількість циклів була непарною, то залишиться ще один цикл. Нехай його довжина \(2n\). Його можна розв’язати за \(n + 1\) крок. Позначимо індекси циклу як \(i_1, i_2, \ldots, i_n\). Спочатку виконаємо свап \((p_{i_1}, q_{j_1})\). Далі виконаємо \(n\) свапів вигляду \((p_{i_k}, q_{j_1})\) для \(k = n, n-1, \ldots, 1\).
Оберемо якийсь степінь \(k\), нехай це буде — \(b\).
Тоді будь-яке число \(x\) — можна репрезентувати як \(m \cdot k^b+z\), де \(0 \le m\) і \(0 \le z < k^b\).
Нехай \(F(x) = \sum_{p=0}^{\infty} \lfloor \frac{x}{k^p} \rfloor\) (функція з умови).
Тоді \(F(m \cdot k^b+z) = F(m \cdot k^b) + F(z)\).
Розіб’ємо числа від \(0\) до \(n\) на блоки розміру \(k^b\) такі, що \((k^b+\frac{n}{k^b})\) – мінімальне. При \(b = \frac{log(n)}{2 \cdot log(k)}\) заокругленому до найближчого цілого сума не перевищуватиме \(2 \cdot (n \cdot k)^{\frac{1}{2}}\), оскільки найбільше з двох чисел не перевищуватиме \((n \cdot k)^{\frac{1}{2}}\).
Суфікс, який не потрапить в жоден блок, рахуватимемо окремо, його довжина буде менше \(k^b\).
Тоді для кожного блоку, межі якого повністю лежать від \(0\) до \(n\) включно, порахуємо його \(F(B \cdot k^b)\) де \(B\) — номер блоку (нумерація від 0). І для чисел \(z\) від \(0\) до \(k^b\) виключно порахуємо \(F(z)\). Тоді будь-яке число буде складатись з \(F(B \cdot k^b)\) + \(F(z)\).
Для кожного запиту нам потрібно рахувати кількість пар \((B,z)\) таких що \(F(B \cdot k^b+z)=g \: (mod \: s)\). Перебиратимемо \(B\) і додаватимемо кількість таких \(z\) що \(F(B \cdot k^b)+F(z)=g \: (mod \: s)\). Це можна зробити тримаючи в масиві кількість кожної остачі та перераховуючи для кожного запиту.
Якщо порахувати усі \(F\) до обробки запитів, а при обробці брати лише модулі то складність буде: \(O(\sqrt{nk} \cdot (\log(n)+q))\).