Темы --> Информатика --> Язык программирования
    Процедуры и функции(96 задач)
    Массивы(232 задач)
    Типы данных(356 задач)
    Циклы(177 задач)
    Условный оператор (if)(164 задач)
    Python(260 задач)
    Standard Template Library(2 задач)
---> 2 задач <---
Источники --> Личные олимпиады --> Нижегородская олимпиада школьников --> 2010
Страница: 1 Отображать по:
#3888
Автомат со сдачей
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Фирма, в которой всё ещё работает ваш друг, решила установить в своих маршрутках автоматы по продаже чая и кофе, чтобы во время поездок и, особенно, во время ожидания в пробках, пассажиры могли с толком провести время.

Стоимость стакана чая и кофе в автомате предполагается установить равной пяти рублям. Автоматы будут принимать монеты по 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
#3890
Шарики
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Фирма, в которой работает ваш друг, решила установить на конечной остановке своих маршруток большую абстрактную скульптуру со своим логотипом. Скульптура будет представлять собой прямоугольную сетку из \(N\) строк и \(M\) столбцов, в некоторых узлах которой будут располагаться разноцветные шары. Для обеспечения жёсткости конструкции шары, расположенные в узлах, соседних по вертикали, горизонтали или диагонали, необходимо соединить металлическими стержнями. Более строго, два шара должны быть соединены стержнем, если разность номеров строк, в которых расположены эти шары, не превосходит по модулю единицы, и разность номеров столбцов тоже не превосходит по модулю единицы.

Напишите программу, которая по заданному расположению шаров позволит определить, как будет выглядеть скульптура после установки стержней.

Входные данные

В первой строке входного файла находятся два натуральных числа \(N\) и \(M\) — размеры конструкции (\(1\leq N,M\leq 100\)). Далее следуют \(N\) строк по \(M\) символов в каждой. Каждый символ — это или “#” (решетка), обозначающий, что в соответствующем узле будет находиться шарик, или “.” (точка), обозначающий, что соответствующий узел будет пустой.

Выходные данные

Выведите в выходной файл \(2N-1\) строку по \(2M-1\) символов в каждой, изображающие как сами шары, так и соединяющие их стержни. А именно, в нечётных позициях нечётных строк выведите символ “#” или “.”, в зависимости от того, заполнен этот узел шариком или нет, а в остальных позициях выведите один из символов “ ” (пробел), “-” (минус), “|” (вертикальная палочка, ASCII #124), “/” (дробь, ASCII #47), “\” (обратный слеш, ASCII #92) или “X” (латинская заглавная буква X, ASCII #88), отражающий конфигурацию стержней в соответствующем месте структуры.

Если какая-то строка выходного файла должна заканчиваться на пробелы, их можно не выводить.

Примечание

Первый пример соответствует рисунку.

Примеры
Входные данные
3 4
##.#
#.##
####
Выходные данные
#-# . #
|/ \ /|
# . #-#
|\ /|X|
#-#-#-#
Входные данные
3 4
.#..
#.#.
.#..
Выходные данные
. # . .
/ \
# . # .
\ /
. # . .
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест