--->
177 задач
<---
Источники
Фирма, в которой всё ещё работает ваш друг, решила установить в своих маршрутках автоматы по продаже чая и кофе, чтобы во время поездок и, особенно, во время ожидания в пробках, пассажиры могли с толком провести время.
Стоимость стакана чая и кофе в автомате предполагается установить равной пяти рублям. Автоматы будут принимать монеты по 5 и 10 рублей, а также купюры в 10, 50 и 100 рублей. Когда пассажиру надо выдавать сдачу (т.е. когда пассажир бросил в автомат десятирублёвую монету или 10-, 50- или 100-рублёвую купюру), автомат выдаёт сдачу пятирублёвыми монетами; если же пассажир бросил в автомат пятирублёвую монету, то автомат её сохраняет и может использовать для сдачи следующим пассажирам.
Ясно, что, чтобы обеспечить возможность выдачи сдачи всем покупателям, может потребоваться изначально загрузить в автомат некоторое количество пятирублёвых монет. Сейчас на маршрутках фирмы проходят испытания с целью определить минимальное количество монет, которые надо загрузить в автомат перед выездом маршрутки в рейс. Вам дан протокол одного из таких испытаний: известен порядок, в котором пассажиры оплачивали свои покупки различными монетами и купюрами. Определите, какое минимальное количество пятирублёвых монет должно было изначально находиться в автомате, чтобы всем пассажирам хватило сдачи.
В первой строке входного файла находится одно натуральное число \(N\) — количество покупок в автомате, которые были совершены в ходе испытания (\(1\leq N\leq 50\,000\)). Во второй строке находятся \(N\) натуральных чисел, каждое из которых равно номиналу монеты или купюры, которую использовал очередной покупатель для оплаты; каждый номинал может принимать одно из четырёх значений: 5, 10, 50 или 100.
В выходной файл выведите одно число — минимальное количество пятирублёвых монет, которые надо было загрузить в автомат изначально, чтобы всем покупателям хватило сдачи.
В первом примере одна пятирублёвая монета потребуется для сдачи первому покупателю и 19 монет — третьему, но при сдаче третьему можно будет использовать ту монету, которую бросит второй покупатель, поэтому изначально в автомате достаточно 19 монет.
Во втором примере сдачу третьему покупателю можно выдать, используя монету первого или второго покупателя, и поэтому не требуется загружать монеты в автомат изначально.
В третьем примере первому же покупателю требуются девять монет сдачи, и все они должны изначально находится в автомате.
3 10 5 100
19
3 5 5 10
0
4 50 5 5 5
9
Дан массив целых чисел. Найти отрезок этого массива с максимальной суммой.
В первой строке дано натуральное число n ( 1 ≤ n ≤ 10 5 ) — размер массива. Во второй строке через пробел перечислены элемента массива. Числа не превышают 10 4 .
Выведите три числа — индекс начала отрезка, индекс конца и саму максимальную сумму. Массив индексируется с единицы. Если ответов несколько — выведите любой.
5 -1 2 3 -2 5
2 5 8
Для заданного натурального N найти последнюю ненулевую цифру числа N!.
Входной файл содержит число N (0 ≤ N ≤ 1 000 000).
Выходной файл должен содержать одну цифру — последнюю ненулевую.
8
2
10
8
Дорожка замощена плитками в один ряд, плитки пронумерованы числами от 1 до 1000. На плитках с номерами \(A\), \(B\) и \(C\) (\(A \lt B \lt C\)) сидят три кузнечика, которые играют в чехарду по следующим правилам:
1. На одной плитке может находиться только один кузнечик.
2. За один ход один из двух крайних кузнечиков (то есть с плитки \(A\) или с плитки \(C\)) может перепрыгнуть через среднего кузнечика (плитка \(B\)) и встать на плитку, которая находится ровно посередине между двумя оставшимися кузнечиками (то есть между \(B\) и \(C\) или \(A\) и \(B\) соответственно). Если между двумя оставшимися кузнечиками находится чётное число плиток, то он может выбрать любую из двух центральных плиток.
Например, если кузнечики первоначально сидели на плитках номер 1, 5, 10, то первым ходом кузнечик с плитки номер 10 может перепрыгнуть на плитку номер 3 (она находится посередине между 1 и 5), или кузнечик с плитки номер 1 может перепрыгнуть на плитку номер 7 или 8 (эти две плитки находятся посередине между плитками 5 и 10).
Даны три числа: \(A\), \(B\), \(C\). Определите, какое наибольшее число ходов может продолжаться игра.
Программа получает на вход три целых числа \(A\), \(B\) и \(C\) (\(1\le A \lt B \lt C\leq 1000\)), записанных в отдельных строках.
Выведите одно число — наибольшее количество ходов, которое может продолжаться игра.
1 4 6
2
В одном известном всем городе скоро стартуют Зимние Олимпийские игры. В связи с этим организаторы игр решили провести эстафету Олимпийского огня — самую продолжительную и масштабную в истории Олимпийских игр. Эстафета состоит из \(N\) этапов, каждый длиной \(a_i\) километров (\(1 \le i \le N\)). У организаторов имеется большое количество олимпийских факелов, каждый из которых может непрерывно гореть на протяжении \(K\) километров забега. По правилам эстафеты каждый факел используется только один раз. В начале каждого этапа участникам эстафеты выдаётся некоторое число факелов, такое, чтобы олимпийский огонь удалось донести до конца этапа. По окончании этапа все использованные (полностью или частично) факелы передаются в дар своим факелоносцам.
Напишите программу, которая по известной схеме эстафеты олимпийского огня, определяет необходимое суммарное количество факелов для проведения эстафеты.
В первой строке заданы два натуральных числа \(N\) и \(K\) (\(N \le 100, K \le 10^6\) ).
Во второй строке заданы \(N\) натуральных чисел \(a_i (a_i \le 10^6 )\).
В первой строке выведите одно натуральное число \(F\) — количество факелов, которое понадобится организаторам для проведения эстафеты олимпийского огня.
В данной задаче баллы за каждый тест начисляются независимо от прохождения остальных тестов и суммируются.
4 3 3 5 4 1
6
10 1 1 2 3 4 5 6 7 8 9 10
55