У цій задачу потрібно лише зчитати числа \(a, b, k\) та вивести \(a+b \cdot k\).
Якщо в кожному рядку буде хоча б один заражений квартал, або в
кожному стовпці буде хоча б один заражений квартал, тоді відповідь —
YES, оскільки ці віруси можуть кожен вибрати свій рядок або
стовпець і в результаті заразити все поле. У протилежному разі —
відповідь NO, оскільки буде хоча б одна клітинка, у якої в
рядку та стовпці немає жодної зараженої клітинки, і тому вона ніколи не
стане зараженою.
Із заданої множини чисел розміром \(n\) необхідно вибрати \(k\) чисел так, щоб їх сума була непарною.
Поділимо усі числа на дві множини: парні і непарні. Для того щоб сума вибраних чисел була непарною, необхідно вибрати непарну кількість непарних чисел. Далі задачу можна розв’язувати багатьма способами. Один з можливих розв’язків наступний: візьмемо одне непарне число. Тоді, поки ще треба брати числа, і є хоча б два непарних числа, будемо брати по два непарних числа. Якщо після цього необхідно добрати ще чисел, добираємо парні. Якщо ми таким процесом вибрали рівно \(k\) чисел, то вони і є відповіддю на задачу. Інакше, відповіді не існує.
У цій задачі потрібно об’єднати всі задані проміжки \([l_i, r_i]\) та вивести суму \(k\) перших значень, які належать їм.
Застосуємо метод скануючої прямої. Створимо вектор подій \(t\) — відкриття проміжку та закриття. Відкриття відбудеться в момент часу \(l_i\), а закриття — в момент \(r_i+1\) (тобто права границя береться невключно). Причому для кожної події запам’ятаємо її тип — відкриття або закриття. Посортувавши ці події за зростанням, будемо перебирати від першої до останньої та підтримувати баланс відкритих проміжків (поточна кількість подій відкривання мінус кількість подій закривання). Якщо до події \(t_i\) баланс є додатним, це означає, що таблетки з проміжку \([t_i, t_{i+1})\) лікують вірус.
Якщо \(k\) перевищує значення \(t_{i+1}-t_i\) (кількість таблеток у проміжку), потрібно додати суму всіх цих таблеток до відповіді, а від \(k\) відняти їх кількість. У протилежному разі, потрібно лише додати суму перших \(k\) та завершити роботу.
Необхідно заданий рядок довжини \(n\) трансформувати в інший, використовуючи операцію «перенести якийсь символ в кінець рядка». Дозволено використовувати не більше ніж \(n\) операцій. Зрозуміло, що для існування відповіді необхідно, щоб кількості відповідних букв в обох рядках співпадали.
Нехай початковий рядок \(s = s_0s_1...s_{n-1}\), та кінцевий рядок \(t = t_0t_1...t_{n-1}\). Будемо будувати рядок \(t\) зліва направо: першою операцією візьмемо символ \(t_0\), другою операцією — символ \(t_1\) і т. д. Останньою операцією візьмемо останній символ \(t_{n-1}\).
На \(i\)-ому кроці в нас є побудований префікс рядка \(t\) довжини \(i-1\), та використані деякі символи рядка \(s\). Треба серед того, що залишилося в рядку \(s\), знайти символ, який відповідає символу \(t_i\), і застосувати операцію до нього. Найпростіша реалізація такого розв’язку працює за час \(O(n^2)\) та набирає 15 балів з 25 можливих.
Оптимізувати цей розв’язок можна так: для кожної з 26 букв запишемо позиції їх входження в рядок \(s\). Кожен символ будемо використовувати справа наліво. Коли беремо якийсь символ, все що треба зробити — пройтися по всіх вказівниках для інших символів і для тих, що є праворуч, запам’ятати, що вони тепер змістилися на одну позицію ліворуч. Така оптимізація перетворює розв’язок у лінійний, тобто \(O(n)\).
У цій задачі дві точки рухаються, кожна в деякому напрямку і з деякою швидкістю. У нас є точка, яка рухається в будь-якому напрямку, зі швидкістю, яка не перевищує задану. Треба нашою точкою зловити дві інші.
Оскільки за умовою задачі наша швидкість перевищує швидкість інших двох точок, то ми завжди можемо зловити ці дві точки. Можна показати, що завжди буде вигідною така стратегія: спершу ловимо якомога швидше якусь одну точку. Тоді ловимо іншу. Для розв’язку переберемо два варіанти, яку з точок ловити першою.
Тепер задача зводиться до такої: задано нашу початкову точку (\(x\), \(y\)), нашу максимальну швидкість \(v\), початкове розміщення точки, яку ми хочемо зловити (\(x_0\), \(y_0\)), та вектор руху цієї точки (\(dx\), \(dy\)). Оскільки ми хочемо зловити точку якомога скоріше, то ми будемо рухатися з максимальною швидкістю до точки, у якій ми зустрінемося із ціллю. Нехай це займе час \(t\). Тоді зустріч відбудеться в точці (\(x_0 + dx \cdot t\), \(y_0 + dy \cdot t\)). Умова коректності такої точки є те, що час, за який ми доберемося до неї повинен бути рівно \(t\):
\(t = \frac{\sqrt{(x_0 + dx \cdot t - x)^2 + (y_0 + dy \cdot t - y)^2}}{v}\)
Якщо переписати цю умову, отримаємо квадратне рівняння:
\(t^2 \cdot (v^2 - dx^2 - dy^2) - 2 \cdot t \cdot (dx \cdot (x_0 - x) + dy \cdot (y_0 - y)) - (x_0 - x)^2 - (y_0 - y)^2 = 0\)
Додатний розв’язок цього рівняння — час, за який ми зловимо точку.
Застосуємо метод динамічного програмування. Підвісимо дерево за довільну вершину-корінь та введемо такий стан динаміки: \([v][mask]\) — скількома способами можна розрізати ребра в піддереві вершини \(v\) так, аби утворені компоненти (усі, окрім тої, яка вище за \(v\)) покривали розміри з масиву \(a\), які вибрані в масці \(mask\).
Для обчислення відповіді для вершини \(v\) та всіх масок (їх буде \(2^k\)) потрібно ввести допоміжну динаміку по всіх синах вершини \(v\). Кожен із синів повинен покривати якусь підмаску, а їх об’єднання має утворити цілу маску. Таку динаміку можна перерахувати за \(3^k\) для кожного сина, перебираючи підмаски поточної маски, яку має покривати поточний син.
Після обчислення допоміжної динаміки для синів є дві опції щодо вершини \(v\) — або залишити ребро, яке веде до її батька, або видалити його. При цьому для маски, яку покрили сини, можна визначити, яким буде розмір нової утворено компоненти у випадку, коли ребро буде видаленим. Цей розмір повинен бути присутнім серед усіх непокритих значень у масці. Якщо їх декілька, переберемо кожен варіант вибору та виставимо відповідний біт в 1.
У результаті в стані \([root][2^k-1]\) буде записано відповідь. Проте деякі розрізання могли бути пораховані декілька разів. Це відбуватиметься у разі, коли в масиві \(a\) були однакові значення. Причому якщо якесь значення повторювалось \(c\) разів, то відповідь була домножена на \(c!\), оскільки кожен з варіант був обраний рівно один раз. Тому наприкінці для кожного значення масиву \(a\) поділимо відповідь на \(c!\), де \(c\) — кількість входжень цього значення в масив \(a\).