#3787

Кривая дракона

Темы: [Арифметические алгоритмы] [Цикл for]

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

Сегодня мальчик Саша на уроке математики узнал про фракталы. Учитель показывал так называемую «кривую дракона». Она представляет собой геометрическую фигуру, которая строится следующим образом: на первом шаге проводится отрезок из начала координатной плоскости в точку (0; 1). Далее на каждом шаге из конца фрактала повторяется уже нарисованная часть фигуры, повернутая на 90 градусов против часовой стрелки (см. рисунок).

После уроков Саша попробовал сам изобразить «кривую дракона», и теперь он хочет знать, в какой точке координатной плоскости он закончил рисовать фрактал, проделав описанные выше N шагов. Требуется написать программу, которая по заданному числу N определяет координаты конца фрактала после выполнения N шагов.

$\text{[math]}$

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

Вводится одно целое число N (1 ≤ N ≤ 30).

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

Выведите два числа через пробел — координаты конца фрактала.

Примеры

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

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

1 1

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

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

2 -2

#3888

Автомат со сдачей

Темы: [Задачи на моделирование] [Циклы]

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

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

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

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

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

3
5 5 10

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

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

4
50 5 5 5

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

#111856

Чехарда

Темы: [Цикл while] [Жадный алгоритм]

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

Дорожка замощена плитками в один ряд, плитки пронумерованы числами от 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$), записанных в отдельных строках.

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

Выведите одно число — наибольшее количество ходов, которое может продолжаться игра.

Примечание к примеру

В примере сначала кузнечик с плитки №6 прыгает на плитку №3. Затем кузнечик с плитки №4 прыгает на плитку №2.

Примеры

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

1
4
6

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

#111986

Олимпийский огонь

Темы: [Цикл for]

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

В одном известном всем городе скоро стартуют Зимние Олимпийские игры. В связи с этим организаторы игр решили провести эстафету Олимпийского огня — самую продолжительную и масштабную в истории Олимпийских игр. Эстафета состоит из $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

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

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

10 1
1 2 3 4 5 6 7 8 9 10

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

#111987

Шахматные клетки

Темы: [Цикл for]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2013, 7-9 классы, Шахматные клетки ]

Недавно Петя услышал на шахматном кружке о мегашахматах.

Поле для мегашахмат — это разделённый на клетки прямоугольник, в котором каждый горизонтальный ряд клеток имеет свою высоту, а каждый вертикальный столбец — свою ширину. Всего на поле n рядов и m столбцов клеток, высота i-го ряда составляет a_i сантиметров, а ширина j-го столбца — b_j сантиметров. Столбцы нумеруются слева направо, а строки — снизу вверх. Клетки покрашены в чёрный и белый цвета в шахматном порядке, левая нижняя клетка поля черная. Это значит, что соседи каждой клетки по вертикали и горизонтали отличаются от нее по цвету.

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

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

В первой строке вводятся два целых числа n и m — количества рядов и столбцов клеток на поле для мегашахмат (1 ≤ n, m ≤ 10⁵).

Во второй строке вводится n целых чисел a_i — высоты рядов клеток в сантиметрах (1 ≤ a_i ≤ 100).

В третьей строке вводится m целых чисел b_j — ширины столбцов клеток в сантиметрах (1 ≤ b_j ≤ 100).

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

Выведите два числа в одной строке: площадь всех чёрных клеток и площадь всех белых клеток в квадратных сантиметрах на поле.

Примеры тестов

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

8 8
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

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

32 32

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

2 3
3 2
3 2 1

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

16 14

Примечание

Второй тест из условия соответствует рисунку.

Тесты к этой задаче состоят из трех групп. Если решение не проходит какую-либо группу тестов, следующие группы не проверяются.

Тесты 1 – 2. Тесты из условия, оцениваются в ноль баллов.
Тесты 3 – 20. В тестах этой группы 1 ≤ n, m ≤ 10³, 1 ≤ a_i, b_i ≤ 10. Эта группа оценивается в 40 баллов, баллы ставятся только при прохождении всех тестов группы.
Тесты 21 – 32. В тестах этой группы дополнительные ограничения отсутствуют. Прохождение тестов из этой группы оценивается из 60 баллов, баллы начисляются за каждый тест независимо от прохождения остальных тестов и суммируются.