#111955

Остров

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

На клетчатой бумаге нарисована карта острова (клетки острова закрашены). При этом остров является клетчато-выпуклой фигурой, то есть каждая горизонтальная или вертикальная линия на карте либо не пересекает остров, либо пересекает его по отрезку (линия пересечения не содержит разрывов). Также остров является связной фигурой, то есть любые две клетки острова соединены путём, каждые две соседние клетки которого имеют общую сторону.

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

$\text{[math]}$

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

Формат входного файла

Программа получает на вход два числа N и M, записанные в отдельных строках, — количество строк и столбцов карты острова (3 ≤ N ≤ 100, 3 ≤ M ≤ 100). Далее записана карта острова — N строк, каждая содержащая M символов. Каждый символ карты может быть либо символом «.», что означает клетку, не принадлежащую острову, либо символом «#», что означает клетку острова. При этом остров не касается края карты.

Введём на карте систему координат. Первая координата является номером строки, строки нумеруются сверху вниз числами от 1 до N. Вторая координата — номер столбца, столбцы нумеруются слева направо числами от 1 до M.

Формат выходного файла

Программа должна вывести координаты клеток карты в порядке их облёта самолётом. Каждая строка вывода должна содержать два числа x и y — координаты самолёта, записанные через пробел (1 ≤ x ≤ N, 1 ≤ y ≤ M). Самолёт должен побывать в каждой соседней с островом клетке ровно один раз. Каждые две клетки, идущие подряд в выводе, должны иметь общую сторону. Можно вывести любой возможный маршрут облёта острова.

Примеры

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

6
7
.......
.......
.......
.###...
.###...
.......

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

#111985

Информатическая сила

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

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

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

В школьной летописи сохранились информатические силы двух классов, $A$ и $B$, а также количество задач на олимпиаде $N$. Завучу, нашедшему летопись, очень хочется узнать, могло ли быть в первом классе больше учеников, чем во втором.

Напишите программу, которая определит, могло ли быть учеников в классе с информатической силой $A$ больше, чем учеников в классе с информатической силой $B$.

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

Вводятся три целых числа, каждое в своей строке — $A$, $B$, $N$ ($0 \le A, B \le 10 000, 1 \le N \le 10 000$).

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

Выведите «Yes», если в первом классе могло быть больше учеников, чем во втором, и «No», в противном случае.

Примечания

Тесты к этой задаче состоят из трех групп.

Тесты 1 – 3. Тесты из условия, оцениваются в ноль баллов.
Тесты 4 – 17. В тестах этой группы $0 \le A, B \le 10, 1 \le N \le 10$. Эта группа оценивается в 30 баллов, баллы ставятся только при прохождении всех тестов группы.
Тесты 18 – 30. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 70 баллов, баллы ставятся только при прохождении всех тестов группы.

Примеры

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

60
30
4

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

Yes

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

30
30
1

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

No

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

30
150
4

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

No

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

#111988

Хоровод

Темы: [Эйлеров цикл] [Условный оператор (if)]

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

Настал декабрь, и вместе с ним пришло время готовиться к Новому Году. На острове рыцарей и лжецов этот праздник традиционно отмечается очень масштабно. Праздничный стол, новогодняя ёлка, конфетти и бенгальские огни — все готово к началу торжества.

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

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

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

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

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

В первой строке входных данных дано целое число n (2 ≤ n ≤ 10⁵) — количество жителей на острове лжецов.

В следующих n строках даны целые числа l_i и r_i (0 ≤ l_i, r_i ≤ 1) — данные о соседях i-го человека. Если l_i = 0, то i-й житель утверждает, что его сосед по хороводу в направлении против часовой стрелки был лжецом, а если l_i = 1, то рыцарем. Аналогично, число r_i содержит информацию о соседе по часовой стрелке.

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

Требуется вывести «Yes», если существует способ выстроить людей по указанным правилам, или «No», если нет.

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

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

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

Yes

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

2
0 0
1 1

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

No

Примечание

Тесты к этой задаче состоят из четырёх групп.

Тесты 1 – 2. Тесты из условия, оцениваются в ноль баллов.
Тесты 3 – 10. На тесты этой группы накладывается ограничение n ≤ 10. Группа тестов оценивается в 20 баллов, баллы ставятся только при прохождении всех тестов группы.
Тесты 11 – 26. На тесты этой группы накладывается ограничение n ≤ 20. Группа тестов оценивается в 25 баллов, баллы ставятся только при прохождении всех тестов группы.
Тесты 27 – 38. В тестах этой группы дополнительные ограничения отсутствуют. Группа оценивается в 55 баллов, баллы ставятся только при прохождении всех тестов группы.

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

Во втором примере, очевидно, нельзя получить никакого решения, так как выстроить двух человек в хоровод можно лишь одним способом. Рассмотрим два случая: если первый человек — рыцарь, то, по его словам, второй человек — лжец, однако, из лживости его слов следует, что первый человек не рыцарь. С другой стороны, если первый человек — лжец, то из его показаний следует, что второй человек — рыцарь, но второй человек говорит, что первый — тоже рыцарь. Таким образом, поскольку в обоих случаях мы получили противоречие, не существует способа построить хоровод из имеющегося набора жителей.