Темы --> Информатика --> Язык программирования --> Массивы
    Одномерные массивы(92 задач)
    Массив констант(7 задач)
    Двумерные массивы(118 задач)
---> 3 задач <---
Источники --> Личные олимпиады --> Нижегородская олимпиада школьников
    2009(6 задач)
    2010(6 задач)
    2011(6 задач)
    2012(6 задач)
    2013(6 задач)
    XI Нижегородская городская олимпиада по информатике им. В. Д. Лелюха, 2015г.(6 задач)
    XII Городская олимпиада школьников по информатике им. В. Д. Лелюха, 2016 г.(6 задач)
Страница: 1 Отображать по:
#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 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест