Порахуємо, скільки разів Марічка може виграти каменем. Ця кількість не може бути більша за кількість ігор, у яких Марічка поставила камінь, і не може бути більша за кількість ігор, у яких Зеник поставив ножиці, тобто \(min(r_M, s_Z)\). Аналогічно, кількість ігор, у яких Марічка може перемогти ножицями й папером рівна \(min(s_M, p_Z)\) i \(min(p_M, r_Z)\), відповідно. Відповідь до задачі буде рівна сумі цих трьох доданків.
Нехай кількість одиниць рівна \(a\), а кількість нулів рівна \(b\). Якщо \(a \le b\) тоді \(2 \cdot a \le a + b = n\). Тому одиниць є не більше ніж половина, і якщо ми видалимо їх усіх, то отримаємо рядок з нулів, який є паліндромом. Аналогічно, коли \(b \le a\), ми можемо видалити всі нулі й отримати рядок з одиниць, який також є паліндромом.
Можна зауважити, що оптимальний рядок — це конкатенація рядків виду
bohdan, danylo, maksym та
bohdanylo. Без обмеження загальності, уважатимемо, що \(d \le b\), а отже немає сенсу
використовувати рядок danylo в нашій назві (якщо він не є
частиною рядка bohdanylo).
Розглянемо два варіанти:
Не використовувати рядок
maksymу назві. Припустимо, що в оптимальній назві рядокbohdanзустрічається принаймні 9 разів, аbohdanylo— принаймні 6 разів. Тоді при заміні дев’яти рядківbohdanна шість рядківbohdanylo(або навпаки) прибуток не зменшиться, а отже існує оптимальна назва, де кількість рядківbohdanменша ніж 9, або кількість рядківbohdanyloменша ніж 6. Тому переберемо кількість рядківbohdanвід 0 до 8, а рeшту вільного місця виділимо під рядокbohdanylo(та навпаки). У такий спосіб ми отримаємо оптимальну назву для команди.Використаємо рядок
maksymпринаймні один раз. Тоді легко бачити, що рядкиmaksymітимуть поряд, і для \(1 \le k\) рядківmaksymпотрібно рівно \(5k + 1\) символів. Аналогічно до попереднього пункту, можна показати, що існує оптимальна назва, у якій або кількість рядківmaksym, абоbohdan, абоbohdanyloне перевищує, наприклад, 20 (існують і строгіші оцінки). Тому перебравши кількість рядків одного із цих типів, зведемо отриману задачу до попереднього пункту (див. код для кращого розуміння).
Складність розв’язку: \(O(1)\) часу та пам’яті.
Розв’язок зі складністю \(O(nmk)\). Переберемо всі можливі \(a\) і \(b\) та перевіримо, чи точки, що з’єднані між собою, належать різним прямокутникам.
Розв’язок зі складністю \(O(n(m^2+k))\). Переберемо \(a\). Якщо для деяких з’єднаних точок \((x_1, y_1), (x_2, y_2)\) виконується \(\left \lfloor{\frac{x_1}{a}}\right \rfloor \ne \left \lfloor{\frac{x_2}{a}}\right \rfloor\), то ці точки будуть у різних прямокутниках. Тепер розглядаємо лише ті пари точок, для яких ця умова не виконується. Треба задовольнити умову \(\left \lfloor{\frac{y_1}{b}}\right \rfloor \ne \left \lfloor{\frac{y_2}{b}}\right \rfloor\).
Тепер маємо одновимірну задачу. Для її розв’язання заведемо масив \(d\). Значення \(d[i]\) означає найменшу \(y\)-координату, не меншу за \(i\), серед усіх точок, що з’єднані з якоюсь точкою з \(y\)-координатою рівною \(i\). Іншими словами, це координата найближчої зверху точки, з’єднаної з точкою з \(y\)-координатою рівною \(i\). Після обчислення такого масиву можемо перебрати \(b\) та перевірити, чи виконується умова \(\left \lfloor{\frac{i}{b}}\right \rfloor \ne \left \lfloor{\frac{d[i]}{b}}\right \rfloor\) для всіх \(i\).
Потрібно перевірити для всіх \(i\) умову \(x_{i+1}-x_i \ge 2\).
Один з варіантів, що дає максимальну кількість будинків з хворими — це коли початкові \(k\) будинків з хворими знаходяться поруч на одній діагоналі. Тоді відповідь буде рівна \(k^2\), але кількість будинків з хворими не може бути більшою за кількість будинків у місті. Отже, відповідь — min(\(k^2\), \(n^2\)).
Зеник може в кожному магазині купувати одноразову маску. У цьому разі він заплатить \(\sum_{i=1}^n a_i\). Цей дивний запис означає суму \(a_i\) за всіма \(i\) від 1 до \(n\).
Якщо ж він вирішить придбати багаторазову маску в \(j\)-ому магазині, то йому доведеться купити одноразові маски в усіх магазинах перед \(j\)-им. Тоді він витратить \(b_j + \sum_{i=1}^{j-1} a_i\). Можна перебрати \(j\) — індекс магазину, де найвигідніше придбати багаторазову маску. Для цього будемо йти індексом \(j\) від 1 до \(n\) і підтримувати значення суми \(a_i\) на префіксі.
Відповіддю буде найменший серед усіх цих варіантів.
Розглянемо граф, вершинами якого будуть люди, причому деякі пари з них будуть з’єднані ребрами, що означатиме дружбу між відповідними людьми.
Запустимо пошук у глибину (або в ширину) з кожної вершини, відповідна людина якої була хворою у початковий момент часу, та помічатимемо відвідані вершини. Важливо не відвідувати вершину 1, а також раніше оброблені вершини. Наприкінці множина помічених сусідів вершини 1 буде відповідати множині друзів, з якими варто обірвати всякі контакти на час пандемії (адже ці друзі можуть стати зараженими).
Складність такого розв’язку — лінійна відносно розміру вхідних даних.
У цій задачу потрібно лише зчитати числа \(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\).
У задачі необхідно вивести 47-ий день заданого року. Таким днем
кожного року є 16 лютого. Відповідно для розв’язку задачі достатньо
просто вивести рядок 16.02. і потім номер року, який треба
зчитати з вводу.
За умовою задачі потрібно згенерувати перестановку \(n\) чисел так, щоб в ній було рівно \(k\) локальних мінімумів (чисел, сусіди якого більші за саме число), або сказати, що цього зробити не можна.
Зрозуміло, що неможливо зробити більше ніж \(\frac{n-1}{2}\) локальних мінімумів. Тому у
випадках, коли \(k >
\frac{n-1}{2}\), виведемо -1.
Щоб створити локальний мінімум у перестановці, нам достатньо просто поміняти місцями два сусідні числа у зростаючій послідовності. Щоб створити \(k\) локальних мінімумів просто зробимо \(k\) таких операцій. Наприклад:
\(1 2 3 4 5 6 7 \rightarrow 1 \Leftrightarrow 2 3 \Leftrightarrow 4 5 \Leftrightarrow 6 7 \rightarrow 2 1 4 3 6 5 7\)
Очевидно, що аби з рядка \(s\) можна було утворити \(t\), потрібно аби \(t\) був підпослідовністю \(s\). Для того щоб це перевірити, достатньо пройти циклом по рядку \(t\), підтримуючи вказівник на відповідне входження такого ж символу в \(s\). При переході до наступного символу в \(t\) потрібно сунути вказівник \(s\), допоки не знайдеться відповідний символ. Якщо вказівник прийшов у кінець рядка, і шуканий символ не був знайдений — підпослідовності не існує.
Після того як відомо, чи можна із \(s\) утворити \(t\), потрібно визначити мінімальну кількість кроків, необхідну для цього. Єдиним обмеженням є той факт, що не можна видаляти більше ніж два однакові символи в межах одного кроку. З цього випливає, що цю кількість можна окремо порахувати для кожної букви, а потім знайти максимальне значення. Зрозуміло, що якщо певну букву потрібно видалити \(x\) разів, то кількість кроків для цього — це \(\lceil \frac{x}{2} \rceil\) (заокруглене вгору).
У задачі задано послідовність із 4 і 7. За одну операцію можна видалити якийсь елемент з послідовності й додати до рахунку суму лівого й правого сусідів. Треба видалити всі елементи, крім першого й останнього, максимізувавши рахунок.
Задача розв’язується жадібно. Спочатку будемо видаляти четвірки, які є сусідами з хоча б однією сімкою, поки не видалимо всі четвірки (це завжди можна зробити за умови якщо присутня хоча б одна сімка). Потім видалимо всі сімки в такому порядку, щоб кожна сімка, яку ми видаляємо, сусідила з двома іншими сімками. Коректність такого підходу легко бачити, якщо розглянути еквівалентну задачу, у якій замість \(4\) і \(7\) є \(0\) і \(1\).
Реалізувати такий алгоритм можна, використовуючи структуру даних стек. Проходимося по послідовності зліва направо й кладемо елементи на стек. Якщо пробуємо поставити \(7\) на \(4\), то видаляємо \(4\). Якщо ставимо \(4\) на \(7\), то видаляємо \(4\) (не ставимо на стек). У результаті залишиться послідовність із сімок, яку треба опрацювати окремо.
За умовою задачі потрібно вивести координати центру кола певного радіусу, яке падає з точки \((x,\infty)\) після того, як воно торкнеться прямої \(y=0\) або іншого кола. Якщо коло не дотикається до інших, то відповідь для нього — \((x, r)\). Якщо ж дотикається — потрібно знайти найвищу точку \((x,y)\), де відбувається дотик. Для цього просто переберемо всі кола, що вже зупинилися, і спробуємо знайти точку, у якій ми будемо до такого кола дотикатися.
Знайти таку точку дуже просто. У момент дотику відстань між центрами двох кіл рівна сумі їхніх радіусів. Координати \(x\) центрів кожного з кіл нам відомі спочатку. За теоремою Піфагора можемо визначити, що \((y-y_i)^2 = (r + r_i)^2 - (x - x_i)^2\). Найбільше значення \(y\) і буде шуканою координатою \(y\) центра кола, що падає. Варто також звернути увагу на те, що для того, щоб коло зупинилося, відстань між центрами кіл має бути строго меншою за суму їхніх радіусів.
У задачі задано граф, у якому деякі ребра мають вагу, а деякі — ні. Необхідно зважити всі ребра, щоб найкоротша відстань між першою і останньою вершинами була рівна заданому числу \(w\).
У першій підзадачі, яка вартувала 10 балів, усі ребра початково не мали ваги. Для того щоб розв’язати цю підзадачу, достатньо знайти шлях між першою і останньою вершинами, на якому є найменша кількість ребер, наприклад, алгоритмом пошуку вшир (BFS). Нехай ця кількість рівна \(k\). Тоді якщо \(k > w\), то відповіді не існує. Інакше вона завжди існує і її можна досягнути, наприклад, так: всім ребрам не на найкоротшому шляху дамо вагу \(w\), усім ребрам, окрім одного на шляху, дамо 1, а останньому дамо \(w - k\). У такий спосіб будь-який шлях, окрім найкоротшого, буде мати вагу не меншу за \(w\), а найкоротший буде мати вагу рівно \(w\).
Для того щоб розв’язати задачу повністю, спершу зробимо, щоб усі ребра без ваги мали вагу 1. Знайдемо найкоротшу відстань між першою і останньою вершинами, наприклад, алгоритмом Дейкстри. Якщо вона перевищує \(w\), то відповіді не існує.
Тепер будемо перебирати всі ребра, які треба зважити, в довільному порядку і для кожного з них повторимо такий процес. Знайдемо найкоротшу відстань між першою і останньою вершиною. Нехай ця відстань рівна \(d\). Додамо до ваги поточного ребра значення \(w - d\) (це значення завжди буде невід’ємне).
Після того як опрацюємо всі ребра, ще раз знайдемо найкоротшу відстань між першою і останньою вершинами. Якщо вона рівна \(w\), то ми знайшли відповідь. Інакше, відповіді не існує.
Неважко побачити, що задача зводиться до такої — знайти максимальну кількість точок, які можна вибрати на лінії так, аби виконувалися такі умови.
Для кожної компанії був хоча б один варіант вибору кінцевої точки, який би не проходив через жодну з вибраних.
Між кожною парою сусідніх вибраних точок має бути хоча б одна компанія.
Це зведення означає, що ми виділяємо максимальну кількість точок-розділювачів, через які не можуть проходити ремонтні роботи, в той час як між ними має бути хоча б одна. Зрозуміло, що максимізація цього числа є еквівалентною максимізації кількості проміжків, яку просять в умові.
Таку зведену задачу легко розв’язати методом динамічного програмування. Введемо стан — координата останньої вибраної точки — і для цього стану будемо максимізовувати загальну кількість уже вибраних точок. Для переходу з такого стану переберемо наступну вибрану точку справа від поточної. Залишається лише перевірити, чи коректним є такий перехід, а саме, чи існує хоча б одна компанія між цими точками, а також, чи кожна з них «поміститься» між цими точками.
Задано масив цілих чисел. Треба сказати, скільки є таких індексів \(i\), що \(a_i\) та \(a_{i+1}\) різної парності.
Задано натуральне число \(n\). Треба сказати кількість натуральних чисел, що не перевищують \(n\), таких, що їхня сума цифр — щаслива.
Переберемо всі числа від 1 до \(n\) і перевіримо, чи сума цифр щаслива.
Задано масив чисел. Можна видалити деякі з них так, щоб сума чисел, які залишаться, була не меншою за \(x\) і середнє арифметичне цих чисел було максимальне.
Ми хочем, щоб \(\frac{sum}{count}\) чисел, які залишаться, було максимальним. Припустимо, що в нас фіксований \(count\), тоді ми хочем максимізувати суму. Тоді нам достатньо видалити \(n-count\) найменших чисел, щоб максимізувати суму.
Оптимальним рішенням задачі буде видаляти найменше число, поки це можливо.
Марічка й Зеник грають у гру. Є \(n\) купок каменів. Марічка ходить першою і може вибрати підмножину купок розміру від 1 до \(n-1\) і забрати будь-яку ненульову кількість каменів з кожної із цих купок. Зеник має право забирати будь-яку ненульову кількість каменів тільки з однієї купки. Програє той хто не зможе зробити ходу. Хто виграє при оптимальній грі обох?
Припустим, \(n \ge 3\). Марічка може забрати 1 купку першим ходом. Незалежно від ходу Зеника на наступному ході Марічки буде щонайменше \(n-2\) купки і не більше ніж \(n-1\) купка, тому Марічка зможе забрати їх усіх. Якщо \(n = 2\), то Зеник виграє тоді й тільки тоді, коли \(a_0 = a_1\). Він зможе завжди повторювати хід Марічки, але в протилежну купку. Інакше виграє Марічка, звівши гру першим ходом до гри, де \(a_0 = a_1\)
У вас є число \(n < 10^9\). Ви можете поділити (якщо ділиться) його на 4 або відняти 7. Треба сказати, чи можна отримати 1.
Розглянемо задачу з іншого боку — ми можем помножити число на 4 й додати 7. Переберем кількість множень на 4. Їх буде не більше ніж \(\log_4 n\). Нехай кількість множень — \(x\). Наше число — це \(4^x\) і тепер ми можемо додати \(7 \cdot 4^y\), де \(y \le x\). Будем додавати числа жадібно — знаходити таке найбільше \(y\), що \(7 \cdot 4^y\) в сумі з нашим поточним числом менше або рівне тому числу, яке нам потрібне.
Вам задано натуральне число \(n\), та потрібно сказати яку максимальну кількість елементів можна вибрати з множини \(\{1, 2, \ldots, n\}\), так щоб жодні два вибрані елементи не відрізнялись на 4 або 7.
Спершу наведемо приклад розв’язку динамічним програмуванням. Позначимо через \(dp[i][mask]\) найбільшу кількість елементів, які ми можемо вибрати з множини \(\{1, 2, ..., i\}\), причому маска \(mask\) відповідає за те, чи брали ми 7 останніх елементів. З кожного стану є не більше ніж два переходи: ми можемо або взяти поточний елемент (якщо він не конфліктуватиме із жодним з попередніх), або ж пропустити його.
Складність такого алгоритму: \(O(n \cdot 2^7)\) по часу та пам’яті, що проходитиме 80% тестів, втім його можна оптимізувати до \(O(n)\) по пам’яті, тримаючи динаміку пошарово, хоч це й доволі складно реалізовувати.
Другий розв’язок конструктивний. Розглянемо групу з 11 елементів, що йдуть підряд. Можна показати (або на папері, або програмно згенерувати попереднім розв’язком), що з них не можна вибрати більше ніж 5 елементів, що не конфліктуватимуть між собою. Причому саме 5 елементів можна вибрати, наприклад, узявши набори \(\{1, 3, 4, 6, 9\}\) чи \(\{1, 2, 4, 7, 10\}\). Тепер будуватимемо відповідь так: розіб’ємо множинну \(\{1, 2, \ldots, n\}\) на блоки по 11 чисел у кожному (можливо, менше в останньому). Ясно, що з кожного блоку ми можемо взяти не більше ніж 5 чисел. Розглянувши кілька простих випадків, бачимо, що якщо остача \(n\) за модулем 11 рівна 2, то можна в кожній групі вибирати елементи з множини остач \(\{1, 2, 4, 7, 10\}\), а в інших випадках — з множини \(\{1, 3, 4, 6, 9\}\). Формальне доведення залишаємо вам на домашнє завдання :)
Складність такого розв’язку: \(O(n)\) по часу та \(O(1)\) по пам’яті.
Вам задано \(n\) ламп, кожна початково може бути або вимкненою, або ввімкненою. Вам потрібно зробити рівно \(n\) ходів, на \(i\)-ому з них ви вибираєте рівно \(i\) ламп та змінюєте їхній стан на протилежний. Чи можна вимкнути всі лампи?
Як і в попередній задачі, опишемо два розв’язки — конструктивний та за допомогою динамічного програмування.
Спершу розв’язок динамічним програмуванням. Нехай \(dp[i][j]\) — це кількість ламп, які треба було вимкнути на \(і\)-ому кроці, щоб після нього рівно \(j\) ламп були ввімкнені. Зауважимо, що таких можливих кількостей може бути декілька. У такому разі \(dp[i][j]\) — будь-яка з них. Якщо ж після \(i\)-ого кроку взагалі неможливо мати рівно \(j\) ввімкнених ламп, то в \(dp[i][j]\) триматимемо відповідну мітку (наприклад, -1).
Якщо після \(i\)-ого кроку в нас
рівно \(j\) увімкнених ламп і на \((i + 1)\)-ому кроці ми вимикаємо \(k\) ламп, то вмикаємо \((i + 1 - k)\) ламп. Тоді кількість
ввімкнених ламп стане \((j - k + i + 1 -
k)\). Тобто, якщо в стан \(dp[i][j]\) можливо перейти, то можна
оновити \(dp[i + 1][j - k + i + 1 -
k]\) значенням \(k\). Якщо в
стан \(dp[n][0]\) неможливо прийти, то
відповідь — No. Інакше — Yes. Для кожного
стану ми знаємо, скільки ламп треба було вимкнути на попередньому кроці,
і можемо симулювати процес. Складність: \(O(n^3)\) часу та \(O(n^2)\) пам’яті.
Конструктивний розв’язок. Покажемо, що з початкового стану ми завжди можемо перейти в стан, де всі (крім, можливо, однієї) лампи є вимкнутими. Спочатку зауважимо, що порядок ходів не має значення, тому робитимемо спочатку \(n\) перемикань, потім \(n - 1\) і так далі. Підтримуватимемо такий інваріант: після ходу з \(і\) перемиканнями є не більше за \(i\) ввімкнених ламп. Спочатку таке, звісно ж, виконується. На кожному кроці будемо в першу чергу вимикати всі ввімкненні лампи, а в другу — вмикати вимкнуті. Якщо на якомусь кроці ми маємо змінити стан \(i\) ламп, причому на його початку було не більше ніж \(i + 1\) ввімкнута лампа, то таким процесом ми залишимо не більше за \(і\) ввімкнутих ламп.
Тепер покажемо, що з ніякого стану ми не можемо перейти якимись ходами в стан, де всі лампи вимкнуті, а якимись іншими — де всі, крім рівно однієї, вимкнуті. Це зрозуміло з міркувань парності, адже парності кількостей перемикань всіх ламп у цих двох кінцевих станах відрізняються, що неможливо з огляду на те, що сума перемикань для досягнення кожного з них є однаковою, а саме \(1 + 2 + \ldots + n = \frac{n \cdot (n + 1)}{2}\), де \(n\) — початкова кількість ламп.
Тому ми виконуватимемо процес, описаний у першій частині, і якщо в кінцевому стані всі лампи вимкнені, то це і є розв’язок, інакше — розв’язку не існує.
Складність такого розв’язку: \(O(n^2)\) часу та пам’яті.
Задано два цілі числа. Треба вивести третє, таке що одне з двох чисел не вході є меншим за третє, а інше — більше.
Якщо \(|a-b| \le 1\), то таке зробити неможливо. Інакше відповідь існує. Наприклад, завжди підходить число \(min\{a, b\} + 1\).
Задано рядок символів. Потрібно сказати, скільки символів треба вставити в рядок, щоб жодні два символи підряд не були однаковими.
Щоб два однакові символи підряд перестали бути двома однаковими символами підряд, достатньо вставити поміж них будь-який інший символ. Тому відповідь — кількість пар однакових символів підряд.
Набір кубиків розташовано на прямокутнику, у кожній клітинці прямокутника є декілька кубиків, поскладаних один на одного. Треба вивести послідовність, у якій їх забирати, щоб на кожному кроці кількості кубиків у клітинках утворювали незростаючі послідовності в кожному рядку й у кожному стовпці.
У задачі є багато можливих розв’язків. Наприклад, можна йти по рядках знизу вверх, по кожному рядку справа наліво й повністю забирати всі кубики з клітинок у такому порядку. Легко бачити, що при такому порядку забирання кубиків необхідна умова завжди буде підтримуватися.
Задано набір з \(n\) чисел, кожне з яких від 1 до 4. Потрібно розбити цю множину на дві з однаковою сумою.
Очевидно, для кожної з можливих ваг \((1..4)\) нас цікавить, скільки котів з такою вагою припаде Зенику. Тому достатньо перебрати всі четвірки чисел \((c_1, c_2, c_3, c_3)\), які позначають, скільки котів певної ваги отримає Зеник. Якщо існує четвірка, для якої \(1 \cdot c_1 + 2 \cdot c_2 + 3 \cdot c_3 + 4 \cdot c_4 = \frac{s}{2}\) — розділити котів можна, інакше — ні (тут \(s\) — загальна вага всіх котів).
Задано масив чисел. Видалимо з нього всі такі елементи, що елемент ліворуч від них є більшим. Повторюємо такий процес, поки масив міняється. Треба сказати результуючий масив.
Зрозуміло, що з масиву видаляться всі такі елементи, що десь праворуч від них є більший елемент, а всі решта залишаться. Тому будемо йти справа наліво і підтримувати максимум на суфіксі. Якщо поточне число менше за максимум, то воно видалиться. Інакше воно увійде в результуючу послідовність.
Задано розміри прямокутника, який треба покрити плиткою \(2 \times 1\). Одну з клітинок покривати не можна. Потрібно сказати, чи можна покрити всі клітинки, крім заданої. Якщо так — вивести розбиття.
Неважко побачити, що коли \(n\) або \(m\) є парними, то відповіді не існує. Адже в такому разі загальна кількість клітинок, які потрібно покрити, є непарною, тому це неможливо.
Коли \(n\) та \(m\) є непарними, покриття все ще може бути неможливим (другий тест з умови). Розфарбуємо прямокутник у шаховому порядку. Причому пофарбуємо верхню ліву клітинку в білий колір. У такому разі білих клітинок на одну більше, ніж чорних. Оскільки одна плитка покриває одну білу та одну чорну клітинки — нам потрібно, щоб кіт спав на білій. Клітинка біла, якщо \(x+y\) — парне число.
Якщо ж \(n\) та \(m\) є непарними, а \(x+y\) — парним, прямокутник можна розфарбовувати так. Неважко з правої сторони відрізати смужку довжиною 2:
(Так само можна відрізати смужку розміром 4, 6, 8, ..., тобто будь-яку парну довжину.)
Аналогічно по інших сторонах:
Після цього або вся площа буде закладеною, або ж залишиться квадрат \(3 \times 3\), усередині якого є виділена клітинка. Такий квадрат легко розфарбувати — достатньо розкласти 4 плитки «по колу» від виділеної клітинки.
Задано дерево, у якому \(k\) вершин є позначеними. Потрібно розбити ці вершини на пари так, щоб не було двох пар, для яких шляхи між вершинами перетинаються.
Підвісимо дерево за довільну вершину. Знайдемо найнижчу вершину, для якої кількість позначених вершин у піддереві (включно з нею) більша за один. Тоді зрозуміло, що якщо кількість для цієї вершини є більшою за два, то відповіді не існує, адже хоча б два шляхи точно будуть проходити через цю вершину. Якщо ж ця кількість є рівною 2, то спаруємо ці вершини та видалимо їхні позначення. Цей процес потрібно повторювати, допоки залишаються позначені вершини.
Цей процес найкраще симулювати алгоритмом пошуку в глибину, де рекурсивна функція повертає позначену вершину, яка залишились у піддереві.