Задача A. Поиск в массиве ≡

Условие

В первой строке входных данных содержатся натуральные числа n и m.

Во второй строке задаются n элементов первого массива, отсортированные по возрастанию, а в третьей строке – m элементов второго массива.

Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит 10⁹

Формат входных данных

Первая строка входных данных содержит числа n и m - количество чисел в первом и втором массиве.

В следующей строке идут n чисел a_i.

В третьей строке идут m чисел b_i.

Формат выходных данных

Требуется для каждого из m чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае.

Ограничения

0 < n,m ≤ 10⁵

 − 10⁹ < a_i, b_i ≤ 10⁹

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

3 3
2 3 5
1 2 3

NO
YES
YES

3 4
1 2 2
1 2 4 5

YES
YES
NO
NO

Задача B. Вложение со сгибом ≡

Условие

Из бумаги вырезаны два прямоугольника со сторонами, параллельными осям координат.

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

Формат входных данных

Входные данные содержат четыре целых числа W₁ H₁ W₂ H₂, где W₁ H₁ — ширина и высота первого прямоугольника, W₂ H₂ — ширина и высота второго прямоугольника.

Формат выходных данных

Выходные данные должны содержать единственную строку YES, если искомый сгиб существует и NO в противном случае.

Если первый прямоугольник помещается во втором даже без сгиба, выведите YES.

Ограничения

1 < W₁, H₁, W₂, H₂ < 10⁹

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

1 2 1 1

YES

20 20 10 10

NO

Задача C. Аквалангист ≡

Условие

Аквалангист Джонс находится в море в координате x_j, y_j на глубине h_j метров. Джонс заметил акулу, которая находится в координате x_s, y_s на глубине h_s метров. Акула тоже заметила Джонса.

Успеет ли Джонс выплыть вертикально вверх к поверхности со скоростью 1 м/с раньше, чем акула достигнет Джонса, если акула способна двигаться только параллельно осям координат со скоростью v_s м/с и приближается к нему по одному из кратчайших путей?

Если Джонс достиг поверхности одновременно с тем, как акула достигла Джонса, считается, что он не успел.

Формат входных данных

Входные данные содержат в двух строках целые числа x_j, y_j, h_j и x_s, y_s, h_s, v_s.

Формат выходных данных

Выходные данные должны содержать YES, если Джонс успеет выплыть и NO в ином случае.

Ограничения

0 ≤ |x_j|, |y_j|, h_j, |x_s|, |y_s|, h_s ≤ 10⁵

1 ≤ v_s ≤ 100

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

0 0 1
100 100 100 1

YES

0 0 1
0 0 2 2

NO

Задача D. Табун ≡

Условие

Однажды черный шахматный король, живущий на доске размером n × m, решил собрать большой табун белоснежных коней. Король для себя и коней может выбрать любые поля на доске. Конечно, ни один белый конь не должен атаковать черного короля. Какое минимальное количество пустых полей окажется на доске?

Формат входных данных

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

Формат выходных данных

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

Ограничения

1 ≤ n, m ≤ 10

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере на доске размером 2 × 4 какое бы место для себя не выбрал король, более 6 коней разместить нельзя. Одно поле останется пустым.

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

2 4

1

Задача E. Мёд и справедливость ≡

Условие

Две пчелы собирают пыльцу с N цветков, расположенных в ряд. Цветок номер i содержит a_i микрограмм пыльцы.

Пчёлы договорились, что первая пчела будет собирать пыльцу с цветков на участке от L до M включительно, а вторая  — от M + 1 до R включительно (L ≤ M < R). Чтобы ни одной из пчёл не было обидно, сумма запасов пыльцы на первом и втором участках пчёл должны совпадать.

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

Формат входных данных

Входные данные содержат целое число N, за которым следует N чисел a_i.

Формат выходных данных

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

Ограничения

2 ≤ N ≤ 10000

1 ≤ a_i ≤ 10⁵

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

3
1 1 2

1 2 3

2
2 5

-1

Задача F. Кошачьи шпионы ≡

Условие

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

Мяуканье представляет из себя набор из букв m, e, o, w, причем этих букв может быть много, но одинаковые буквы всегда идут подряд.

Вы, как член службы безопасности кошачьего государства, допросили n особей, и каждого попросили издать звук мяуканья. От вас требуется ответить на вопрос: сколько среди опрошенных вами особей являются шпионами.

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

Формат входных данных

Первая строка входного файла содержит одно целое число: n - количество допрошенных особей.

В следующих n строках содержится целое число m_i и строка s_i длинны m_i.

Формат выходных данных

Выходной файл должен содержать одно целое число - количество шпионов.

Ограничения

0 < N ≤ 10⁵

0 < m_i ≤ 10⁵

0 < ∑m_i ≤ 4 * 10⁵

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

5
4 meow
11 meeeeooooow
4 miow
4 myau
5 hello

3

7
7 bonjour
7 alaykum
8 dobryden
2 ep
9 reverence
4 iiti
8 konishua

7

Задача G. Слон Пахом и разработка RPG ≡

Условие

Слон Пахом создаёт новую RPG, для игры ему потребовался уровень-лабиринт. Лабиринт содержит n × m платформ, n рядов по m платформ. Платформы бывают трёх видов:

1. Коридоры. В зависимости от ориентации обозначаются или символом "-" (находясь на такой платформе можно, пройти только влево или вправо) или "|" (находясь на такой платформе, можно пройти только вверх или вниз).
2. Перекрёстки. Обозначаются символом "+" (можно пройти в любую сторону).
3. Стены. Обозначаются символом "#" (по ним нельзя пройти).

С платформы на платформу можно перейти, только если платформы стыкуются между собой. Во время похождения по коридору игрок может повернуть платформу, на которой он находится, на 90 градусов и продолжить прохождение в любом направлении, или же оставить платформу нетронутой и пройти дальше.

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

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

Формат входных данных

Первая строка входных данных содержит два целых числа n и m. Следующие n строк содержат по m символов каждая — описание лабиринта.

Формат выходных данных

Первая строка выходных данных должна содержать "YES", если лабиринт проходимый, в противном случае "NO".

Если лабиринт проходимый, то следующая строка должна содержать целое число k — минимальное количество поворотов, необходимое для прохождения лабиринта.

Ограничения

1 ≤ n, m ≤ 10³

Описание подзадач и системы оценивания

Решения, работающие для n = 1, оцениваются из 30 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

5 5
+++++
+++++
+++++
+++++
+++++

YES
0

1 8
+-------

YES
0

1 8
+------|

NO

5 6
|-----
|-###-
#|---#
####|#
+++#|-

YES
5

1 1
#

NO