#3787

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

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

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

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

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

$\text{[math]}$

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

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

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

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

Примеры

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

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

1 1

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

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

2 -2

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