Задача A. Выйду ночью в поле с конями ≡

Условие

Поле шахматное, оба коня — тоже. Первый стоит на клетке с координатами (x₁, y₁), второй — (x₂, y₂). Кони одновременно совершают ходы по обычным правилам (буквой Г). Может ли так случиться, что они окажутся на одной клетке?

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

Первая строка входного файла содержит два натуральных числа, записанных через пробел: x₁, и y₁ — положение первого коня. Во второй строке в том же формате заданы числа x₂, и y₂ — положение второго коня. Гарантируется, что кони изначально стоят на разных клетках.

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

Выведите "Yes" или "No" (без кавычек) — ответ на вопрос задачи.

Ограничения

1 ≤ x₁, x₂, y₁, y₂ ≤ 8

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

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

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

В примере у коней есть возможность после двух ходов оказаться на одном поле.

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

7 8
2 1

Yes

Задача B. Нелюбимые цифры ≡

Условие

Тимофей недавно научился считать. Это радостное событие омрачает лишь одно обстоятельство — некоторые цифры Тимофею категорически не нравятся, и если хотя бы одна такая цифра присутствует в очередном числе, то мальчик его пропускает. Например, если Тимофею не нравятся цифры от 3 до 8 включительно, то при счете двенадцати предметов он будет называть числа: 1, 2, 9, 10, 11, 12, 19, 20, 21, 22, 29, 90.

Тимофею нужно посчитать n предметов. Какое число он назовет последним?

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

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

Во второй строке в порядке возрастания через пробел перечислены k нелюбимых цифр.

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

Выведете одно натуральное число — то, которым Тимофей закончит счет предметов. Гарантируется, что ответ на задачу не превысит 10⁵.

Ограничения

0 ≤ n ≤ 100

1 ≤ k ≤ 9, гарантируется, что нелюбимые цифры не образуют непрерывный интервал от 1 до 9 включительно.

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

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

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

12 6
3 4 5 6 7 8

90

20 4
0 2 4 6

53

Задача C. Злой палиндром ≡

Условие

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

Напомним, что число является палиндромом, если оно одинаково читается в обоих направлениях. Например, числа 1, 33, 1001 — палиндромы, а 13 или 1024 — нет.

Напомним, что число является злым, если при записи в двоичной системе счисления оно содержит чётное число единиц. Например, числа 3 (11₂ в двоичной системе счисления), 6 (110₂), 51 (110011₂) — злые, а 7 (111₂), 8 (1000₂) или 19 (10011₂) — нет.

Тимофей выписывает все подходящие для заклинания числа на листочек в возрастающем порядке. Какое число в этой последовательности окажется на n-ом месте?

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

В единственной строке записано одно натуральное число n — порядковый номер злого палиндрома.

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

Выведете одно натуральное число — соответствующий злой палиндром.

Ограничения

1 ≤ n ≤ 10⁵

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

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

Подзадача 1: 0 ≤ n ≤ 500, баллы: 30. Гарантируется, что ответ не превысит 10⁵

Подзадача 2: нет дополнительных ограничений, баллы: 70. Гарантируется, что ответ не превысит 10¹⁰

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

Комментарий к первому примеру: Первое натуральное число, являющееся одновременно палиндромом и злым числом, это 3. Оно одинаково читается в обоих направлениях, а при переводе в двоичную систему счисления имеет две (четное число) единицы в записи. Меньшие натуральные числа (1 и 2) не подходят - они хоть и палиндромы, но не являются злыми, так как содержат в своей записи в двоичной системе счисления нечетное число единиц (одну).

Комментарий ко второму примеру: Приведем ряд из десяти первых чисел на листочке Тимофея: 3, 5, 6, 9, 33, 66, 77, 99, 101, 111.

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

1

3

10

111

Задача D. Плохой шифр ≡

Условие

Евгений разработал шифр для обмена сообщениями с друзьями. Пока шифр работает только для чисел по следующему алгоритму:

1) Заданное натуральное число разбивается на цифры.

2) Каждая цифра переводится в двоичную систему счисления.

3) Двоичные записи записываются подряд без пробелов.

Например, для числа 195 алгоритм сработает так: 195 - 1 9 5 - 1 1001 101 - 11001101.

Евгений зашифровал одно натуральное число и получил двоичную запись s. Эту запись он передал своему другу Всеволоду, а через несколько минут получил от него сообщение, в котором говорилось, что этот шифр никуда не годится, поскольку существует несколько чисел, которые будут зашифрованы одинаково. Более того, Всеволод точно указал количество таких чисел и сами числа! Попробуйте сделать то же самое.

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

Единственная строка входного файла содержит двоичную запись s.

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

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

Ограничения

1 ≤ len(s) ≤ 20

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

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

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

10010

7
42 90 202 410 1002 2010 10010

Задача E. В двух из трех ≡

Условие

Найдите числа, которые присутствуют ровно в двух массивах из трех.

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

Первая строка входного файла содержит три натуральных числа n_i, записанных через пробел — размеры трех массивов. В следующих трех строках через пробел расположены упорядоченные по возрастанию целые числа x_i — сами массивы. Гарантируется, что в каждом из массивов все числа различны.

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

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

Ограничения

1 ≤ n_i ≤ 10⁵

 − 10⁹ ≤ x_i ≤ 10⁹

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

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

Решения, верно работающие при n_i, x_i ≤ 10³, получат не менее 40 баллов.

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

5 6 7
1 2 3 4 5
-2 0 2 4 6 8
-3 0 3 6 9 12 15

0 2 3 4 6