Ціна однієї канапки \(price = a + 2 \cdot b + c\). Отже відповідь до задачі це \(\lfloor \frac{s}{price} \rfloor\) (ділення націло).
Об’єм води за годину в Дністрі після \(i\)-того села — це сума об’єму води за
годину яка була в Дністрі до \(i\)-того
села та у всіх струмках які втікають безпосередньо перед \(i\)-тим селом. Таку суму потрібно
порахувати для кожного села. Зауважте, що об’єм води може перевищувати
розмір 32-бітного типу даних (для прикладу, int в C++),
тому для суми тут потрібно використовувати 64-бітний тип даних
(long long в С++).
Зауважимо, що рядок kanapka починається та закінчується
на підрядок ka. Щоб отримати два входження рядка
kanapka оптимально буде накласти початок другого входження
на кінець першого, отримавши рядок kanapkanapka. Щоб
отримати третє входження можна просто додати рядок napka і
отримати kanapkanapkanapka.
Формалізуємо алгоритм:
утворюємо один рядок
ka,поки можемо, дописуємо рядки
napkaдо кінця рядка.
Позначимо кількість символів k, a,
n та p — \(cntK\), \(cntA\), \(cntN\) та \(cntP\) відповідно.
Тоді максимальна кількість входжень буде рівна \(\min (cntK-1, \lfloor \frac{cntA - 1}{2} \rfloor,
cntN, cntP)\) якщо є хоча б по одному входженню букв
k та a.
Якщо ж в рядку немає букви k чи букви a, то
відповідь на задачу 0.
Очевидно, що Зенику варто піти або в супермаркет, або відвідати магазин кожного типу окремо, оскільки якщо Зеник відвідав супермаркет, то йому вже не потрібно йти ще в якийсь магазин. Отже задача зводиться до двох випадків: коли Зеник йде в супермаркет, або коли Зеник купує продукти у всіх магазинах окремо.
Розгляньмо випадок, коли Зеник йде до супермаркету. Оскільки ми хочемо мінімізувати відстань до координати 0, то варто вибрати супермаркет який найближчий до цієї координати. Тому нам потрібно вибрати такий супермаркет, в якого мінімальне значення \(|d_i|\). Це можна зробити за \(O(n)\).
Тепер розгляньмо випадок коли Зеник купує всі продукти в різних магазинах. Як порахувати відповідь коли ми маємо лише по одному магазину кожного типу? Знайдімо найправішу координату і найлівішу. Позначимо координати хлібного, м’ясного та сирного магазинів як \(a\), \(b\) та \(c\) відповідно. Легко зрозуміти що координата найлівішої точки це \(l = \min (a, b, c, 0)\), а найправішої \(r = \max (0, a, b, c)\). Щоб оптимально обійти їх нам потрібно спочатку піти в один бік, повернутися додому, піти в інший бік і знову повернутися додому. Отже відповідь для випадку магазинів різних типів буде \((|l| + r) \cdot 2\).
Що робити якщо магазинів багато? Ми можемо перебрати магазин кожного типу в який піде Зеник і таким чином знайти відповідь. Такий алгоритм праюватиме за \(O(n^3)\), що занадто повільно. Цей алгоритм легко оптимізувати.
Розглянемо магазини одного типу. Якщо є якісь два магазини з додатніми координатами, то нам ніколи не буде вигідно йти до магазину який знаходиться далі від нас, тому його не потрбіно перебирати. Аналогічні міркування справджуються і для магазинів з від’ємними координатами. В результаті, для кожного типу магазинів нас цікавлять лише два магазини: найближчий до нас з додатньою координатою і найближчий з від’ємною координатою. Після того як ми викинемо решту магазинів, всього їх залишиться не більше ніж 6: по 2 кожного типу. Тепер для кожного типу магазинів можемо перебрати до якого підемо, тому що різних таких комбінацій буде не більше ніж \(2 \cdot 2 \cdot 2 = 2^3 = 8\).
Відповідь на задачу це мінімум з двох випадків: або йдемо до найближчого супермаркета, або до кожного типу магазинів окремо.
Загальна складність алгоритму \(O(n + 2^3)\).