У задачі необхідно вивести 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\), то ми знайшли відповідь. Інакше, відповіді не існує.
Неважко побачити, що задача зводиться до такої — знайти максимальну кількість точок, які можна вибрати на лінії так, аби виконувалися такі умови.
Для кожної компанії був хоча б один варіант вибору кінцевої точки, який би не проходив через жодну з вибраних.
Між кожною парою сусідніх вибраних точок має бути хоча б одна компанія.
Це зведення означає, що ми виділяємо максимальну кількість точок-розділювачів, через які не можуть проходити ремонтні роботи, в той час як між ними має бути хоча б одна. Зрозуміло, що максимізація цього числа є еквівалентною максимізації кількості проміжків, яку просять в умові.
Таку зведену задачу легко розв’язати методом динамічного програмування. Введемо стан — координата останньої вибраної точки — і для цього стану будемо максимізовувати загальну кількість уже вибраних точок. Для переходу з такого стану переберемо наступну вибрану точку справа від поточної. Залишається лише перевірити, чи коректним є такий перехід, а саме, чи існує хоча б одна компанія між цими точками, а також, чи кожна з них «поміститься» між цими точками.