Порахуємо ціну за дві пачки гречки без знижки — 2⋅a, а зі знижкою — b. Отже, ми зекономимо 2⋅a−b.
Пройдемо циклом по всіх областях, і якщо кількість хворих у відповідній області більша за межу «червоної» зони, тоді до відповіді додаємо одиницю.
Нехай pi-е ребро злитка лежить уздовж i-ого ребра валізи. Тоді для всіх i має виконуватися api≤bi. Переберемо всі можливі перестановки p та перевіримо, чи виконується ця умова хоча б для однієї з них.
D. Шифрування корупційних схем
Достатньо реалізувати алгоритм, описаний в умові — для кожної серії знайдемо її довжину, виведемо її розмір та сам символ.
E. Дешифрування корупційних схем
У рядку виділимо числа — довжини серій та літери — символи рядка. Кожен символ виведемо потрібну кількість разів.
Використаємо підхід динамічного програмування, а саме dpi — максимальна відстань, яку Зенику потрібно буде пройти, за умови, що він має всі довідки від 1 до ai і стоїть у кабінеті i. Тоді перебравши наступний кабінет, у який завітає Зеник, можна порахувати відповідь для позиції i. Складність такого підходу — O(n2).
Можна показати, що для того, щоб максимізувати відстань, яку пройде Зеник, його варто відправити в крайній кабінет, який видає поточну довідку. Наприклад, якщо він зараз у кабінеті, де видають 2-гу довідку, тоді його відправлять або в найлівіший, або в найправіший кабінет, у якому видають 3-тю довідку. Складність у такому разі стає O(n).
Використаємо систему неперетинних множин.
Пройдемся по всіх ребрах графа (u,v). Якщо вершини u та v належать різним компонентам зв’язності, то просто об’єднаємо їх. Якщо ж вони в одній компоненті, назвемо це ребро зайвим.
Пройдемося по всіх зайвих ребрах (u,v). Якщо в графі є тільки одна компонента зв’язності, то задача розв’язана. Інакше, існує вершина w, що не зв’язна з u. Замінимо дорогу (u,v) на (u,w) та об’єднаємо компоненти, що містять вершини u й w.
Зауважте, що оскільки m≥n, відповідь завжди існує.