У задачі необхідно вивести 47-ий день заданого року. Таким днем
кожного року є 16 лютого. Відповідно для розв’язку задачі достатньо
просто вивести рядок 16.02. і потім номер року, який треба
зчитати з вводу.
За умовою задачі потрібно згенерувати перестановку n чисел так, щоб в ній було рівно k локальних мінімумів (чисел, сусіди якого більші за саме число), або сказати, що цього зробити не можна.
Зрозуміло, що неможливо зробити більше ніж n−12 локальних мінімумів. Тому у
випадках, коли k>n−12, виведемо -1.
Щоб створити локальний мінімум у перестановці, нам достатньо просто поміняти місцями два сусідні числа у зростаючій послідовності. Щоб створити k локальних мінімумів просто зробимо k таких операцій. Наприклад:
1234567→1⇔23⇔45⇔67→2143657
Очевидно, що аби з рядка s можна було утворити t, потрібно аби t був підпослідовністю s. Для того щоб це перевірити, достатньо пройти циклом по рядку t, підтримуючи вказівник на відповідне входження такого ж символу в s. При переході до наступного символу в t потрібно сунути вказівник s, допоки не знайдеться відповідний символ. Якщо вказівник прийшов у кінець рядка, і шуканий символ не був знайдений — підпослідовності не існує.
Після того як відомо, чи можна із s утворити t, потрібно визначити мінімальну кількість кроків, необхідну для цього. Єдиним обмеженням є той факт, що не можна видаляти більше ніж два однакові символи в межах одного кроку. З цього випливає, що цю кількість можна окремо порахувати для кожної букви, а потім знайти максимальне значення. Зрозуміло, що якщо певну букву потрібно видалити x разів, то кількість кроків для цього — це ⌈x2⌉ (заокруглене вгору).
У задачі задано послідовність із 4 і 7. За одну операцію можна видалити якийсь елемент з послідовності й додати до рахунку суму лівого й правого сусідів. Треба видалити всі елементи, крім першого й останнього, максимізувавши рахунок.
Задача розв’язується жадібно. Спочатку будемо видаляти четвірки, які є сусідами з хоча б однією сімкою, поки не видалимо всі четвірки (це завжди можна зробити за умови якщо присутня хоча б одна сімка). Потім видалимо всі сімки в такому порядку, щоб кожна сімка, яку ми видаляємо, сусідила з двома іншими сімками. Коректність такого підходу легко бачити, якщо розглянути еквівалентну задачу, у якій замість 4 і 7 є 0 і 1.
Реалізувати такий алгоритм можна, використовуючи структуру даних стек. Проходимося по послідовності зліва направо й кладемо елементи на стек. Якщо пробуємо поставити 7 на 4, то видаляємо 4. Якщо ставимо 4 на 7, то видаляємо 4 (не ставимо на стек). У результаті залишиться послідовність із сімок, яку треба опрацювати окремо.
За умовою задачі потрібно вивести координати центру кола певного радіусу, яке падає з точки (x,∞) після того, як воно торкнеться прямої y=0 або іншого кола. Якщо коло не дотикається до інших, то відповідь для нього — (x,r). Якщо ж дотикається — потрібно знайти найвищу точку (x,y), де відбувається дотик. Для цього просто переберемо всі кола, що вже зупинилися, і спробуємо знайти точку, у якій ми будемо до такого кола дотикатися.
Знайти таку точку дуже просто. У момент дотику відстань між центрами двох кіл рівна сумі їхніх радіусів. Координати x центрів кожного з кіл нам відомі спочатку. За теоремою Піфагора можемо визначити, що (y−yi)2=(r+ri)2−(x−xi)2. Найбільше значення y і буде шуканою координатою y центра кола, що падає. Варто також звернути увагу на те, що для того, щоб коло зупинилося, відстань між центрами кіл має бути строго меншою за суму їхніх радіусів.
У задачі задано граф, у якому деякі ребра мають вагу, а деякі — ні. Необхідно зважити всі ребра, щоб найкоротша відстань між першою і останньою вершинами була рівна заданому числу w.
У першій підзадачі, яка вартувала 10 балів, усі ребра початково не мали ваги. Для того щоб розв’язати цю підзадачу, достатньо знайти шлях між першою і останньою вершинами, на якому є найменша кількість ребер, наприклад, алгоритмом пошуку вшир (BFS). Нехай ця кількість рівна k. Тоді якщо k>w, то відповіді не існує. Інакше вона завжди існує і її можна досягнути, наприклад, так: всім ребрам не на найкоротшому шляху дамо вагу w, усім ребрам, окрім одного на шляху, дамо 1, а останньому дамо w−k. У такий спосіб будь-який шлях, окрім найкоротшого, буде мати вагу не меншу за w, а найкоротший буде мати вагу рівно w.
Для того щоб розв’язати задачу повністю, спершу зробимо, щоб усі ребра без ваги мали вагу 1. Знайдемо найкоротшу відстань між першою і останньою вершинами, наприклад, алгоритмом Дейкстри. Якщо вона перевищує w, то відповіді не існує.
Тепер будемо перебирати всі ребра, які треба зважити, в довільному порядку і для кожного з них повторимо такий процес. Знайдемо найкоротшу відстань між першою і останньою вершиною. Нехай ця відстань рівна d. Додамо до ваги поточного ребра значення w−d (це значення завжди буде невід’ємне).
Після того як опрацюємо всі ребра, ще раз знайдемо найкоротшу відстань між першою і останньою вершинами. Якщо вона рівна w, то ми знайшли відповідь. Інакше, відповіді не існує.
Неважко побачити, що задача зводиться до такої — знайти максимальну кількість точок, які можна вибрати на лінії так, аби виконувалися такі умови.
Для кожної компанії був хоча б один варіант вибору кінцевої точки, який би не проходив через жодну з вибраних.
Між кожною парою сусідніх вибраних точок має бути хоча б одна компанія.
Це зведення означає, що ми виділяємо максимальну кількість точок-розділювачів, через які не можуть проходити ремонтні роботи, в той час як між ними має бути хоча б одна. Зрозуміло, що максимізація цього числа є еквівалентною максимізації кількості проміжків, яку просять в умові.
Таку зведену задачу легко розв’язати методом динамічного програмування. Введемо стан — координата останньої вибраної точки — і для цього стану будемо максимізовувати загальну кількість уже вибраних точок. Для переходу з такого стану переберемо наступну вибрану точку справа від поточної. Залишається лише перевірити, чи коректним є такий перехід, а саме, чи існує хоча б одна компанія між цими точками, а також, чи кожна з них «поміститься» між цими точками.