Задача Трекс-Пекс-Фекс (TREX)
Буратіно прийшов на Поле чудес, маючи P золотих монет та мішечок солі. Лисиця Аліса та кіт Базіліо повідомили йому, що якщо на цьому полі закопати T золотих монет (не обов’язково всі) і сказати заклинання «Трекс-пекс-фекс», то кількість монет подвоїться і можна буде викопати 2T золотих. Але якщо перед закопуванням T монет їх посолити, то після виголошення заклинання Буратіно викопає 2Т+1 монету. Буратіно має K порцій солі. Скільки разів потрібно сказати «Трекс-пекс-фекс», щоб отримати рівно S золотих?
Формат введення/виведення:
Програма TREX зчитує з клавіатури (стандартного пристрою введення) три цілих числа P, K, S (0≤K≤100, 0≤P,S≤109). Програма TREX виводить на екран число N – мінімальну кількість заклинань «Трекс-пекс-фекс», а потім N рядків, кожен з яких містить пару чисел – кількість закопаних монет та число «1» або «0». Одиниця виводиться, якщо золоті потрібно солити, і нуль – якщо ні. У випадку існування різних послідовностей дій Буратіно з мінімальною кількістю заклинань «Трекс-пекс-фекс» можна вивести будь-яку з них. Якщо отримати задану кількість монет неможливо, виводиться єдине число «−1».
Приклад:
|
Введення |
Виведення |
| 1 2 20 | 41 02 15 010 0 |
Задача Спам (SPAM)
Відомо, що на скриньку електронної пошти часто приходять листи рекламного характеру, листи зі шкідливими вкладеннями або посиланнями, які власник скриньки зовсім не очікував. Такі листи називаються спамом. У Васі є поштова скринька на одному з безкоштовних поштових серверів, і він, як усі нормальні люди, не любить спам. Розмір екрану обмежений і тому перша сторінка списку листів поштової скриньки не може відобразити всю пошту: Користувач пошти може бачити не більше M листів і, очевидно, це будуть найсвіжіші з них.Вася досить довго не перевіряв свою пошту і в його скринці накопичилося N листів, частина з яких є спамом. Якщо він бачить небажану пошту на першій сторінці, то виділяє всі спамерські листи, натискає кнопку «видалити», і виділені об'єкти переміщаються в папку «Видалені». Після цього на першій сторінці відображуються M найсвіжіших листів з решти і серед них може знову опинитися спам. У цьому випадку Вася знову виділяє небажану пошту і видаляє її зі скриньки описаним вище методом. Як тільки на першій сторінці перестане відображатися спам, Вася буде задоволений.
Формат введення/виведення:
Програма SPAM спочатку зчитує з клавіатури (стандартного пристрою введення) два цілих числа N і M (1≤N≤200000, 1≤M≤100000). Далі зчитується рядок, що містить N чисел (0 або 1), які визначають тип листа (1 – спам, 0 – ні) в порядку від найсвіжіших до найдавніших. Програма SPAM виводить на екран два цілих числа – кількість листів, що будуть видалені, та кількість натискань на кнопку «видалити».
Приклад:
|
Введення |
Виведення |
| 10 40 1 1 0 1 1 0 1 0 1 | 5 3 |
Задача СумRMQтор (SUMRMQ)
Заповітною мрією винахідника Ніколя Барузова було створення машини (еремк’ютера), основною функцією якої буде генерування послідовності випадкових чисел. Послідовність генерується наступним чином: перше число послідовності дорівнює X1, а кожне наступне обчислюється за формулою , де X1, A, B и q – задані цілі числа.Далі Ніколя задався такою метою: розширити застосування еремк’ютера ввівши виконання ним додаткової функції – пошук мінімального значення у згенерованій послідовності. В процесі тестування виявилося, що еремк’ютер-мінімізатор знаходить мінімум з K послідовно розташованих елементів. Тепер Ніколя удосконалює свою машину таким чином, що для заданої послідовності з N елементів знаходяться мінімуми для всіх можливих числових відрізків довжиною K (відрізок складають елементи, розміщені підряд), а потім обчислюється їх сума. Ваша задача написати програму, яка перевіряє правильність роботи машини шляхом підрахунку вказаної суми.Формат введення/виведення:Програма SUMRMQ зчитує з клавіатури шість цілих чисел, розділених пробілом N, K, X1, A, B та q (3≤K≤N≤107, K≤106, 0≤A,B,X1≤109, 0≤q≤30). Програма повинна вивести одне число – суму мінімумів на всіх відрізках довжини K.Приклад:
Пояснення до тесту: Згенерована послідовність 2 19 8 17 30 31Отримана сума 65=2+8+8+17+30
Формат введення/виведення:|
Введення |
Виведення |
| 6 2 2 5 9 5 | 65 |
Задача Автомагістраль (HIGHWAY)
Пан Бізнесюк збирається у ділову поїздку з рідної Логарифмічної області країни Олімпія у далеке місто Експоненціальськ, причому їхати він буде власним мерседесом. Автомагістраль, що з’єднує Логарифмічну область з Експоненціальськом, складається з N послідовних фрагментів. Всередині кожного фрагменту можна їхати або по безплатній дорозі, витрачаючи ai секунд, або по платній, витрачаючи ci олімпійських центів та bi секунд. Між цими фрагментами є транспортні розв’язки, через які можна з’їхати з однієї дороги на іншу. Такі переміщення вимагають qi секунд (без різниці, з платної дороги на безплатну чи з безплатної на платну). При продовженні руху по тій самій дорозі таких затримок не виникає. Розпочати та завершити рух можна як по платній так і безплатній дорозі, тому розв’язки є лише між першим та другим, другим та третім, …, (N–1)-м та N-м фрагментами.Пан Бізнесюк давно знає гасло «час – це гроші» і на даний момент оцінює одну секунду свого часу у K олімпійських центів, а тому пана Бізнесюка цікавить мінімізація величини P + K · T, де P – загальна сума сплачених дорожніх зборів, T – загальний витрачений час, зміст величини K пояснений у попередньому реченні.
Програма HIGHWAY зчитує з клавіатури у першому рядку два цілих числа N (2≤N≤60) та K (0≤K≤2012). Далі у другому рядку зчитується три цілих числа a1, b1 та c1 – час руху по безплатній та платній дорогах першого фрагменту та ціна проїзду по платній дорозі. У кожному з наступних N–1 рядків зчитується по чотири цілі числа qi, ai, bi та ci – час на переміщення між дорогами, час руху по безплатній та платній дорогах цього фрагменту і ціна проїзду по платній дорозі відповідно. Усі значення ai, bi та ci (1≤i ≤N) у межах від 1 до 1012. Усі значення qi (2≤i ≤N) у межах від 0 до 109.
Приклад:
|
Введення |
Виведення |
| 5 7795 17 100004 41 17 10003 23 17 1002 17 17 101 15 17 1 | 13892 |
Пояснення: Для даного прикладу, мінімум величини P + 77T досягається при P = 1110, T = 166 на маршруті «безплатна (час 95), зміна дороги (час 4), платна (час 17, плата 1000), платна (час 17, плата 100), платна (час 17, плата 10), зміна дороги (час 1), безплатна (час 15)».