Темы --> Информатика --> Язык программирования
    Процедуры и функции(96 задач)
    Массивы(232 задач)
    Типы данных(356 задач)
    Циклы(177 задач)
    Условный оператор (if)(164 задач)
    Python(260 задач)
    Standard Template Library(2 задач)
---> 4 задач <---
Источники --> Личные олимпиады --> Нижегородская олимпиада школьников
    2009(6 задач)
    2010(6 задач)
    2011(6 задач)
    2012(6 задач)
    2013(6 задач)
    XI Нижегородская городская олимпиада по информатике им. В. Д. Лелюха, 2015г.(6 задач)
    XII Городская олимпиада школьников по информатике им. В. Д. Лелюха, 2016 г.(6 задач)
Страница: 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
.#..
#.#.
.#..
Выходные данные
. # . .
/ \
# . # .
\ /
. # . .
#3893
Переливание духов
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

... но нужен ли на самом деле кому-нибудь 6\(1\over7\)-пунктовый шрифт, который на три четверти — шрифт Baskerville, и на четверть — Helvetica?

Дональд Э. Кнут. Идея Мета-фонта1

Маленькая девочка Оля добралась до полки, на которой стоят флаконы с мамиными любимыми духами, и начала заниматься своим любимым занятием — переливанием жидкостей из одного флакона в другой. Когда наконец мама застала её за этим занятием, прекрасная коллекция духов была уже безнадёжно утрачена.

К счастью, Оля — аккуратная девочка, поэтому все свои действия она записывала на бумажку. Помогите ей успокоить маму: определите, каков состав духов в первом (мамином любимом) флаконе, чтобы мама смогла придумать этой смеси новое название и рассказывать всем, какие прекрасные духи она смогла сделать вместе с дочерью.

Считайте, что Оля не пролила ни одной капли, а также что она тщательно встряхивала флаконы после каждого переливания. Учтите, что в маминых флаконах порой не видно, есть ли там жидкость, и потому Оля иногда могла пытаться переливать духи из пустого флакона (в результате, естественно, ничего не переливалось). Вы можете также считать, что после каждого переливания в каждом флаконе каждый тип духов либо полностью отсутствует, либо содержится в объеме не меньшем чем \(10^{-10}\).

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

На первой строке входного файла находятся два числа \(N\) и \(M\) — количество флаконов и число типов маминых любимых духов соответственно (\(2 \leq N \leq 100\); \(1 \leq M \leq 100\)). Далее следуют \(N\) строк, на \(i\)-ой из которых находятся два числа — тип \(L_i\) и объем \(V_i\) духов, находившихся изначально в \(i\)-ом флаконе (\(1\leq L_i \leq M\); \(0 \leq V_i \leq 1000\)). Возможно, что в нескольких флаконах находились духи одного и того же типа; возможно, что какого-то типа вообще не было на полке.

Далее во входном файле следует строка с числом \(K\) — количеством совершённых переливаний (\(1 \leq K \leq 1000\)). За ней следуют \(K\) строк, на \(k\)-ой из которых находятся три числа \(S_k\), \(T_k\) и \(A_k\) — номера флаконов, откуда и куда переливала Оля при \(k\)-ом переливании, и количество перелитой жидкости (в процентах от количества жидкости в \(S_k\)-ом флаконе перед переливанием). Гарантируется, что \(1\leq S_k,T_k\leq N\), что \(S_k\neq T_k\), и что \(0\leq A_k\leq 100\). Все числа во входном файле целые.

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

В выходной файл выведите \(M\) чисел — процентное содержание всех видов духов (от первого до \(M\)-ого) в первом флаконе после последнего переливания. Выводите результат с точностью не меньше двух знаков после запятой. Гарантируется, что после последнего переливания первый флакон оказался непустым.

Примечание

1... but does anybody really need a 6\(1\over7\)-point font that is one fourth of the way between Baskerville and Helvetica? — Donald E. Knuth, The Concept of a Meta-Font

Примеры
Входные данные
3 2
1 100
2 200
1 500
2
3 2 20
2 1 50
Выходные данные
60.00 40.00
#111519
Праздничные дни
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

В Тридевятом царстве царь был любителем разных заморских традиций. Как прознает, что в другом царстве есть какой-то обычай, сразу думает, как бы его к тридевятым реалиям приспособить.

Вот неделю назад вернулось посольство из Тридесятого царства. И главный посол доложил царю: дескать, придумал Тридесятый царь следующую вещь. Чтобы как-то зарегулировать гуляния народные, повелел он указать определенные дни, и в эти дни устраивать широкие гуляния, а в остальные дни массовые сборища запретить. И с тех пор жизнь в Тридесятом царстве стала прекрасной: гулять так гулять, работать так работать, и все строго по цареву указу.

Понравилась мысль такая царю Тридевятого царства. Подумал он ввести и у себя такие порядки. Собрал царь советников своих, и говорит: подготовьте мне список дней, в которые гулять можно. Только не на год, а на \(N\) дней вперед — посмотрим, дескать, что получится; понравится — сделаем круглогодичным.

И вот вчера принесли советники царю список. Но вот незадача: каждый советник свой список приготовил, да еще и обоснование предложил, какой праздник в какой из этих дней надо отмечать. И у всех советников праздники важные, но у всех — разные! Царь думал-думал и решил: а возьмем их все — объединим предложения советников! Если какой-то день есть в списке хотя бы одного советника, то объявим этот день праздничным, и пускай народ гуляет! Глядишь, и не будет недовольных.

Только одна проблема осталась: некоторые дни оказались в списках сразу у нескольких советников. Но царь и тут нашел выход: перенесем некоторые праздники на более поздние дни, так, чтобы в каждый день получался только один праздник, и переносы были бы как можно короче.

Пусть, например, четыре советника сразу предложили сделать некоторый день (пускай день 5) праздничным. Тогда перенесем три из этих четырех праздников на дни 6, 7 и 8 — так, что праздничными будут дни с 5 по 8 включительно. А если оказывается, что, например, день 7 тоже предложен в качестве праздничного кем-нибудь из советников, то перенесем этот праздник еще дальше — на день 9.

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

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

На первой строке входного файла находится одно число \(N\) — количество дней, на которые царь хочет произвести планировку праздников.

На второй строке входного файла находятся \(N\) неотрицательных целых чисел — для каждого дня указано, сколько советников предложили считать его праздничным.

Гарантируется, что \(1\leq N\leq 100\,000\), и что сумма всех чисел во второй строке входного файла не превосходит \(100\,000\).

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

В выходной файл выведите одну строку, состоящую из символов “+” или “-”. “+” обозначайте праздничный день, “-” — непраздничный. Выведите как минимум \(N\) символов — по одному для каждого из дней, на которые проводится планирование. Но если праздники приходится переносить на дни после \(N\)-го (что допустимо), то выведите больше символов — до последнего праздничного дня.

Символы разделяйте пробелами.

Система оценки
  • Подзадача 0 (0 баллов) тест из условия.
  • Подзадача 1 (50 баллов) \( N \le 1000 \). Необходимые подгруппы: 0.
  • Подзадача 2 (50 баллов) без дополнительных ограничений. Необходимые подгруппы: 0-1.
Примеры
Входные данные
5
0 3 0 0 0
Выходные данные
- + + + -
Входные данные
10
0 4 0 2 0 0 0 0 1 0
Выходные данные
- + + + + + + - + -
Входные данные
3
0 3 0
Выходные данные
- + + +
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест