Помітимо, що щасливе число \(a + b\) завжди менше за 444444. Тому у цій задачі достатньо перебирати доданок \(b\) до \(5 \cdot 10^5\) та перевіряти, чи є \(a + b\) щасливим числом. Зауважимо, що при перевірці щасливості треба уважно розглянути випадки коли \(a\) або \(b\) рівні 0.
B. Щасливі числа без послідовних четвірок
Використаємо підхід динамічного програмування. Використовуватимемо такі позначення:
\(ans_i\) — відповідь на задачу для \(i - 1\), тобто сума щасливих чисел, довжина яких строго менша за \(i\).
\(dp_{4, i}\) — сума щасливих чисел, що мають довжину \(i\) та останню цифру 4.
\(cnt_{4, i}\) — кількість щасливих чисел, що мають довжину \(i\) та останню цифру 4.
\(dp_{7, i}\) — сума щасливих чисел, що мають довжину \(i\) та останню цифру 7.
\(cnt_{7, i}\) — кількість щасливих чисел, що мають довжину \(i\) та останню цифру не 4 (це буде цифра 7, або число з 0 цифр).
Ці значення можна обраховувати за такими формулами:
\(ans_i = ans_{i - 1} + dp_{4, i - 1} + dp_{7, i - 1}\)
\(dp_{4, i} = 10 \cdot dp_{7, {i - 1}} + 4 \cdot cnt_7\)
\(cnt_{4, i} = cnt_{7, {i - 1}}\)
\(dp_{7, i} = 10 \cdot dp_{4, {i - 1}} + 7 \cdot cnt_{4, {i - 1}} + 10 \cdot dp_{7, {i - 1}} + 7 \cdot cnt_{7, {i - 1}}\)
\(cnt_{7, i} = cnt_{4, {i - 1}} + cnt_{7, {i - 1}}\)
Початково для довжини 0 використовуватимемо такі значення: \(ans_0\) = 0, \(dp_{4, 0}\) = 0, \(dp_{7, 0}\) = 0, \(cnt_{4, 0}\) = 0, \(cnt_{7, 0}\) = 1. Ідейно ми пробуємо дописати одну цифру справа до числа. Такий розв’язок працюватиме за \(O(n)\), що занадто повільно.
Запишемо вектор \((ans_i, dp_{4, i}, cnt_{4, i}, dp_{7, i}, cnt_{7, i})\). Зробимо перехід від довжини \(i\) до довжини \(i + 1\) за допомогою множення матриці.
\[\begin{gathered} \begin{pmatrix} ans_i \\ dp_{4, i} \\ cnt_{4, i} \\ dp_{7, i} \\ cnt_{7, i} \end{pmatrix} = \begin{pmatrix} 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 10 & 4 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 10 & 7 & 10 & 7 \\ 0 & 0 & 1 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} ans_{i - 1} \\ dp_{4, {i - 1}} \\ cnt_{4, {i - 1}} \\ dp_{7, {i - 1}} \\ cnt_{7, {i - 1}} \end{pmatrix}\end{gathered}\]
Тепер нам треба помножити зліва дану матрицю \(n + 1\) раз на початковий вектор. Тоді відповідь буде знаходитися в першій комірці нашого вектора. Оскільки множення матриць є асоціативною операцією, то можна знайти матрицю в степені \(n + 1\) та помножити її на початковий вектор. Це можна зробити двійковим піднесенням до степеня. Зауважимо, що всі операції множення та додавання потрібно виконувати за модулем \(10^9 + 7\). Загальна складність \(O(5^3 \cdot log(n))\).
Якщо рядок складається лише з цифр 4 або лише з цифр 7, то відповідь -1. Можна довести, що якщо підрядки довжини \(n\) та довжини \(n - 1\) є паліндромами, то це можливо тоді і тільки тоді коли рядок складається лише з 4 або лише з 7, а тому, якщо рядок не є паліндромом, то відповідь \(n\), інакше відповідь \(n - 1\).
Зробимо операції для кожного рядка так, що в першому стовпці всі значення були рівні 4. Після цього для кожного рядка потрібно або більше не робити операції або зробити 3 операції — перетворити на 7.
Назвемо рядок синім, якщо робимо 0 операцій, і жовтим, якщо 3.
Тепер дивимось на стовпці:
Якщо в стовпці всі значення однакові, зробимо їх рівними 4. Після цього нам байдуже чи робимо ще 3 операції, чи ні.
Якщо в стовпці 2 різних значення і можна зробити операції до цього стовпця так, щоб ці значення були 1 та 7. Тоді всі рядки з 1 повинні бути жовтими, 7 — синіми.
Якщо в стовпці 2 різних значення і можна зробити операції до цього стовпця так, щоб ці значення були 4 та 7. Тоді можливо 2 випадки: залишаємо 4, 7 — тоді всі 7 повинні бути синіми, або робимо зі значень 1 та 4 — тоді всі 1 повинні бути жовтими. Тобто ми можемо розбити всі рядки на 2 групи та, або всі елементи першої групи повинні бути жовтими, або всі елементи другої групи повинні бути синіми. Сформулюємо це так, що, якщо є хоча б один жовтий елемент другої групи, то всі елементи першої групи жовті. І якщо є хоча б один синій елемент першої групи, то всі елементи другої групи сині.
Якщо в стовпці 3 різних значення і можна зробити операції до цього стовпця так, щоб ці значення були 1, 4 та 7. Тоді всі рядки з 1 повинні бути жовтими, 7 — синіми.
В будь-якому іншому варіанті відповідь не існує.
Знайдемо всі значення рядків, які можливо знайти використовуючи ці умови. Якщо немає суперечностей, коли один рядок повинен бути одночасно і синім і жовтим, то відповідь існує. Також це можливо сформулювати як задачу 2-sat.
Перший масив побудуємо так, щоб в ньому було \(n\) щасливих чисел довжиною 10. Це можна зробити перебравши всі маски довжини 10 і замінювати біти зі значенням 0 на 4, а зі значенням 1 на 7. Таких масок є \(2^{10}\) > 747.
Другий масив побудуємо так, щоб в ньому було \(m\) перших щасливих чисел, помножених на \(10^{10}\). В нас є 2 числа довжини 1, 4 довжини 2, 8 довжини 3 і так далі. Отже, нам досить мати 9 цифр, щоб скласти 747 чисел. Тоді найбільше число займатиме не більше ніж 19 цифр і буде меншим ніж \(10^{19}\) < \(2^{64}\).
Нехай кількість цифр 4 у рядку є парною, а кількість цифр 7 -
непарною. Тоді, якщо усі цифри 4 у рядку стоять послідовно, то відповідь
NO — ми не зможемо видалити усі цифри 4, адже останні дві 4
точно будуть сусідніми.
Інакше відповідь YES — розглянемо кожну групу цифр 4
підряд, видалимо всі крім одного або двох залежно від парності. Після
цього повидаляємо всі 4 беручи пари з різних груп. Залишились лише
символи 7 — видалимо їх всіх крім одного.
Якщо ж кількість цифр 4 у рядку є непарною, а кількість цифр 7 - парною, то розмірковуємо за аналогією.
Припустимо, що Зеник знає дорогу \((u, v)\) таку, що
Відстань між барами \(u\) та \(v\) для Марічки не менша 3.
Зеник може добратись до бару \(u\) або до бару \(v\) швидше ніж Марічка.
Тоді Зеник приходить в один з цих барів та кожного разу, коли Марічка опиняється в сусідньому з ним барі, переходить по цій дорозі. Так він зможе постійно тікати від Марічки.
Інакше Марічка завжди зможе наздогнати Зеника. Якщо ми розглянемо дерево Марічки, то Зеник зможе лише не може покинути те саме піддерево — він зможе перестрибнути вершину Марічки, але Марічка наступним ходом зможе також попасти в цю вершину, тож це не має сенсу. Тому Марічка може просто іти в напрямку Зеника.
Зенику ж вигідно знайти таку вершину, що до неї йому ближче, ніж Марічці, по дорозі до цієї вершини Зеник теж заходить лише в вершини, які йому ближче, та відстань від початкової позиції Марічки до цієї вершини максимальна — це і буде відповідь. Тож Зеник перейде в цю вершину і буде чекати там Марічку.