Зеник спочатку задонатив \(b\) гривень, а потім \(k\) разів по \(x\) гривень. Тобто, можна записати це формулою \(b + k \cdot x\). Отже, в задачі було достатньо запрограмувати таку формулу.
Як альтернативний розв’язок можна було \(k\) разів додати \(x\) до відповіді за допомогою циклу.
В даній задачі потрібно було перевірити чи 47 є в числі.
Для зручності можна зчитати це число як рядок. Тепер нам потрібно
перевірити входження підрядка 47 в нього, що можна зробити
циклом або вбудованими функціями мови програмування. Також цю перевірку
можна було зробити без використання рядків.
Спочатку навчимось перевіряти чи Петро зможе дійти до зупинки не пізніше ніж до неї приїде трамвай. Для обрахунку часу потрібно поділити відстань на швидкість. Використовуючи цю формулу знайдемо витрачений час трамваю та час Петра. З обмежень задачі можна помітити, що отримані часи будуть цілими. Отже для точності розв’язку будемо обраховувати їх діленням націло.
Для кожної зупинки ми дізнаємось чи Петро може до неї дійти і встигнути на трамвай. Якщо він зможе дійти до двох зупинок, тоді необхідно додатково перевірити до якої зупинки йому ближче. Він піде до першої зупинки, якщо до неї відстань не більша ніж до другої. У випадку якщо він зможе дійти лише до однієї зупинки, то нам потрібно визначити до якої саме. Якщо ж не може дійти до жодної тоді він не встигне на тренування.
Порахуємо кількість різних PIN-кодів. Ми знаємо що кожну цифру можна вибирати двома способами. Також обираємо їх незалежно одну від одної. Тому відповідь це добуток кількості варіантів для кожної з цифр, що в даному випадку дорівнює \(2^n\).
Якщо перебрати усі можливі пари PIN-кодів і виконати для них відповідну операцію, то необхідно порахувати скільки раз ми отримали рядок \(x\). Такий розв’язок пройде приклади та перший блок тестів.
Якщо ми переберемо тільки перший PIN-код, то, згідно умови, можемо однозначно знайти другий. Це можна зробити таким чином: якщо в рядку \(x\) на \(i\)-тій позиції цифра 0, то в другому PIN-коді ставимо таку ж цифру як і в першому. Якщо ж на \(i\)-тій позиції 1, то змінимо цифру з першого PIN-коду на протилежну. Отже, ми можемо згенерувати всі PIN-коди довжини \(n\) і кожен з них буде першим PIN-кодом рівно в одній парі, що нам підходить. Такий розв’язок пройде другий блок тестів.
Оскільки кожен PIN-код утворить одну пару, що нам підходить, а кількість PIN-кодів \(2^n\), то й відповідь до задачі \(2^n\).
Тому для повного розв’язку задачі достатньо вивести \(2^n\).
Перший блок тестів можна розвязувати такими способами:
Для кожного дня порахуємо кількість регіонів з міст під контролем 47-ляндії. Для цього будемо ітеруватись по містах. Якщо ми зустрічаємо місто під контролем 47-ляндії, яке ми ще не відвідували, то обійдемо усі досяжні з нього міста підконтрольні 47-ляндії. Тепер усі ці міста є відвіданими і більше цей регіон не буде врахований. Таким чином після кожного дня ми можемо порахувати відповідь. Складність такого алгоритму буде рівна \(O(q \cdot n)\).
Для кожного міста, будемо пам’ятати значення \(cnt_v\) — скільки в неї є сусідініх міст під контролем 47-ляндії. Тоді коли місто перестає бути підконтрольним 47-ляндії то замість одного регіону, ми отримуємо \(cnt_v\) регіонів. Кожне сусіднє місто буде в своєму окремому регіоні. І навпаки якщо місто стає підконтрольним 47-ляндії, то \(cnt_v\) регіонів об’єднаються в один. При зміні стану міста оновимо значення \(cnt\) для кожного сусіднього міста. Такий розв’язок має складність рівну \(O(q \cdot n)\).
Розглянемо країну як структуру дерево. Візьмемо одне з міст як корінь цього дерева, кожна вершина в цьому дереві, крім кореня, має батька. Тепер замість \(cnt_v\), пам’ятатимемо \(son_v\) — кількість синів даної вершини під контролем 47-ляндії. Для того аби визначити \(cnt_v\) нам достатньо перевірити чи батько даної вершини належить 47-ляндії. А решта сусідніх міст є синами поточної вершини, ми знаємо скільки серед них належать 47-ляднії — \(son_v\). У випадку коли батько належить 47-ляндії, тоді \(cnt_v = son_v + 1\), у іншому варіанті \(cnt_v = son_v\). Тепер якщо вершина змінює свій стан тоді ми маємо оновити значення \(son\) для її батька, якщо звісно він існує. Тоді кожна така операція працює за \(O(1)\), а сумарна складність запитів рівна \(O(q)\). Також необхідно порахувати початкові значення \(son_v\), що ми можемо зробити за \(O(n)\) звичайним пошуком вглиб, або певними формулами.
Код розв’язку C++ \(O(n \cdot q)\)
Код розв’язку C++ \(O(n \cdot q)\)
Переберемо всі підрядки рядка \(s\). Для кожного такого підрядка переберемо всі підрядки \(t\) і порівняємо їх на рівність. Такий розв’язок працюватиме за \(O(|s|^2 \cdot |t|^2 \cdot cmp)\), де cmp — час порівняння двох підрядків, що в найгіршому випадку рівне \(O(|t|)\). Цей розв’язок пройде перший блок тестів.
Розглянемо швидший розв’язок. Переберемо всі підрядки рядка \(t\) і запишемо їх в мультимножину. Тепер для кожного підрядка \(s\), замість того щоб перебирати підрядок в \(t\), просто подивимося скільки таких підрядків є в нашій мультимножині. Такий розв’язок працюватиме за \(O((|t|^2 + |s|^2) \cdot log(|t|^2) \cdot cmp)\), де cmp — час порівняння двох підрядків, що в найгіршому випадку рівне \(O(|t|)\). Цей розв’язок пройде два перші блоки тестів.
Тепер розглянемо розв’язок, який розв’яже задачу з повними обмеженнями. Нехай ми знайшли підрядки з рядків \(s\) та \(t\) які співпадають. Очевидно, що всі їхні відповідні рядки також співпадають. Якщо довжина підрядків які співпадають рівна \(n\), то можна до відповіді додати \(\frac{n \cdot (n + 1)}{2}\) і вже не розглядати їх підрядки. Тоді якщо ми співставимо \(s\) і \(t\) у всіх можливих позиціях і знайдемо проміжки де рядки співпадають, то зможемо легко порахувати відповідь.
Наприклад якщо \(s\) = aabcabb, а \(t\) = abba, то один з варіантів співставлення виглядатиме так:
Тут є підрядки довжин 2 та 1, тому до відповіді треба додати \(\frac{2 \cdot 3}{2} + \frac{1 \cdot 2}{2} = 3 + 1 = 4\). Зауважимо, що рядок \(t\) може виходити за межі \(s\), наприклад так:
Оскільки в нас є \(|s| + |t| - 1\) позиція для того щоб їх співставити, то загальна складність такого алгоритму буде \(O((|s| + |t|) \cdot |t|)\).
Розглянемо перший блок тестів, у ньому нам потрібно заповнити прямокутник розміру \(1 \times (n - b[i])\), тому навчимось розвязувати задачу заповнення коли в нас є прямокутник розміру \(1 \times m\). Для цього розглянемо найправішу плиточку, що буде стояти в цьому прямокутнику. Вона може бути розміру 1 або розміру 2. Поставивши одну з цих плиточок в нас залишиться прямокутник розміру \(1 \times (m - 1)\) або \(1 \times (m - 2)\) відповідно. Визначимо \(f[m]\), як відповідь на задачу для прямокутника розміру \(1 \times m\). Тоді можна записати таке рівняння: \(f[m] = f[m - 1] + f[m - 2]\), а значення \(f[0]\) і \(f[1]\) рівні 1. Цей масив можна обрахувати звичайним циклом.
Перейдемо до другого блоку, нам потрібно заповнити прямокутник розміру \(2 \times (n - a[i])\), тобто потрібно вміти розвязувати задачу заповнення для прямокутника \(2 \times m\). Для цього введемо два масиви \(g[m]\) — відповідь на задачу для прямокутника розміру \(2 \times m\), та допоміжний \(h[m]\) — відповідь на задачу для фігури зображеної нижче, зрозуміло що відповідь буде аналогічна якщо зверху буде більша кількість вільних клітинок.
Спробуємо для них написати рівняння подібно до першого блоку, для цього розглянемо як зліва будуть замощені плиточки , спочатку для \(h[m]\). Для цієї фігури є два варіанти яка плиточка знаходиться в найлівішій вільній клітинці:
Якщо ставимо плитку розміру 1, то переходимо до задачі \(g[m - 1]\), якщо ж розміру 2 то до задачі \(h[m - 1]\), тому формула \(h[m] = g[m - 1] + h[m - 1]\). Тепер розглянемо задачу \(g[m]\).
Тепер розглянемо усі можливі варіанти плиточки що буду покривати ліву нижню клітинку:
У перших двох варіантах ми переходимо до задач \(h[m]\) і \(g[m - 1]\) відповідно. Для третього варіанту:
Розглянемо варіанти плиточки для лівої верхньої клітинки.
Тобто переходимо до задач \(h[m - 1]\) і \(g[m - 2]\) відповідно. А отже кінцева формула буде такою: \(g[m] = h[m] + g[m - 1] + h[m - 1] + g[m - 2]\). Отже ми можемо ці відповіді порахувати в циклі, спочатку рахуємо \(h[m]\) потім \(g[m]\).
Зауважимо що \(g[1]\) рівне 2, бо ми можемо взяти дві плиточки розміру 1 або одну розміру 2. А \(g[0]\) рівне 1, бо ми нічого не ставимо, як і було сказано в примітках. Значення \(h[1]\) буде рівне 1, бо ми можемо поставити лише одну пличотку. Зрозуміло, що \(h[0] = 0\), бо такої фігури не існує, а отже її не можна заставити плиточками.
Повернемось до початкової задачі. Без обмежень загальності, нехай у верхньому рядку потрібно закласти \(m\) клітинок, а у нижньому на \(d\) більше.
Тепер розглянемо межу між прямокутником ширини 1 і прямокутником ширини 2. Розглянемо варіант коли там стоїть плиточка розміру 2.
У такому варіанті зліва в нас задача \(f[d - 1]\), а справа \(h[m]\) і ці задачі незалежні, тобто для кожного способу зліва можна вибрати будь-який спосіб справа, тому кількість варіантів рівна добутку цих двох величин. Зауважимо, що цей варіант можливий лише за умови \(d \geq 1\) і \(m \geq 1\), для того аби плиточка розміру два мала клітинки на які її ставитимуть.
Якщо ж на межі не було плиточки довжини 2, то в нас будуть дві незалежні задачі, одна виділена синім, а інша жовтим.
Тоді відповідно в нас є задача \(f[d]\) і \(g[m]\), аналогічно до попереднього варіанту до відповіді потрібно додати добуток цих величин. Отже, відповідь на задачу буде рівна \(g[m] \cdot f[d] + h[m] \cdot f[d - 1]\).