Завдання другого туру NetOI-2022
Розв'язки надіслати до 0 годин 30.12.22. Реєстрація учаксників продовжується.
Задача Discount. Відвідавши перед Різдвом великий магазин, ви обрали багато подарунків рiдним та друзям. Зекономити певну кількість грошей вам можуть допомогти два типи знижок, що дають у магазина:
1. при купівлі 3-х товарів, Ви платите за них як за 2 найдорожчих з них;
2. при купівлі 5-и товарів, Ви платите за них як за 3 найдорожчих з них.
Таким чином, певнi товари можна об’єднати у трійки або п’ятірки i заплатити за них менше. Треба визначити найменшу можливу суму грошей, яка буде витрачена на придбання усіх подарунків.
Напишуть програму, що за цінами усіх подарунків, знаходить мінімальну суму грошей, якої вистачить на їх купівлю.
Технічні умови. Програма Discount читає з пристрою стандартного введення ціле число N (1⩽ N⩽123456). Другий рядок містить N натуральних чисел — ціни подарунків. Сума цін усіх подарунків менша за 1018. Об’єднувати можна не лише ті товари, що йдуть підряд у вхідних даних.
Програма виводить на пристрій стандартного виведення єдине число — знайдену мінімальну суму грошей, за яку можна купити усі подарунки.
Приклад
|
Введення |
Виведення |
|
5 50 80 50 100 20 |
230 |
Коментар. Якщо ціни п’яти обраних подарунків складають: 50, 80, 50, 100, 20, то можна з них усіх скласти п’ятірку й отримати за них знижку: два найдешевші товари (20+50=70) дістануться безкоштовно, сплатити треба лише за решту. Загалом вся покупка буде коштувати 80+50+100=230 грошових одиниць, замість 300.
Задача Presents2022. Василько чекає різдвяні подарунки! Від друзів та родичів він чекає чотири подарунки з тим, щоб однаковими були вартості тільки двох подарунків.
Василько гарний математик та програміст. Він вирішив визначити для довільної суми вартості подарунків n кількість їх варіантів. Допоможіть йому.
Технічні умови. Програма Presents2022 читає з пристрою стандартного введення єдине число n
(0≤n≤3·109). Програма виводить на пристрій стандартного виведення єдине число – шукану кількість варіантів.
Приклади
Введення 7
Виведення 1
Введення 19
Виведення 30
Коментар. Єдина комбінація для першого прикладу 1+1+2+3.
Задача Newbrackets2022. Правильна послідовність дужок утворюється за такими правилами:
- ( ),[ ],{ } – правильні;
- якщо а – правильна послідовність, і b – правильна, то ab правильна;
- Якщо а – правильна, то (а), [а], {а} – теж правильні.
Дано послідовність дужок. Яку мінімальну кількість дужок (відкритих чи закритих) треба вставити в дану послідовність, аби отримати правильну послідовність?
Технічні умови. Програма Newbrackets2022 читає з пристрою стандартного введення стрічку, яка складається виключно зрізних дужок довжиною не більше 103 символів. Програма виводить на стандартний пристрій виведення одну величину – шукану кількість дужок.
Приклади
Введення ))((
Виведення 4
Введення (())
Виведення 0
Задача Npolygon
Якось до Петра в гості завітав його друг Семен. Вони разом готувалися до олімпіади з усного рахунку, а тому постійно додавали всі числа, які тільки бачили. Марічка вирішила допомогти друзям та намалювала N-кутник, до кожної з вершин якого приписала число. Семен, побачивши зображення, запропонував додавати не всі числа, а тільки k (1 < k < N), що йдуть підряд за годинниковою стрілкою. Петро запропонував не всім вершинам многокутника приписувати одне й те саме число. Друзі з подивом помітили, що при цьому іноді суми отримуються однаковими для всіх вершин. Вони позначили S(i,k) як суму чисел в k послідовних вершинах, починаючи з вершини i. Друзі вирішили знайти максимальне k, при якому всі такі суми рівні.
Технічні умови. Програма Npolygon зчитує з стандартного пристрою введення єдине ціле число N кількість кутів N-кутника (3 ≤ N ≤ 1015).
Програма виводить на стандартний пристрій виведення єдине число k (1 < k < N) – максимальну кількість чисел, що розташовані підряд за годинниковою стрілкою, серед яких хоча б два різних, таких, що для всіх i S(i,k) рівні між собою. Якщо таку послідовність чисел у заданого N-кутника написати немає можливості, виведіть «-1» (без лапок).
Приклад
|
Введення |
Виведення |
|
6 |
4 |
|
9 |
6 |
Задача Fixcandy
Для учасників олімпіади з інформатики організатори вирішили провести екскурсію на кондитерську фабрику концерну ROSVEN. Їм показали, як виконує упаковку фасувально-пакувальний автомат, який має N резервуарів, у кожен з яких кожну секунду потрапляє рівно одна цукерка. Цукерки пакуються рівно по k штук у коробці, а тому, як тільки в одному з резервуарів трапляється вказана кількість цукерок, вони відправляються на упаковку і резервуар стає пустим. Далі заповнення резервуару починається спочатку.
Коли олімпієць Петро почав спостерігати, в кожному резервуарі автомата знаходилась деяка кількість цукерок і захотів спробувати фасувати . Йому довірили виготовити не менше L коробок по k цукерок, а після виконання завдання звільнити всі резервуари від цукерок, що залишилися. Власник концерну, що супроводжував екскурсантів, почувши це, жахнувся, прекрасно розуміючи, що звільнення резервуарів перетвориться у процедуру з’їдання цукерок. А це означало, що концерн понесе збитки, яких власник не любив, бо був дуже скупий….
Поки Петру пояснювали, що той повинен робити, власник звернувся по допомогу до інших олімпійців: мінімізувати кількість цукерок, що їх зможе з’їсти Петро. А для цього потрібно визначити, за який мінімальний час Петро гарантовано виконає (а може, і перевиконає) завдання, а кількість цукерок у резервуарах залишиться мінімально можливою.
Технічні умови. Програма Fixcandy спочатку зчитує з стандартного пристрою введення три цілих числа N, K, L (1≤N≤106, 1≤K≤109, 0≤L≤109). Потім зчитується N невід’ємних цілих чисел a1, a2 ,… aN строго менших К – кількість цукерок у кожному з резервуарів автомата перед початком роботи.
Програма виводить на екран (стандартний пристрій виведення) одне число – мінімальну тривалість зміни, при якій гарантовано виконано завдання і при якій Петро, на радість власнику, з’їсть мінімальну кількість цукерок.
Приклад
|
Введення |
Виведення |
|
3 3 2 1 1 2 |
2 |
Примітка: В момент часу 0 (початок зміни) у резервуарах знаходиться (1, 1, 2) цукерок.
0 сек: (1, 1, 2)
1 сек: (2, 2, 0) => 1 упаковка
2 сек: (0, 0, 1) => 2 упаковки, всього 3
Таким чином, на другій секунді завдання вже виконано, а сума цукерок, яку потрібно з’їсти, мінімальна.
Завдання підготували Й. Ентін, Г. Непомнящий, Ю. Пасіхов, І. Порубльов