Якщо оцінка за предмет — 10 або більше, то вона вже є відмінною. Якщо ж оцінка — 9 або менше, то для того щоб зробити її відмінною, треба буде заплатити \(10 - p_i\) доларів. Зрозуміло, що вигідно зробити відмінними спершу всі 9, потім всі 8 і т. д.
Для кожної оцінки від 1 до 12 знайдемо кількість предметів з такою оцінкою. Оцінки 10, 11 і 12 відмінні зразу. Решту оцінок переберемо від 9 до 1. Поки залишаються гроші, будемо робити оцінки з предметів відмінними.
Для кожного символа виберемо, на яких позиціях ми будемо його залишати: на парних чи на непарних. Переберемо всі такі варіанти. Для кожного символа є по 2 варіанти, тому загалом різних комбінацій є \(2 ^ 4 = 16\). Для кожної комбінації пройдемося по рядку, залишимо відповідні символи й перевіримо, чи збігається отриманий рядок з рядком \(t\). Якщо одна з комбінацій підійде, то відповідь позитивна, інакше — негативна.
Для кожного кадета порахуємо дві величини: за яку мінімальну ціну можна виштовхати всіх кадетів ліворуч від нього — \(l_i\), і праворуч від нього — \(r_i\), відповідно.
Розглянемо кадетів зліва від \(i\)-ого, які виштовхують когось. Нехай їхні індекси — \(i_1, i_2, \ldots, i_l=i\). Тоді \(i_1\)-ий кадет виштовхує всіх на півінтервалі \(\left[1, i_1\right)\), \(i_2\)-ий виштовхує всіх на \(\left[i_1, i_2\right)\) і т. д. Нехай для деякого \(j\) \(a_{i_j} \ge a_{i_{j+1}}\). Відповідь не стане гіршою, якщо \(i_{j+1}\)-ий кадет виштовхає всіх, кого виштовхував \(i_j\)-ий, а \(i_j\) не буде виштовхувати нікого. Тому існує оптимальна відповідь, у якій \(a_{i_1} < a{i_2} < \dots < a{i_l}\).
Пройдемося по кадетах зліва направо й будемо підтримувати зростаючий стек і рахувати \(l_i\). Поки стек непорожній і останній елемент стеку не менший за поточне значення \(a_i\), «викидаємо» елемент зі стеку й перераховуємо \(l_i\). Після цього «закидаємо» \(a_i\) в стек і перераховуємо \(l_i\). \(r_i\) рахуємо аналогічно до \(l_i\).
Для того щоб порахувати відповідь, переберемо, який підвідрізок з \(k\) кадетів залишиться наприкінці. Таких варіантів буде \(n - k+1\). Для фіксованого початку підвідрізка \(i\) нам потрібно виштовхати всіх кадетів лівіше від \(i\)-ого та всіх кадетів правіше від \((i + k - 1)\)-ого, а отже відповідь для \(i\) буде рівна \(l_i + r_{i+k-1}\). Візьмемо мінімальну відповідь.
Спершу скоротимо дріб, поділивши чисельник і знаменник на їхній найбільший спільний дільник. Оскільки відношення суми червоних до суми чорних рівне \(\frac{p}{q}\), то сума червоних \(r = p \cdot x\), а сума чорних \(b = q \cdot x\), де \(x\) — ціле. Якщо додамо ці дві суми, отримаємо \((p + q) \cdot x\), а з іншого боку, сума чисел від 1 до \(n\) рівна \(\frac{n \cdot(n+1)}{2}\). А отже, нам необхідне \(n\) таке, що \(\frac{n \cdot(n+1)}{2}\) ділиться на \(p + q\).
Знайдемо таке мінімальне \(n\), для якого це виконується. Воно не є більшим за \(2\cdot(p + q)\), бо для \(n = 2\cdot(p + q)\) ця умова виконується. Отже, ми можемо визначити \(x\), а знаючи \(x\) можемо визначити \(r\) і \(b\).
Методом математичної індукції можна довести, що числами від 1 до \(n\) можна подати будь-яку суму від 0 до \(\frac{n \cdot(n+1)}{2}\), а отже можна й подати суму рівну \(r\). Для цього можна брати якомога більше число серед тих, що ми ще не взяли, і таке, щоб загальна сума не перевищила шукану суму.
Для кожної IT-компанії порахуємо найменшу відстань до всіх серверів. Для цього використаємо алгоритм пошуку вшир, але не з одного початкового сервера, а з усіх серверів цієї компанії. Для кожного сервера буде порахована мінімальна відстань до найближчого сервера цієї компанії.
Для кожного питання Зеника ми вже знаємо, за який мінімальний час з \(x_i\)-ої компанії ми можемо надіслати запит на сервер \(y_i\). Залишається перевірити, чи цей час не більший за \(t_i\).
Між двома містами \(i\) та \(j\) можна передати повідомлення, якщо відрізки \([x_i-w_i, x_i+w_i]\) та \([x_j-w_j, x_j+w_j]\) перетинаються або дотикаються. Отже, якщо розглянути такі відрізки, то нам потрібно видалити мінімальну їх кількість, щоб відрізки що залишилися не перетиналися — це рівносильно тому, щоб вибрати максимальну кількість відрізків, що не перетинаються.
Розглянемо найлівіший відрізок, який ми залишили у відповіді. Якщо існує відрізок з меншим правим кінцем, то можна взяти його до відповіді замість того, який зараз найлівіший.
Тоді задачу можна розв’язувати жадібно. Посортуємо всі відрізки за правим кінцем. Пройдемо по них та будемо брати поточний відрізок до відповіді, якщо він не перетинається з останнім з тих, що ми вже взяли.
Нехай \(len\) — сумарна довжина шляхів. Тоді розділимо шляхи на дві групи:
ті, у яких довжина більша за \(B\), таких відрізків буде не більше \(\frac{len}{B}\) — назвемо їх великими;
ті, у яких довжина менша за \(B\) — відповідно назвемо їх малими.
Для \(i\)-того великого шляху порахуємо скільки спільних вершин він має з \(j\)-тим шляхом, позначимо цю величину \(cnt_{ij}\). Для \(i\)-того великого шляху будемо пам’ятати величину, яку ми маємо додати до всіх вершин на ньому — \(add_i\). Також будемо пам’ятати суму всіх елементів цього шляху \(sum_i\). Для кожної вершини \(v\) будемо пам’ятати її поточне значення, не враховуючи оновлень великих шляхів, \(x_v\).
Тоді відповідь для \(i\)-того великого шляху буде рівна \(sum_i\) — складність \(O(1)\).
Для \(j\)-того малого шляху порахуємо суму значень \(x_v\) вершин цього шляху. Щоб знайти суму на ньому, необхідно ще врахувати ті значення, що додають великі відрізки: \(i\)-тий великий відрізок додасть \(cnt_{ij} \cdot add_i\). Складність рівна \(O(B + \frac{len}{B})\), адже потрібно пройтися по всіх вершинах шляху (не більше ніж \(B\)) і по кожному великому шляху, а великих шляхів не більше ніж \(\frac{len}{B}\).
Тепер нам потрібно порахувати значення \(cnt_{ij}\) і вміти підтримувати параметри \(x_v\) i \(sum_i\).
Для \(i\)-того великого шляху позначимо всі його вершини, тоді переберемо \(j\)-тий шлях і проітеруємося по його вершинах, і якщо вершина помічена, тоді виконаємо \(cnt_{ij} := cnt_{ij} + 1\).
Якщо приходить \(+ val\) до \(j\)-того шляху тоді для \(i\)-того великого шляху зробимо \(sum_i := sum_i + cnt_{ij} \cdot val\). Якщо \(i\)-ий шлях великий, тоді нам треба ще оновити \(add_i := add_i + val\). Якщо ж малий, тоді потрібно пройтися по всіх його вершинах \(v\) і виконати \(x_v := x_v + val\). Складність — \(O(\frac{len}{B}\) i \(O(\frac{len}{B} + B)\) для великого і малого шляху відповідно.
Отже, складність для одного запиту рівна \(O(\frac{len}{B} + B)\), сумарна складність рівна \(O(k \cdot (\frac{len}{B} + B) + n \cdot B)\). Якщо вибрати \(B^2 = len\) тоді загальна складність \(O((n + k) \cdot \sqrt {len})\).