#1988

Строительство школы

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

Источники: [ Личные олимпиады, Московская олимпиада школьников, 7-9 классы, 2010, Задача D ]

В деревне Интернетовка все дома расположены вдоль одной улицы по одну сторону от нее. По другую сторону от этой улицы пока ничего нет, но скоро все будет – школы, магазины, кинотеатры и т.д.

Для начала в этой деревне решили построить школу. Место для строительства школы решили выбрать так, чтобы суммарное расстояние, которое проезжают ученики от своих домов до школы, было минимально.

План деревни можно представить в виде прямой, в некоторых целочисленных точках которой находятся дома учеников. Школу также разрешается строить только в целочисленной точке этой прямой (в том числе разрешается строить школу в точке, где расположен один из домов – ведь школа будет расположена с другой стороны улицы).

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

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

Сначала вводится число N — количество учеников (0 < N < 100001). Далее идут в строго возрастающем порядке координаты домов учеников — целые числа, не превосходящие 2∙10⁹ по модулю.

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

Выведите одно целое число — координату точки, в которой лучше всего построить школу. Если ответов несколько, выведите любой из них.

Примеры

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

4
1 2 3 4

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

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

3
-1 0 1

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

#3016

Списывание

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

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

На контрольной работе N учеников сидят в ряд. Для каждого ученика известно, какую оценку он получил бы, если бы писал эту контрольную самостоятельно (оценка — это число от 2 до 5). Однако ученики могут писать контрольную не только самостоятельно, но и списывать у своего соседа, но только если сосед пишет контрольную самостоятельно. В этом случае списывающий получит такую же оценку, какую получит тот, у кого он списал.

А именно (правила применяются строго в указанном порядке):

Школьники, которые знают материал на 5, будут писать контрольную самостоятельно.
Школьник, который знает материал на 4, если он сидит рядом с тем, кто знает на 5, будет списывать у него, а в противном случае будет писать самостоятельно.
Школьник, который знает на 3, если он сидит рядом с тем, кто знает на 5, будет списывать у него. Если среди его соседей знающего на 5 нет, но есть тот, кто знает на 4, и при этом пишет самостоятельно, то троечник будет списывать у него. В противном случае будет писать самостоятельно.
Аналогично школьник, знающий на 2 — из соседей, которые пишут самостоятельно, выберет того, кто знает лучше, и спишет у него. А если таких нет (или оба его соседа также знают на 2), то будет писать самостоятельно.

Определите, кто какую оценку в итоге получит.

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

Вводится число N (1<=N<=10) - количество учеников, и далее последовательность из N чисел, описывающая, кто на какую оценку может написать контрольную, если будет писать самостоятельно.

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

Выведите N чисел - оценки, которые получат ученики за контрольную.

Примечания к примерам тестов

1. Первый и пятый ученики будут писать самостоятельно. Второй спишет у первого, а четвертый — у пятого (в итоге также получат пятерки). Третьему не у кого списывать, так как его соседи будут писать работу не самостоятельно.

2. Второй и четвертый спишут у третьего, пятый — у шестого.

Примеры

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

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

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

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

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