Завдання 2-го туру NetOI-2018. Розв'язки надсилати до 0 годин 30 грудня 2018 року
Задача Treats. Василь Пупкін вирішив організувати олімпіаду по стрибкам в ширину. Він отримав n коробок з призами від спонсора. Кожна коробка містить різні призи, але в кожній коробці призи однакові. З накладної відомо, що в i-й коробці міститься mi однакових призів. Василь вирішив нагородити команду, що перемогла. Команда може отримати не меньше a призів, та не більше ніж b призів. Тепер перед Василем постає питання: скільки дати призів команді-переможцю та яких? Ваша задача підрахувати скількома способами він може розподілити призи.
Технічні умови. Програма Treats читає в одному рядку три цілих числа: n, a та b, що розділені одним пропуском(1≤n≤10, 0≤a≤b≤10 000 000). Кожне з наступних n цілих чисел такі, що i+3 число - це mi – кількість цукерок в i-му пакунку. (0≤mi≤1000000). Програма виводить на пристрій стандартного виведення k mod 109+7 (залишок від ділення кількості способів на 109+7
Приклад
Введення
2 1 3 3 5
Виведення
9
Коментар. Призи можна розподілити такими способами:
(1,0),(2,0),(3,0),(0,1),(0,2),(0,3),(1,1),(1,2),(2,1)
--------------
Задача Tickets2018. За квитками на концерт гурту «Золоті роги» вишикувалася черга з N фанатів, кожен з яких хоче купити 1 квиток. На всю чергу працювала лише одна каса, тому продаж квитків йшов дуже повільно. І це дратувало фанатів гурту, що стояли в черзі. Найкмітливіші швидко помітили, що кілька квитків в одні руки касир продає швидше, ніж коли ці ж квитки продаються по одному. Тому вони надумали передавати гроші першому з них, щоб він купив квитки на всіх. Однак для боротьби зі спекулянтами касир продавала не більше 3-х квитків в одні руки, тому домовитися таким чином між собою могли лише 2 або 3 фанати, що стоять поспіль. Відомо, що на продаж i-ій людині з черги одного квитка касир витрачає Ai секунд, на продаж двох квитків - Bi секунд, трьох квитків - Ci секунд. Напишіть програму, яка підрахує мінімальний час, за який могли б придбати квитки всі фанати. Зверніть увагу, що квитки на групу фанатів завжди купує перший з них. Також ніхто купує зайвих квитків (тобто квитків, які нікому не потрібні).
Технічні умови. Програма Tickets2018 читає з пристрою стандартного введення число N - кількість покупців в черзі (1≤N≤5000). Далі йде N трійок натуральних чисел Ai, Bi, Ci. Кожне з цих чисел не перевищує 3600. Люди в черзі нумеруються починаючи від каси. Програма виводить на пристрій стандартного виведення єдине число - мінімальний час в секундах, за який всі могли б придбати квитки.
Приклади:
Введення
5
5 10 15
2 10 15
5 5 5
20 20 1
20 1 1
Виведення
12
Введення
2
3 4 5
1 1 1
Виведення
4
---------------
Задача Кepler. У планетарній системі Пупкін-2018 три планети обертаються в одному напрямку навколо світила. Для зручності астрономи поділили орбіти на N однакових сегментів. Для кожної планети відомо, скільки сегментів вона долає за один земний рік. Парадом планет назвемо ситуацію, при якій усі три планети та зірка розташовані на одній прямій. Відомо, що зараз відбувається парад планет, при цьому зараз всі планети розташовані по один бік від світила (див. малюнок). Чи можливо таке, що через цілу кількість земних років від цього «параду» станеться новий «парад планет»? Якщо так, то через скільки років станеться найближчий парад планет?
Технічні умови. Програма Кepler читає з пристрою стандартного введення число N <= 109- кількість сегментів а далі в цьому ж рядку через пропуски числа A, B, C - кількість сегментів, що долає кожна з планет за один земний рік (1<=A,B,C<=109) Програма виводить на пристрій стандартного виведення цілу кількість земних років, через яку відбудеться парад планет. Якщо таке не можливо, вивести -1
Приклад:
Введення
2 1 2 3
Виведення
1
----------------
Задача Minbus. Службовий автобус робить один рейс за встановленим маршрутом і в разі наявності вільних місць підбирає робітників, які очікують на зупинках, і відвозить їх на завод. Автобус також може чекати на зупинці робітників, які ще не прийшли. Відомо час приходу кожного робітника на свою зупинку і час проїзду автобуса від кожної зупинки до наступної. Автобус приходить на першу зупинку в нульовий момент часу. Тривалість посадки робітників в автобус вважається нульовою. Потрібно написати програму, яка визначить мінімальний час, за який автобус привезе максимально можливу кількість робітників.
Технічні умови. Програма Minbus читає з пристрою стандартного введення в першому рядку кількість зупинок N і кількість місць в автобусі M. Кожен i-й рядок з наступних N рядків містить ціле число - час руху від зупинки і до зупинки i + 1 (N + 1 -а зупинка - завод), кількість робітників K, які прийдуть на i-ую зупинку, і час приходу кожного робітника на цю зупинку в порядку приходу (1≤M≤2000, 1≤N, K≤200000). Програма виводить на пристрій стандартного виведення єдине число – шукану величину, тобто мінімальний час, за який можна перевезти максимальну кількість робітників.
Приклад
Введення
3 5
1 2 0 1
1 1 2
1 4 0 2 3 4
Виведення
4
-------------
Задача Gardener. Як відомо, найкращі натуральні парфуми роблять з живих квітів. Вирощуванням найкращих квітів займаються на підприємстві ''Flowers''. Але квіти досить вибаглива рослина. Квітники в якому вони ростуть мають форму великих прямокутних паралелепіпедів. І, якщо, в ній вже ростуть квіти, то для того, щоб нову квітку можна було б посадити в цей квітник та вона могла б прижитись потрібно, щоб вона мала б колір точно такий як і у більшості квіток цього квітника. За умови, що кількості квіток, які знаходяться в абсолютній більшості у даному квітнику можуть бути однаковими, то у квітник потрібно посадити квітку екзотичного кольору, що позначається числом 0.
Допоможіть садівнику підприємства, що займається розсадкою квітів для конкретного замовлення парфумерних компаній, написати програму, яка допоможе визначити якого кольору має бути квітка, для того щоб її можна було посадити у конкретний квітник.
Технічні умови. Програма Gardener читає з пристрою стандартного введення ціле число 1=<n=<1000000 а далі в тому ж рядку через пропуски n (1≤с≤100) чисел - кольори квіток, що вже ростуть у даному квітнику. Програма виводить на пристрій стандартного виведення одне число – номер кольору квітки, яку можна посадити у квітник. Зауважимо, що колір екзотичної квітки 0.
Приклад:
Введення:
10 2 3 3 5 2 5 6 2 3 4
Виведення:
0
Завдання підготоували В. Ветров, Г. Непомнящий, Ю.Пасіхов, М. Стречень