Обласна олімпіада 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