Порахуємо ціну за дві пачки гречки без знижки — \(2 \cdot a\), а зі знижкою — \(b\). Отже, ми зекономимо \(2 \cdot a - b\).
Пройдемо циклом по всіх областях, і якщо кількість хворих у відповідній області більша за межу «червоної» зони, тоді до відповіді додаємо одиницю.
Нехай \(p_i\)-е ребро злитка лежить уздовж \(i\)-ого ребра валізи. Тоді для всіх \(i\) має виконуватися \(a_{p_i} \le b_i\). Переберемо всі можливі перестановки \(p\) та перевіримо, чи виконується ця умова хоча б для однієї з них.
D. Шифрування корупційних схем
Достатньо реалізувати алгоритм, описаний в умові — для кожної серії знайдемо її довжину, виведемо її розмір та сам символ.
E. Дешифрування корупційних схем
У рядку виділимо числа — довжини серій та літери — символи рядка. Кожен символ виведемо потрібну кількість разів.
Використаємо підхід динамічного програмування, а саме \(dp_i\) — максимальна відстань, яку Зенику потрібно буде пройти, за умови, що він має всі довідки від 1 до \(a_i\) і стоїть у кабінеті \(i\). Тоді перебравши наступний кабінет, у який завітає Зеник, можна порахувати відповідь для позиції \(i\). Складність такого підходу — \(O(n^2)\).
Можна показати, що для того, щоб максимізувати відстань, яку пройде Зеник, його варто відправити в крайній кабінет, який видає поточну довідку. Наприклад, якщо він зараз у кабінеті, де видають 2-гу довідку, тоді його відправлять або в найлівіший, або в найправіший кабінет, у якому видають 3-тю довідку. Складність у такому разі стає \(O(n)\).
Використаємо систему неперетинних множин.
Пройдемся по всіх ребрах графа \((u, v)\). Якщо вершини \(u\) та \(v\) належать різним компонентам зв’язності, то просто об’єднаємо їх. Якщо ж вони в одній компоненті, назвемо це ребро зайвим.
Пройдемося по всіх зайвих ребрах \((u, v)\). Якщо в графі є тільки одна компонента зв’язності, то задача розв’язана. Інакше, існує вершина \(w\), що не зв’язна з \(u\). Замінимо дорогу \((u, v)\) на \((u, w)\) та об’єднаємо компоненти, що містять вершини \(u\) й \(w\).
Зауважте, що оскільки \(m \ge n\), відповідь завжди існує.