Якщо число \(n - 1\) не є щасливим, то виведемо його і \(1\). Інакше — \(2\) та \(n - 2\).
Знайдемо першу четвірку у записі заданого числа, та змінимо її на сімку. Якщо ж число не містить жодної четвірки, то потрібно змінити останню сімку на четвірку.
Порахуємо вклад кожної цифри до відповіді. Цифра на позиції \(i\) додасть \(i \cdot s_i \cdot \sum_{j = 1}^{n - i} 10^j\). Тут множник \(i\) відповідає за кількість способів вибрати ліву межу, щоб \(i\)-та цифра була у підрядку. А сума відповідає за кількість способів вибрати праву межу. Варто зауважити, що зміна правої межі змінює розряд \(i\)-тої цифри. Рахувати відповідь легше з права на ліво, підтримуючи значення суми.
Для кожної цифри порахуємо на скількох кубиках вона повинна зустрічатися. Для цифри \(d > 0\) це буде довжина максимального числа, що складається лише з таких цифр, і не перевищує \(n\). Для \(d = 0\) нам завжди треба принаймні \(len - 1\) кубик (наприклад, щоб викласти число \(1\) з \(len - 1\) ведучим нулем).
Розглянемо випадок \(n = 100\). Його не можна розв’язати за допомогою трьох кубиків, адже для викладення чисел \(001, 002, ..., 008\) потрібно, щоб принаймні на двох кубиках була цифра \(0\), а третій містив всі цифри від \(1\) до \(8\), що неможливо.
Тому варто врахувати, що при \(n > 9\), треба принаймні два кубики, крім тих \(len - 1\) на яких є цифра \(0\). Можна показати що існує набір кубиків, який використовує саме таку кількість кожної цифри і ним можна подати всі числа від \(1\) до \(n\).
Розглянемо число \(L = 10^{17} - 1\). Воно складається лише з цифр \(9\), тому зрозуміло, що воно утворюватиме хорошу пару з числами без цифри \(9\) (і лише з ними). Також розглянемо проміжок [\(10^{17}\), \(2 * 10^{17} - 1\)]. Зрозуміло, що жодна пара чисел з цього проміжку не є хорошою, адже всі вони містять цифру \(1\). Чисел без цифри \(9\) на проміжку [\(10^{17}\), \(2 * 10^{17} - 1\)] є рівно \(9^{17} > 10^{16}\), тому відповідь завжди існуватиме. Причому достатньо взяти \(R\) як \(x\)-те число без жодної дев’ятки у десятковому записі. Неважко зрозуміти, що це \(10^{17}\) + (\(x - 1\)) у системі числення \(9\).
Випадок \(n = 1\) тривіальний, надалі \(n > 1\). Розглянемо таку стратегію Зеника: кожен раз, окрім можливо останнього він ставить +. Щоб Марічка перемогла, їй потрібно, щоб незалежно від останнього ходу Зеника мати можливість отримати якусь конкретну остачу при діленні на \(k\). Це можливо, лише якщо множини \(\{4 + 4, 4 + 7, 7 + 7\}\) та \(\{4 * 4, 4 * 7, 7 * 7\}\) мають якийсь спільний елемент за модулем \(k\). При \(k > 49 - 4 = 45\) це неможливо, тому Зеник переможе у таких випадках.
Якщо \(k \le 45\), розв’язуватимемо задачу за допомогою динамічного програмування \(canWin[m][s][p]\) - чи може Марічка перемогти, якщо їй залишилося поставити \(m\) символів, поточна сума рівна \(s\), а добуток після останнього знаку множення \(p\). Тоді переберемо варіанти наступного ходу Марічки та Зеника. Складність такої динаміки \(O(nk^2)\).
Також можна помітити, що якщо для якоїсь пари (\(n\), \(k\)) Зеник виграє для всіх \(r\), то він виграватиме і для всіх (\(m\), \(k\)), де \(m > n\). Можна показати, що якщо \(k > 7\), то таке \(n\) завжди існує, і є доволі невеликим. Тому можна знайти всі нетривіальні розв’язки.
Випадок, коли \(n\) є непарним числом тривіальний. Розглянемо лише випадок парних \(n\). Стан гри характеризується таким набором чисел:
кількість компонент, де в обох частках непарна кількість вершин (назвемо їх типом 1)
кількість компонент, де в обох частках парна кількість вершин (тип 2)
кількість компонент, де в одній частці парна кількість вершин, а у іншій - непарна (тип 3а)
кількість ізольованих вершин (тип 3б)
кількість вільних ребер, які можна провести не зменшуючи кількість компонент зв’язності
З парності \(n\) випливає, що кількість вершин типу 3 (3а + 3б) є парним числом. Можна помітити, що важлива лише парність кількості вільних ребер.
Є два типи ходів, які не змінюють парність кількості вільних ребер:
З’єднання компоненти типу 1 і компоненти типу 3
З’єднання двох компонент типу 3, так щоб вийшла компонента типу 1
Можна помітити, що обидва ці ходи (і лише вони) зміннюють парність компонент типу 1, тому кожен хід змінює або парність кількості вільних ребер, або парність кількості компонент типу 1.
Також можна помітити, що будь-які операції з компонентами типу 2 не впливають на стан гри (окрім, можливо операцій з вільним ребром, але їх ми вже винесли окремо).
Припустимо, немає компонент типу 3а, а значить кількість компонент типу 3б парна. Твердження: якщо є вільне ребро, то Марічка виграє якщо кількість компонент типу 3б (cnt3b) ділиться на 4, а якщо немає — то коли не ділиться. Доведести це можна індукцією по cnt3b.
Тепер легко бачити, що якщо є рівно дві компоненти 3а, то Марічка завжди переможе, адже вона може з’єднати їх двома способами, один з них змінить кількість вільних ребер, а інший кількість компонент типу 1. Відповідно вона може вибрати свій хід таким чином, аби перейти у програшний для Зеника стан (відповідно до поточної кількості cnt3b).
З міркувань парності, якщо є рівно одна компонента типу 3а, то повинна бути принаймні ще одна компонента типу 3б, і в цьому випадку аналогічно Марічка виграє.
Тепер, якщо є більше, аніж дві компоненти типу 3a, то той хто змушений робити ходи пов’язані з ними - програє, адже за один хід не можна змінити кількість цих компонент більш, аніж на 2, а і cnt3a = 1, i cnt3a = 2 - виграшні, тому у ці стани ходити не можна. Тоді можна помітити, що виграшні стани тут — ті і лише ті, де парність кількості вільних ребер, і компонент типу 1 різна.