В одном известном всем городе скоро стартуют Зимние Олимпийские игры. В связи с этим организаторы игр решили провести эстафету Олимпийского огня — самую продолжительную и масштабную в истории Олимпийских игр. Эстафета состоит из N этапов, каждый длиной ai километров (1 ≤ i ≤ N). У организаторов имеется бесконечное количество олимпийских факелов, каждый из которых может непрерывно гореть на протяжении K километров забега. По правилам эстафеты каждый факел используется только один раз. В начале каждого этапа участникам эстафеты выдаётся некоторое число факелов, такое, чтобы олимпийский огонь удалось донести до конца этапа. По окончании этапа все использованные (полностью или частично) факелы передаются в дар своим факелоносцам.
В процессе подготовки эстафеты выяснилось, что последовательно идущие этапы можно объединить в один этап, и таким образом на проведение эстафеты потребуется меньше факелов. Однако по соображениям техники безопасности нельзя объединять больше, чем M подряд идущих этапов.
Напишите программу, которая по известной схеме эстафеты Олимпийского огня определяет, какое максимальное число факелов можно «сэкономить» и какие этапы для этого нужно объединить.
В первой строке заданы 3 натуральных числа N, M и K (N ≤ 106, M ≤ 10, K ≤ 108).
Во второй строке заданы N натуральных чисел ai (ai ≤ 109).
В первой строке выведите одно натуральное число F — на сколько можно максимально сократить количество используемых факелов на протяжении всей эстафеты.
Во второй строке выведите одно натуральное число P — количество групп объединённых этапов.
Затем в P строках выведите сами группы — по 2 натуральных числа si и ci, где si — номер первого этапа в группе, а ci — количество этапов в группе. Все si должны идти в порядке возрастания, а ci не превосходить M. Если существует несколько оптимальных решений, разрешается вывести любое.
5 3 3
1 1 1 3 3
2
1
1 3
6 3 3
1 1 1 1 1 1
4
2
1 3
4 3
5 5 2
2 4 6 8 10
0
0
Длина автомобильной дороги составляет N километров. Часть дороги необходимо отремонтировать. При обследовании дорога была разбита на N участков длиной 1 километр, и для каждого участка было определено, нуждается ли он в ремонте или нет, после чего был составлен план дороги, на котором отмечены участки, нуждающиеся в ремонте.
Для ремонта дороги можно привлечь несколько компаний-подрядчиков. Каждая компания может отремонтировать только непрерывный фрагмент дороги. При этом из-за требований антимонопольного законодательства длина фрагмента дороги, который ремонтирует одна компания, не должна превышать L километров (даже если на фрагменте, который ремонтирует одна компания, есть не нуждающиеся в ремонте участки, общая длина данного фрагмента не должна превышать L километров).
Определите, какое наименьшее количество компаний-подрядчиков необходимо привлечь для ремонта дороги.
Первая строка входных данных содержит целое число L ( L > 0 ) — максимальную длину фрагмента дороги, который может отремонтировать одна компания. Во второй строке входных данных записано целое число N ( N > 0 ) — длина всей дороги. Следующие N строк содержат по одному числу, равному 0 или 1. Число 1 обозначает, что соответствующий участок дороги нуждается в ремонте, число 0 — что участок не требует ремонта.
Программа должна вывести одно целое число — минимальное количество компаний-подрядчиков, которое необходимо привлечь для ремонта дороги.
В тесте из примера первая компания может отремонтировать участок номер 3, вторая компания — участки с 5 по 7.
Ограничения и система оценивания
Решение, правильно работающее в случае, когда числа L и N не превосходят 10, будет оцениваться в 30 баллов.
Решение, правильно работающее в случае, когда числа L и N не превосходят 1000, будет оцениваться в 60 баллов.
Решение, правильно работающее в случае, когда числа L и N не превосходят 10 5 , будет оцениваться в 100 баллов.
3 8 0 0 1 0 1 0 1 0
2
В игре Cookie Clicker игрок зарабатывает печеньки (cookies), щёлкая мышкой по изображению большой печеньки. Тратя заработанные печеньки, игрок может покупать различные усовершенствования (ферму, фабрику и т. д.), которые также производят дополнительные печеньки.
Рассмотрим упрощённый вариант этой игры. Пусть игрок может сделать один щелчок мышкой в секунду, что приносит ему одну печеньку. Также в любой момент времени игрок может потратить C печенек на покупку фабрики (при этом у игрока должно быть не меньше C печенек, после покупки фабрики количество его печенек моментально уменьшается на C ). Каждая купленная фабрика увеличивает ежесекундное производство печенек на P штук (то есть если у игрока одна фабрика, то он получает 1 + P печенек в секунду, две фабрики — 1 + 2 P печенек, три фабрики — 1 + 3 P печенек и т. д.). Игрок может приобрести неограниченное число фабрик стоимостью C печенек каждая. Фабрика начинает производить дополнительные печеньки сразу же, например, если после какой-то секунды игры у игрока стало C печенек, то игрок может купить фабрику и уже на следующей секунде его производство печенек увеличится на P штук.
Оригинальная игра никогда не заканчивается, но мы будем считать, что целью игры является набрать хотя бы N печенек. Определите минимальное время, за которое может быть достигнута цель игры.
Программа получает на вход три целых положительных числа, записанных в отдельных строках: С (стоимость фабрики), P (производительность одной фабрики) и N (необходимое количество печенек).
Программа должна вывести одно целое число — минимальное время в секундах, за которое игрок может получить не менее N печенек.
В первом тесте: через 50 секунд после начала игры у игрока будет 50 печенек, и он сможет купить фабрику. После этого он будет получать 4 печеньки в секунду, и на производство 100 печенек понадобится еще 25 секунд.
Во втором тесте: игрок сможет набрать 100 печенек за 100 секунд, при этом фабрику покупать нет смысла.
Ограничения и система оценивания
Решение, правильно работающее в случае, когда все входные числа не превосходят 1000, а для получения N печенек за минимальное время нужно приобрести не более одной фабрики, будет оцениваться в 30 баллов.
Решение, правильно работающее в случае, когда все входные числа не превосходят 1000, будет оцениваться в 70 баллов.
Решение, правильно работающее в случае, когда все входные числа не превосходят 10 9 , будет оцениваться в 100 баллов.
50 3 100
75
99 10 100
100
Даны три строки, состоящие из строчных латинских букв. С этими строками можно производить следующие операции: либо заменить один символ строки на два таких же символа (например, заменить символ «a» на «aa»), либо, наоборот, заменить два подряд идущих одинаковых символа на один такой же символ.
Необходимо при помощи этих операций сделать все три строки равными какой-то другой общей строке S либо определить, что это сделать невозможно. При этом нужно минимизировать общее количество операций.
Программа получает на вход три строки, состоящие из строчных букв латинского алфавита. Длина каждой строки не превышает 100 символов.
Если при помощи указанных операций возможно сделать все три строки равными, выведите такую строку S , что суммарное число операций, необходимых для преобразования всех трёх данных строк к строке S , будет минимальным. Если этого сделать нельзя, программа должна вывести одно слово IMPOSSIBLE (заглавными буквами).
Решение, которое выводит правильный ответ только на тестах из условия и тех тестах, на которых ответом является слово IMPOSSIBLE, будет оцениваться в 0 баллов.
aaaza aazzaa azzza
aazza
xy xxyy yx
IMPOSSIBLE