В даній задачі потрібно було перевірити чи 47 є в числі. Для зручності можна зчитати це число як рядок. Тепер нам потрібно перевірити входження підрядка 47 в нього, що можна зробити циклом або вбудованими функціями мови програмування. Також цю перевірку можна було зробити без використання рядків просто перевіряючи останні дві цифри і після цього видаляти останню цифру.
B. Функцiя з простим дiльником
Якщо \(n\) парне тоді \(f^k(n) = n + 2 * k\). А якщо \(n\) непарне то в нього \(pr(n)\) теж непарне, отже \(f(n) = n + pr(n)\) — парне. Тому розв’язок потрібно шукати тільки для парних \(m\). Тобто для непарних відповідь -1. Тепер для парного потрібно визначити розв’язок, такми може бути \(n = m - 2 * k\) — парне, так як \(m\) парне. \(f^k(n) = n + 2 * k = m - 2 * k + 2 * k = m\). Проте це число має бути більше за 1. Також потрібно довести що якщо це число менше за 2, тоді розв’язку взагалі не існує. Тобто \(m < 2 * k + 1\). Ми знаємо що найменше просте число на яке ділиться \(n\) є хоча б 2 або більше, тому \(f^k(n) >= n + 2 * k\), отже \(n + 2 * k <= m < 2 * k + 1\) що не може виконуватись для \(n > 1\).
Підвісимо дерево за довільну вершину. Розглянемо певне піддерево вершини \(v\), зі зрозумілих причин із піддерева не може іти більше одного шляху до батька вершини \(v\). Якщо б таке було б, то вершина \(v\) була б покрита двома шляхами, що суперечить умові. Нехай \(b\) та \(r\) — це кількість вершин синього та червоного кольорів в піддереві вершини \(v\). Можливо лише 3 випадки \(b = r\), \(b = r + 1\) та \(r = b + 1\), бо інакше ті вершини що не спарували в шляхи мають шлях що проходить через вершину \(v\), якщо таких вершин більше ніж 2 тоді це погано.
Будемо виконувати такий процес: паруємо шляхи у нижчих піддеревах вершини \(v\) тоді до цієї вершини приходять якісь шляхи, можливо шлях що починається у вершині \(v\). Тоді таких шляхів має бути не більше двох і вони мають бути різних кольорів. Це можна зробити наприклад рекурсивним пошуком в глибину який повертатиме колір шляху що іде з піддерева.
Розглянемо простішу задачу, це знайти мінімальну суму чисел \(a_i \oplus x\). Оскільки ксор змінює біти незалежно, то сума рівна \(\sum_{bit=0}^{30} (2^bit * \sum{i=1}^n [bit in a_i] \oplus [bit in x]\). Якщо ми порахуємо \(cnt_0[bit]\) та \(cnt_1[bit]\) — кількість чисел що мають біт \(bit\) виключений та включений відповідно. Тоді сума перетворюється в таку: \(\sum_{bit=0}^{30} (2^bit * cnt_{![bit in x]}[bit])\). Для того аби її мінімізувати нам необхідно вибрати чи буде ключений чи виключений біт в \(x\), виберемо такий аби в нас була \(cnt[bit]\) якомога менша:
\(cnt_0[bit] \ge cnt_1[bit]\) — тоді біт буде виключений,
\(cnt_0[bit] < cnt_1[bit]\) — тоді біт буде включений.
Таким чином перебравши біти ми можемо визначити за \(O(logA)\) мінімальну суму.
Тепер повернемось до нашої задачі, для неї спробуємо вимкнути найстарший біт (серед перших 30 бітів) числа \(x\) і подивимось чи по усіх інших бітах ми можемо отримати суму меншу за \(s\), тобто по молодших бітах будемо мінімізовувати суму. Зрозуміло що якщо ми змогли отримати суму меншу за \(s\) то нам не вигідно включати цей старший біт числа \(x\).
Отже ми вміємо визначати найстарший біт числа \(x\). Визначивши його ми можемо аналогічно визначити другий старший біт і так далі.
Очевидно, що Зенику варто піти або в супермаркет, або відвідати магазин кожного типу окремо, оскільки якщо Зеник відвідав супермаркет, то йому вже не потрібно йти ще в якийсь магазин. Отже задача зводиться до двох випадків: коли Зеник йде в супермаркет, або коли Зеник купує продукти у всіх магазинах окремо.
Розгляньмо випадок, коли Зеник йде до супермаркету. Оскільки ми хочемо мінімізувати відстань до координати 0, то варто вибрати супермаркет який найближчий до цієї координати. Тому нам потрібно вибрати такий супермаркет, в якого мінімальне значення \(|d_i|\). Це можна зробити за \(O(n)\).
Тепер розгляньмо випадок коли Зеник купує всі продукти в різних магазинах. Як порахувати відповідь коли ми маємо лише по одному магазину кожного типу? Знайдімо найправішу координату і найлівішу. Позначимо координати хлібного, м’ясного та сирного магазинів як \(a\), \(b\) та \(c\) відповідно. Легко зрозуміти що координата найлівішої точки це \(l = \min (a, b, c, 0)\), а найправішої \(r = \max (0, a, b, c)\). Щоб оптимально обійти їх нам потрібно спочатку піти в один бік, повернутися додому, піти в інший бік і знову повернутися додому. Отже відповідь для випадку магазинів різних типів буде \((|l| + r) \cdot 2\).
Що робити якщо магазинів багато? Ми можемо перебрати магазин кожного типу в який піде Зеник і таким чином знайти відповідь. Такий алгоритм праюватиме за \(O(n^3)\), що занадто повільно. Цей алгоритм легко оптимізувати.
Розглянемо магазини одного типу. Якщо є якісь два магазини з додатніми координатами, то нам ніколи не буде вигідно йти до магазину який знаходиться далі від нас, тому його не потрбіно перебирати. Аналогічні міркування справджуються і для магазинів з від’ємними координатами. В результаті, для кожного типу магазинів нас цікавлять лише два магазини: найближчий до нас з додатньою координатою і найближчий з від’ємною координатою. Після того як ми викинемо решту магазинів, всього їх залишиться не більше ніж 6: по 2 кожного типу. Тепер для кожного типу магазинів можемо перебрати до якого підемо, тому що різних таких комбінацій буде не більше ніж \(2 \cdot 2 \cdot 2 = 2^3 = 8\).
Відповідь на задачу це мінімум з двох випадків: або йдемо до найближчого супермаркета, або до кожного типу магазинів окремо.
Загальна складність алгоритму \(O(n + 2^3)\).
F. Play Metal Louder Than Hell
Якщо \(a_i >= n\) і остання прослухана пісня буде \(pos\), тоді масив пісень \(S_i\) потрібно перетворити у такий: \(S_{pos}, S_{pos - 1}, ..., S_0, S_{n-1}, ... S_{pos + 1}\). Тобто нам треба розвернути якийсь префікс, суфікс і їх обєднати.
Якщо \(a_i + song >= n\), тобто у випадку коли ми перестрибнемо у списку пісень з останньої на першу. Тоді новий масив буде мати вигляд \(S_{pos}, S_{pos - 1}, ..., S_0, S_{n - 1}, ... S_{song}, S_{pos + 1}, ..., S_{song - 1}\). Тобто у нас є три кусочки і деякі з них треба розвернути та змерджити.
Якщо \(a_i + song < n\) тоді масив буде мати вигляд \(S_{pos}, S_{pos - 1}, ..., S_{song}, S_0, ..., S_{song - 1}, S_{pos + 1}, ..., S_{n - 1}\). Тут теж є проміжки які треба розвертати.
Отже постає завдання розвертати певні проміжки і переставляти їх місцями. Для цього використаємо декартове дерево, тепер треба вміти його розвертати. Для того аби розвертати його треба додатково змінну яка памятатиме чи треба розвернути піддерево, це буде реалізовуватись подібно до пушів у дереві відрізків.
Або ми можемо побудувати два декартових дерева, одне пряме, а інше розвернене. Тоді коли нам потрібно розвернути проміжок це означає що нам необхідно поміняти проміжок між цими деревами.
Зауважимо, що нам не вигідно розрізати десь між однаковими символами, тобто нам вигідно обєднувати відрізки з однаковими значеннями. Знайдемо для пари \(A\), \(B\) розрізи де є число \(А\) зліва та \(В\) справа. Для такої пари і всіх розрізах запамятаємо \((x, y)\), де \(x\) — кількість \(A\) зліва від перерізу, а \(y\) — кількість \(B\) справа. Тепер нам потрібно знайти максимальний скалярний добуток з цих точок, тобто максимальне \(x_i \cdot x_j + y_i \cdot y_j\). Посортуємо точки, тобто за зростанням \(x\), а для однакових за зростанням \(y\). Будемо тримати масив точок в порядку зростання \(x\) та спадання \(y\). Тепер розглядаємо нову точку, вона буде мати \(x\) >= за усі значення \(x\) серед точок в масиві, тоді видаляємо усі точки що мають \(y\) менший або рівний. Точки що видаляємо потрібно спробувати їх зкомбінувати з точкою що їх видаляє. А після цього процесу порахуємо скалярний добуток для кожної пари точок з цього порахованого масиву.