Очевидно, що перший алгоритм потрібно завжди реалізувати з нуля. Для всіх інших циклом пройдемо по них (від другого до останнього) та перевіримо, чи відрізняється поточний алгоритм від попереднього. Якщо відрізняється, додамо до відповіді 1.
Серед коржів з однаковим радіусом необхідно вибрати той, що має найбільший об’єм. Коржі з різними радіусами завжди можна поставити так, аби корж зверху мав менший радіус, ніж корж знизу. Отже, потрібно просто просумувати максимальні об’єми по всіх унікальних радіусах.
Один зі способів згенерувати паролі — це розглянути числа від 1 до
\(n\) в системі числення з основою
\(k\). Цифра 0 відповідатиме букві
a, 1 — b, і т. д.
Записати число \(x\) в системі числення з основою \(k\) доволі просто — для цього необхідно \(m\) разів виконувати такий процес: візьмемо остачу від ділення \(x\) на \(k\) та цілочисельно поділимо \(x\) на \(k\). Остачі від ділення на кожному кроці утворюють число в системі числення з основою \(k\).
\[\sum_{i=1}^n |p_i - i| \equiv \sum_{i=1}^n p_i + \sum_{i=1}^n i \equiv \frac{n(n+1)}{2}+\frac{n(n+1)}{2} \equiv n(n+1) \equiv 0 \mod 2\]
Отже, якщо \(k\) непарне, то
відповідь NO.
Якщо \(k \le 2 \cdot (n - 1)\), тоді ми можемо побудувати таку перестановку: \[\left(\underline{\frac{k}{2}+1}, 2, 3, \ldots, \frac{k}{2}-1, \frac{k}{2}, \underline{1}, \frac{k}{2}+2, \frac{k}{2}+3, \ldots, n - 1, n\right)\]
Якщо \(k > 2 \cdot (n-1)\), тоді
зробимо \(p_1 = n\) і \(p_n = 1\). \(|p_1-1|+|p_n-n|=2 \cdot (n-1)\). Зменшимо
\(k\) на \(2
\cdot (n - 1)\) і розв’яжемо меншу задачу на підпослідовності
\((2, 3, \ldots, n - 1)\),
використовуючи аналогічні міркування. Якщо на якомусь кроці ми
використали всі елементи перестановки, але \(k\) все ще більше за 0, значить розв’язку
не існує і відповідь — NO.
Приклад для \(n=11\), \(k=44\).
\((1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) \xrightarrow{\text{+20}} (\underline{11}, 2, 3, 4, 5, 6, 7, 8, 9, 10, \underline{1}) \xrightarrow{\text{+16}} (11, \underline{10}, 3, 4, 5, 6, 7, 8, 9, \underline{2}, 1) \xrightarrow{\text{+8}} (11, 10, \underline{7}, 4, 5, 6, \underline{3}, 8, 9, 2, 1)\).
Спробуємо перевірити, чи існує квадрат розміру \(k \times k\) який має усі елементи менші за \(x\).
Утворимо новий масив \(a_{i j} = 0\), якщо \(d_{i j} \le x\) або \(a_{i j} = 1\) інакше. Тоді порахувавши префіксні суми, ми можемо знайти суму в одному квадраті \(k \times k\) за \(O(1)\).
Переберемо всі квадрати, і якщо хоча б в одному з них сума буде рівна \(0\) — це означатиме, що квадрат не містить елементів більших за \(x\).
Тепер ми можемо скористатися методом двійкового пошуку для того, аби знайти мінімальне значення \(x\), для якого існує квадрат \(k \times k\), що містить усі елементи не більші за \(x\). Це значення й буде відповіддю на задачу.
Код розв’язку Python (набирає 10 балів)
Трикутник з найменшою площею побудований на вершинах опуклого многокутника складатиметься з трьох послідовних вершин многокутника. Для доведення цього факту треба скористатись формулою для обчислення площі трикутника: площа рівна половині добутку довжини основи трикутника на довжину висоти, опущеної на неї.
Якщо розглянути трикутник, який складається не з трьох послідовних вершин, зафіксувати дві з них, і сунути третю в один з двох напрямків по вершинах многокутника, довжина висоти буде зменшуватись, а отже площа трикутника також буде зменшуватися. Такий процес можна продовжувати, поки вершини трикутника не будуть послідовними вершинами многокутника. На рисунку площі трикутників \(ABD\) та \(ABE\) менші за площу трикутника \(ABC\), бо відстані від точок \(D\) та \(E\) до прямої \(AB\) менші за відстань від точки \(C\) до цієї прямої.
Тепер подивимось на те, як буде грати Зеник. Оскільки він хоче мінімізувати площу трикутника, то на своєму ході він просто обере найменший трикутник з трьох послідовних вершин многокутника й розріже многокутник уздовж відповідної діагоналі. На цьому гра завершиться.
Марічці ж, знаючи, що Зеник завжди завершить гру своїм ходом, немає змісту давати йому можливість вибрати трикутник з найменшою площею, тому вона на своєму ході обере найбільший трикутник, який складається з трьох послідовних вершин многокутника. Отже, Марічка може завершити гру на першому ході.
Відповідь на задачу — найбільша площа трикутника з трьох послідовних вершин многокутника.
Розглянемо дві сусідні станції \(j\) та \(j+1\). Між ними розташовані будинки з індексами від \(l\) до \(r\).
Сформулюємо та доведемо таке твердження. Для деякого оптимального розв’язку існує такий індекс \(s\), \(l \le s \le r\), що потреби \(i\)-ого будинку будуть повністю забезпечені водою з \(j\)-ої станції при \(l \le i < s\), повністю покриті водою з \((j+1)\)-ої станції при \(s < i \le r\), а потреби \(s\)-ого будинку — частково з \(j\)-ої, частково з \((j+1)\)-ої станцій (можливо, повністю з однієї станції).
Доведення. Припустимо, що до \(i\)-го будинку, де \(l \le i \le r\) привезли воду з \(t\)-ї станції, \(t<j\). Це не вигідно, бо цю воду можна було привезти з \(j\)-ї станції, тоді сумарна відстань буде меншою. Аналогічно невигідно везти воду з \(t\)-ї станції, якщо \(t>j+1\).
Отже, потреби всіх будинків між станціями \(j\) та \(j+1\) вигідно покрити водою із цих станцій.
Нехай \(i_1\) — найправіший будинок, до якого везли воду з \(j\)-ї станції, а \(i_2\) — найлівіший, до якого везли з \((j+1)\)-ї.
Припустимо, що \(i_2<i_1\). Нехай до \(i_1\)-го будинку з \(j\)-ї станції привезли \(c_1\) літрів води, а до \(i_2\)-го з \((j+1)\)-ї — \(c_2\) літрів. Позначимо \(d=\min\{c_1, c_2\}, c_1’=c_1-d, c_2’=c_2-d\).
Якщо до \(i_1\)-го будинку з \(j\)-ї станції привезуть \(c_1’\) літрів води, до \(i_2\)-го з \((j+1)\)-ї станції — \(c_2’\) літрів, а недостачу \(d\) літрів для \(i_1\)-го та \(i_2\)-го будинків будуть покривати відповідно \((j+1)\)-а та \(j\)-а станції, то сумарна відстань зменшиться, позаяк \(c_1’\) або \(c_2’\) дорівнює нулю.
Отже, \(i_1 \le i_2\).
Потреби будинків з номерами меншими за \(i_1\) буде покривати \(j\)-а станція, більшими за \(i_1\) — \((j+1)\)-а станція. Якщо \(i_1=i_2\), то потреби \(i_1\)-го будинку будуть покривати обидві станції. Тому можна взяти \(s=i_1\).
Отже, твердження доведено.
Звідси випливає, що проміжки між сусідніми станціями можна розв’язувати незалежно один від одного. Задача розбивається на підзадачі з двома станціями \(j\) та \(j+1\) та будинками між ними. Навчимося розв’язувати таку підзадачу.
Розв’язок за \(O(\sum_{i} a_i)\).
Скористаємося динамічним програмуванням.
Нехай \(dp_1[x]\) — мінімальна відстань, яку має проїхати автомобіль з лівої станції, щоб відвезти будинкам \(x\) літрів води. \(x\) однозначно визначає, яким будинкам скільки води привезе автомобіль. Нехай \(i\) — найправіший будинок, якому лівий автомобіль привезе воду. Тоді \(dp_1[x] = dp_1[\max\{0, x - k\}]+2(h_i-s_j)\).
Таку саму динаміку \(dp_2\) можна порахувати для правої станції. Відповіддю на підзадачу буде \(\min_x dp_1[x]+dp_2[t-x]\), де \(t=\sum_{i} a_i\) — сума потреб будинків.
Розв’язок за \(O(n^2 \log n)\).
Розглянемо числову пряму, на якій число \(x\) відповідає \(x\) літрам води. \(l\)-му будинкові відповідає півінтервал \(\left(0, a_l \right]\), \((l+1)\)-му — \(\left(a_l, a_l+a_{l+1} \right]\), \((l+2)\)-му — \(\left(a_l+a_{l+1}, a_l+a_{l+1}+a_{l+2} \right]\) і т.д. Позначимо кінець півінтервалу, що відповідає \(i\)-ому будинку \(e_i\). Також у кожного будинку є число \(f_i=2(h_i-s_j)\) — відстань, яку має проїхати автомобіль від \(j\)-ої станції до будинку й назад. Динаміку \(dp_1\) з попереднього розв’язку можна уявити на цій прямій: остання поїздка автомобіля — це стрибок з точки \(x-k\) в точку \(x\), за цей стрибок платимо \(f_i\), де \(i\) — номер будинку, чиєму півінтервалу належить точка \(x\). Процес розвезення води лівим автомобілем можна представити послідовністю точок \(w, w + k, w + 2 \cdot k, \dots, w + p \cdot k\) — за першу поїздку відвозимо \(w \le k\) літрів, за кожну наступну — \(k\) літрів.
Якщо \(w<k\) та жодна з точок \(w+p \cdot k\) не є кінцем півінтервалу якогось будинку, то можемо кожну точку в послідовності посунути вправо на одиницю, при цьому сумарна відстань не збільшиться (кожна точка залишиться в тому півінтервалі, де вона була), а відвезена кількість літрів (остання точка в послідовності) збільшиться на одиницю. Тому варто розглядати тільки такі \(w\), що \(w=k\) або такі, що \(w+p \cdot k=e_i\) для деяких \(p\), \(i\), тобто \(w \equiv e_i \mod k\) — різних кандидатів на \(w\) буде \(O(n)\).
Наступне спостереження: якщо лівий автомобіль привіз повну цистерну води до \(i\)-ого будинку, то він буде продовжувати возити туди повні цистерни, поки може.
Для кожного \(w\) маємо таких кандидатів на межу поділу між лівим та правим автомобілями.
Повністю покриваємо потреби будинків до \((i-1)\)-ого. Воду, що залишилася, веземо до \(i\)-ого будинку. Останньою точкою буде такий мінімальний \(x\), що \(e_{i-1} < x \le e_i\), \(x \equiv w \mod k\). Зауважте, що такої точки може не існувати. Назвемо такого кандидата кандидатом типу А.
Повністю покриваємо потреби будинків до \((i-1)\)-ого. Воду, що залишилася, веземо до \(i\)-ого будинку. Возимо повні цистерни до \(i\)-ого будинку, поки вони туди поміщаються. Останньою точкою буде такий максимальний \(x\), що \(e_{i-1}+k < x \le e_i\), \(x \equiv w \mod k\). Такої точки може не існувати. Назвемо такого кандидата кандидатом типу Б.
Для кожного \(w\) при переході між сусідніми кандидатами легко перераховувати відповідь. Якщо кандидат \(y\) потрапляє в півінтервал \(i\)-ого будинку, а попередній кандидат був \(x\), то до відповіді додасться \(\frac{y-x}{k}f_i\) (число \(\frac{y-x}{k}\) ціле).
Для лівого та правого автомобілів порахуємо відповіді для всіх кандидатів.
Щоб знайти відповідь на задачу, треба для кожного кандидата для лівого автомобіля \(x\) знайти такого найменшого кандидата \(y\) для правого автомобіля, що \(x+y \ge t\), де \(t=\sum_{i} a_i\) — сума потреб будинків.
Це можна зробити, посортувавши кандидатів.
Складність сортування буде \(O(n^2 \log n)\).
Розв’язок за \(O(n^2)\).
Посортуємо всіх кандидатів на \(w\). Зауважимо, що в кожному півінтервалі буде не більше як два кандидати з однаковою остачею за модулем \(k\) (не більше як один типу А та не більше як один типу Б з такою остачею). Хочемо посортувати кандидатів в \(i\)-ому півінтервалі за \(O(n)\). Спершу знайдемо мінімального кандидата типу А в цьому півінтервалі. Нехай його остача за модулем \(k\) дорівнює \(z\). Додамо до посортованого списку кандидатів типу А для всіх остач \(w\) від \(z\) до \(k-1\), потім — від 0 до \(z-1\). Для цього пройдемося по списку кандидатів на \(w\). У такий спосіб ми посортували кандидатів типу А. Так само зробимо з кандидатами типу Б. Отже, посортували всіх кандидатів.