#2839

Темы: [Массив констант]

Источники: [ Личные олимпиады, Школьная личная олимпиада ФМШ №2007 г. Москвы, 2010, 8 класс, Задача C ] [ Личные олимпиады, Школьная личная олимпиада ФМШ №2007 г. Москвы, 2010, 9 класс, Задача A ]

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

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

Вводятся два числа, разделенных пробелом - число, месяц.

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

Вывести одно число - количество дней.

Примеры

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

2 1

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

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

31 12

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

#3207

Чемпионат по стрельбе

Темы: [Одномерные массивы] [Линейный поиск]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2011, 2 день, Задача B ]

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

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

Будем считать, что участник соревнования занял $k$-е место, если ровно $(k - 1)$ участников чемпионата набрали строго больше очков, чем он. При этом победителями считались все участники чемпионата, занявшие первое место.

Требуется написать программу, которая по заданным результатам чемпионата определяет, какое самое высокое место на чемпионате мог занять папа победителя школьного этапа олимпиады по информатике.

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

Первая строка входного файла содержит целое число $n$ — количество участников чемпионата страны по стрельбе ($3 \le n \le 10^5$).

Вторая строка входного файла содержит $n$ положительных целых чисел, каждое из которых не превышает 1000, — очки участников чемпионата, приведенные в том порядке, в котором они выполняли стрельбу.

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

В выходном файле должно содержаться одно целое число — самое высокое место, которое мог занять папа школьника. Если не существует ни одного участника чемпионата, который удовлетворяет, описанным выше условиям, выведите в выходной файл число 0.

Примечание

Правильные решения для тестов, в которых $1 \le n \le 1000$, оцениваются из 50 баллов.

Примеры

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

7
10 20 15 10 30 5 1

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

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

3
15 15 10

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

#3788

Кубики

Темы: [Одномерные массивы]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2011, Задача C ]

ООО «Симптотика» собирается наладить выпуск обучающих игр для детей младшего дошкольного возраста. Одной из придуманных игр был набор кубиков, из которых можно было собирать различные фигуры. Кубики упаковывались в коробку размером N × N × 1 кубиков.

Однако, многочисленные маркетинговые исследования показали, что детям неинтересно просто собирать различные фигурки. Гораздо интереснее складывать некоторый набор кубиков на дно коробки в столбики, а после этого переворачивать коробку на 90 градусов по часовой стрелке и смотреть, как именно меняется их расположение. Будем для простоты считать, что коробка поворачивается мгновенно, после чего все кубики падают на дно. На следующем рисунке продемонстрировано, как выглядит расположение кубиков в коробке до и после поворота на 90 градусов.

$\text{[math]}$

Разумеется, многим детям становится интересно, как будет выглядеть расположение кубиков после K поворотов в том же направлении. Требуется написать программу, которая вычисляет итоговое положение кубиков в коробке после K поворотов.

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

Сначала вводятся целые числа N и K (1 ≤ N ≤ 10, 0 ≤ K ≤ 10⁹). После этого, во второй строке вводятся N неотрицательных чисел, не превышающих N. i-ое число обозначает количество кубиков в столбце под номером i.

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

Необходимо вывести N чисел через пробел, i-ое из которых обозначает количество чисел в i-ом столбце в полученном после K поворотов расположении кубиков.

Примечание

Пример соответствует иллюстрации из условия.

Примеры

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

5 1
1 3 4 0 1

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

4 2 2 1 0

#3890

Шарики

Темы: [Двумерные массивы]

Источники: [ Личные олимпиады, Нижегородская олимпиада школьников, 2010, Задача D ]

Фирма, в которой работает ваш друг, решила установить на конечной остановке своих маршруток большую абстрактную скульптуру со своим логотипом. Скульптура будет представлять собой прямоугольную сетку из $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

Переливание духов

Темы: [Двумерные массивы] [Задачи на моделирование]

Источники: [ Личные олимпиады, Нижегородская олимпиада школьников, 2012, Задача A ]

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

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

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

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

Считайте, что Оля не пролила ни одной капли, а также что она тщательно встряхивала флаконы после каждого переливания. Учтите, что в маминых флаконах порой не видно, есть ли там жидкость, и потому Оля иногда могла пытаться переливать духи из пустого флакона (в результате, естественно, ничего не переливалось). Вы можете также считать, что после каждого переливания в каждом флаконе каждый тип духов либо полностью отсутствует, либо содержится в объеме не меньшем чем $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$-ого) в первом флаконе после последнего переливания. Выводите результат с точностью не меньше двух знаков после запятой. Гарантируется, что после последнего переливания первый флакон оказался непустым.

Примечание

¹... 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

Примеры

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

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

60.00 40.00