В даній задачі потрібно перевірити чи жеребець і кобила знаходяться у
одній чверті. Для перевірки цього можна перевірити, чи знак координати
по осях x та y є однаковим. Найпростіше таку
перевірку можна зробити перевіривши чи добутки значень їх x
та y координат є додатними числами.
Перш за все треба перевірити чи існує квадрат, що з площею рівною сумарній площі необхідній для коней. Нехай існує такий квадрат зі стороною \(n\), тоді у випадку якщо \(n\) парне, то ми завжди можемо розташувати наших коней.
У випадку коли \(n\) є непарним, то достатньо перевірити чи можна розташувати деяких коней, щоб покрити перший рядок і перший стовпець. Якщо вийде, то ми просто перейдемо до квадрата зі стороною \((n - 1)\), який є парним і ми в нього завжди зможемо розташувати коней. Оскільки ми можемо розташовувати лише лошат і кобил в перший рядок і стовпець, то нам цікаво чи в нас є достатньо цих коней, щоб покрити повністю ці ділянки: \(a + 2b \ge 2n - 1\).
Задачу можна переформулювати у таких термінах: ми залишаємо лише підрядок від \(l\)-го до \(r\)-го символу, за одну операцію можна видалити підрядок який має перший і останній символ однакові та має хоча б два символи та потрібно відповісти чи можна такими операціями видалити заданий підрядок.
У випадку коли \(l = r\) зрозуміло,
що ми не можемо виконати жодної операції тому відповідь No.
Якщо ж \(s[l] = s[r]\) тоді ми за одну
операцію можемо видалити весь цей підрядок.
Для випадку коли \(s[l] \neq s[r]\) достатньо перевірити чи існує така позиція \(l < i < r - 1\) така що \(s[l] = s[i]\) та \(s[i + 1] = s[r]\) у такому випадку ми можемо видалити весь цей підрядок за дві операції, якщо ж такої позиції немає, то ми не зможемо видалити цей підрядок.
Дану задачу можна переформулювати в термінах графів: кожна хата це вершина графа, а також для зручності визначимо вершину яка буде початком для кур’єра, тоді для того аби дійти з цієї вершини до хати, в якій кур’єр купить овес необхідно заплатити ціну за мішок. Також ми знаємо скільки коштує переміститись між сусідніми хатами та ціна на переміщення між деякими парами хат — ціна проїзду в маршрутці.
Шукана відповідь буде рівна найдешевшому = найкоротшому шляху з початкової вершини для кур’єра до відповідної хати. Для пошуку найкоротшого шляху можна використати алгоритм Дейкстри.
Розглянемо певний шлях (\(a_1\), \(a_2\), \(\dots\), \(a_k\)) і нехай кількість сусідів для вершин на цьому шляху рівна \(sz_1\), \(sz_2\), \(\dots\), \(sz_k\) відповідно. Тоді такий шлях розділить дерево на \(1 + (\sum_{i = 1}^{k} sz_i) - 2(k - 1)\), так початково була одна компонента і кожне ребро з вершиною шляху збільшить кількість компонент на 1, окрім ребер ті що є на шляху - таких \(k - 1\) і ми їх врахували двічі. Цю формулу можна перетворити на таку \(3 + \sum_{i = 1}^{k} (sz_i - 2) = 3 + \sum_{i = 1}^{k} val_{a_i}\), де \(val_{v}\) рівне кількості сусідів вершини \(v\) мінус 2.
В термінах задачі нам потрібно максимізувати суму значень \(val_v\) на шляху починаючи з вершини \(w\) і додати 3 до цього значення. Знайдемо максимальний по сумі значень шлях у дереві \(A - B\), подібно до алгоритму пошуку діаметра в дереві. Можна довести що максимальний шлях з вершини \(w\) буде завершуватись у одній з вершин \(A\) або \(B\). Тому порахуємо сумарне значення на шляху з вершини \(A\) і вершини \(B\), відповідь буде максимальне значення з цих двох шляхів плюс 3.
Побудуємо граф із \(n\) вершин, де вершина відповідає за остачу по модулю \(n\). З вершини \(x\) будемо мати два переходи у вершини \((10x + 4)\%n\) та \((10x + 7)\%n\) - це буде означати що до побудованого числа з остачою \(x\) ми можемо доставити цифру в кінець і отримати числа з такими остачами. У такому графі нас цікавить в першу чергу найкоротший цикл з вершини що відповідає за остачу 0 і серед таких найкоротших циклів нас цікавить лексикографічно найменший. Для того аби отримати потрібний результат будемо виконувати пошук вшир, де першочергово будемо розглядати перехід з додаванням 4 і після цього з додаванням 7.
Розглянемо конструкцію де певне число \(val\) довжини \(len\) повторюємо певну кількість разів \(x\) так аби воно ділилось на \(n\). Розглянемо значення цього числа \(\frac{val \cdot (10^{len \cdot x} - 1)}{(10^{len} - 1)}\), це число має ділитись на \(n\), тобто \(val \cdot (10^{len \cdot x} - 1)\) має ділитись на \(n \cdot (10^{len} - 1) = m\).
Використаємо теорему Ейлера: для взаємнопростих \(a\) та \(m\) виконується \(a^{\varphi(m)} \equiv 1 \pmod m\). Розглянемо такі \(n\) які взаємнопрості з 10, також використовуючи те що \(10^{len} - 1\) взаємнопросте з 10, отримаємо \(10^{len \cdot \varphi(m)} - 1 \equiv 0 \pmod m\). Якщо ми число \(val\) повторимо \(x \cdot \varphi(n(10^{len}-1))\) разів то таке утворене число буде ділитись на \(n\), проте це правильно лише для \(n\) взаємнопростих з 10.
Розглянемо що відбувається коли \(n\) не є взаємнопростим із 10. Якщо \(n\) ділиться на 5 то у такому випадку не існує ніякого щасливого числа, яке ділиться на 5.
У іншому випадку \(n\) ділиться на 2, це означає що нам необхідно задовольнити аби щасливе число ділилось на певний степінь двійки. Для вирішення цього візьмемо \(val = 447444474444447744\) - щасливе число яке ділиться на \(2^{18}\), а отже ділиться і на усі можливі степені які може містити число \(n\).
Можна показати що \((10^{18} - 1) \cdot \varphi(10^{18} - 1) \cdot \varphi(n)\) ділиться на \(\phi(n(10^{18} - 1))\). Отже, нам достатньо рядок \(447444474444447744\) повторити \((10^{18} - 1) \cdot \varphi(10^{18} - 1) \cdot \prod \varphi(n_i)\). Використовуючи правила ми можемо множити кількість повторів без жодних проблем.