В задачі потрібно просто зробити те, що сказано в умові. Для спрощення написання коду, можна не будувати нову стрічку, а одразу рахувати суму.
Цікавий факт: крім банківських карток алгоритм Луна використовується для IMEI та номерів соціального страхування в Канаді.
Будемо перебирати \(p_i\) та ділити
\(n\) на \(p_i\), поки \(n\) ділиться на \(p_i\) без остачі. Якщо після цих операцій
ми отримали одиницю — відповідь YES, інакше
NO.
Цікавий факт: на квітень 2023, найбільше відоме людству просте число \(2^{82589933}-1\). Це число має \(24862048\) цифр.
Задачу можна розв’язувати незалежно по \(x\) і \(y\). Для однієї із координат відповіддю завжди буде одна із сусідніх пар в посортованому масиві. Достатньо вибрати із двох відповідей меншу. Під час сортування треба бути обережним, щоб також мінімізувати \(i+j\). Для цього слід сортувати не лише по координаті, а й по номеру.
Цікавий факт: Точка-У здатна гатити орків на відстані до 120км.
Нескладно помітити, що якщо \(b=c\), ми можемо досягти Помаранчевої Революції зробивши \(b\) червоно-голубих зустрічей.
Подивимося уважно, що стається із \((b-c)\) після зустрічі оранжевого і голубого:
\[\begin{gathered} a' = a - 1 \\ b' = b - 1 \\ c' = c + 1 + 1 + k \\ b' - c' = (b - c) - \textbf{(k+3)} \end{gathered}\]
Аналогічно після зустрічі оранжевого і червоного
\[\begin{gathered} a' = a - 1 \\ b' = b + 1 + 1 + k \\ c' = c - 1 \\ b' - c' = (b - c) + \textbf{(k+3)} \end{gathered}\]
Бачимо, що різниця не міняє остачі від ділення на \((k+3)\). Отже якщо \((b-c)\) не ділиться на \((k+3)\) націло, то отримати \(b=c\) неможливо і відповідь
NO. Інакше відповідь YES. Для знаходження
порядку зустрічей застосуємо жадібний підхід.
Цікавий факт: Вважають, що давні єгиптяни одними з перших бджолярів в світі.
Розгленемо будь-яку сторону квадрата. Припустимо ми зафіксували кутики. Можливо показати, що якщо обидва кутики є випуклими, то сторона буде валідною тоді і тільки тоді, якщо кількість частинок 5-го типу є на один більшою ніж 6-го. Аналогічно, якщо обидва кутики є впуклими, то кількість частинок 6-го типу має бути на один більшою за кількість частинок 5-го. Якщо ж кутики різного типу, то кількість частинок 5-го і 6-го типів повинна бути однаковою. Кількість частинок 7-го типу може бути будь-якою.
Переберемо парність \(n\) і кутики. Для кожної сторони виставимо обов’язкові частинки - можливо одну з 5-го або 6-го типу і можливо одну 7-го, щоб була потрібна парність. Після цього можна добирати будь-яку кількість пар - 5 і 6 або дві 7.
Тож ми можемо перебрати усі можливо рамки розміру 3х3 та 4х4 і максимізувати кількість можливих пар. Тоді щоб збільшити \(n\) на 2 потрібно використати 4 пари. Перебирати можна кутики з виставленням необхідних частинок. Або можна перебрати усі \(2^8\) та \(2^{12}\) варіантів з’єднань.
Код розв’язку з перебором кутиків
Код розв’язку з перебором варіантів
Цікавий факт: Вважають, що аматорським малюванням Казимир Малевич почав займатися в Конотопі.
Програшні позиції — многокутники, для яких відстань від лівого краю до правого рівна відстані від нижнього до верхнього \(max(x_i) - min(x_i) = max(y_i) - min(y_i)\) (назвемо такі многокутники обрізаними квадратами), і з них за одну операцію не можна відрізати многокутник з такими ж характеристиками. Можна довести, що з обрізаного прямокутника завжди можна за одну операцію вирізати обрізаний квадрат, з якого в свою чергу за одну операцію не можна вирізати обрізаний квадрат, тільки прямокутник: \(max(x_i) - min(x_i) \ne max(y_i) - min(y_i)\). Для цього підійде обрізаний квадрат найменшого розміру.
Імплементація: йдемо з лівого краю многокутника до правого і підтримуємо найвищу і найнижчу точку, таким чином ми знаємо: \(min(x_i)\) — лівий край, \(max(y_i)\) — координата \(y\) найвищої розглянутої точки, \(min(y_i)\) — координата \(y\) найнижчої розглянутої точки, \(max(x_i)\) — поточна \(x\) координата. Якщо в якийсь момент до досягнення правого краю рівність буде виконуватись, то виграє перший гравець. Аналогічний прохід треба зробити зліва направо, зверху вниз і знизу вверх. Якщо рівність ніколи не виконається — виграє другий гравець. Складність \(O(dx + dy + n)\).
Цікавий факт: найбільший спечений пляцок важив 10540 кг.
Проходимо по масиву часткових різниць зліва направо і підтримуємо кількість відкритих проміжків висоти 1 (ціна створення 1) та відкриті проміжки висоти \(x\) (ціна створення 1, але їх можна розбити на \(x\) одиничних проміжків за певну ціну). Проміжків висоти 1 в нас завжди буде менше, ніж \(х\); якщо більше, то поміняємо їх на один проміжок \(х\) з ціною розбиття 0. Маємо два випадки:
Часткова різниця \(a\) додатня. Поки \(a \ge x\) додаємо проміжок \(x\) з ціною \(x-1\) та 1 до відповіді. Залишилось \(a < x\), треба або відкрити \(a\) проміжків висоти 1 або відкрити 1 проміжок висоти \(x\) і закрити \(x-a\) проміжків висоти 1. Якщо кількість відкритих проміжків висоти 1 не менше \(x-a\): тоді закриваємо \(x-a\) одиничних і додаємо один проміжок висоти \(x\) з ціною \(a-1\), +1 до відповіді. Інакше, збільшуємо кількість відкритих одиничних відрізків на \(a\) і якщо вигідніше розбити найдешевший (нехай його ціна \(p\)) \(x\) проміжок для об’єднання \(p + 1 < x\), то розбиваємо його і додаємо до відповіді \(p+1\) і формуємо новий \(x\) проміжок з ціною \(a-1\), інакше просто додаємо до відповіді \(a\).
Часткова різниця \(-a\) від’ємна. Аналогічно поки \(a \ge x\) закриваємо найдорожчий проміжок висоти \(x\). Тепер ми можемо або закрити \(a\) проміжків висоти 1 і нічого не платити, або закрити один \(x\) і відкрити \(x-a\) 1 і заплатити \(x-a\). Якщо в нас є \(a\) проміжків висоти 1, то закриваємо їх і міняємо проміжок висоти \(x\) на інший з ціною \(x-a\) якщо це вигідно (вона менша). Якщо немає, тоді можливо вигідно поміняти найдешевший (нехай його ціна \(p\)) \(x\) на проміжки висоти 1. Тоді в першому випадку ми платимо \(p\), в другому \(x-a\). Тобто якщо \(p < x - a\), то заплатимо \(p\), закриємо цей проміжок висоти \(x\) і можемо змінити найдорожчий відрізок \(x\) на інший з ціною \(x-a\); інакше заплатимо \(x-a\) і видалимо найдорожчий відрізок \(x\) (треба видалити відрізок ціною \(x-a\) і можна замінити найдорожчий відрізок \(x\) на інший з ціною \(x-a\) => просто видалимо найдорожчий відрізок \(x\)).
Складність \(O(n \cdot log(n))\).
Цікавий факт: Бар Шона в Ірландії працює безперервно ще з середньовіччя.