Обласна олімпіада 2021 - Тур 1 (розбір) | Статті

A. Знижка вiд уряду

Порахуємо ціну за дві пачки гречки без знижки — $2 \cdot a$, а зі знижкою — $b$. Отже, ми зекономимо $2 \cdot a - b$.

Код розв’язку C++

Код розв’язку Python

B. Степан на карантині

Пройдемо циклом по всіх областях, і якщо кількість хворих у відповідній області більша за межу «червоної» зони, тоді до відповіді додаємо одиницю.

Код розв’язку C++

Код розв’язку Python

C. Золотий злиток

Нехай $p_i$-е ребро злитка лежить уздовж $i$-ого ребра валізи. Тоді для всіх $i$ має виконуватися $a_{p_i} \le b_i$. Переберемо всі можливі перестановки $p$ та перевіримо, чи виконується ця умова хоча б для однієї з них.

Код розв’язку C++

Код розв’язку Python

D. Шифрування корупційних схем

Достатньо реалізувати алгоритм, описаний в умові — для кожної серії знайдемо її довжину, виведемо її розмір та сам символ.

Код розв’язку C++

Код розв’язку Python

E. Дешифрування корупційних схем

У рядку виділимо числа — довжини серій та літери — символи рядка. Кожен символ виведемо потрібну кількість разів.

Код розв’язку C++

Код розв’язку Python

F. Довідки

Використаємо підхід динамічного програмування, а саме $dp_i$ — максимальна відстань, яку Зенику потрібно буде пройти, за умови, що він має всі довідки від 1 до $a_i$ і стоїть у кабінеті $i$. Тоді перебравши наступний кабінет, у який завітає Зеник, можна порахувати відповідь для позиції $i$. Складність такого підходу — $O(n^2)$.

Можна показати, що для того, щоб максимізувати відстань, яку пройде Зеник, його варто відправити в крайній кабінет, який видає поточну довідку. Наприклад, якщо він зараз у кабінеті, де видають 2-гу довідку, тоді його відправлять або в найлівіший, або в найправіший кабінет, у якому видають 3-тю довідку. Складність у такому разі стає $O(n)$.

Код розв’язку C++

Код розв’язку Python

G. Велике крадівництво

Використаємо систему неперетинних множин.

Пройдемся по всіх ребрах графа $(u, v)$. Якщо вершини $u$ та $v$ належать різним компонентам зв’язності, то просто об’єднаємо їх. Якщо ж вони в одній компоненті, назвемо це ребро зайвим.

Пройдемося по всіх зайвих ребрах $(u, v)$. Якщо в графі є тільки одна компонента зв’язності, то задача розв’язана. Інакше, існує вершина $w$, що не зв’язна з $u$. Замінимо дорогу $(u, v)$ на $(u, w)$ та об’єднаємо компоненти, що містять вершини $u$ й $w$.

Зауважте, що оскільки $m \ge n$, відповідь завжди існує.

Код розв’язку C++

Код розв’язку Python