Задача Трекс-Пекс-Фекс (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.
Пример:
| Ввод | Вывод |
| 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)».