Задача A. Отгадай слово ≡

Условие

Хрюша и Степашка играют в игру "Отгадай слово". Правила игры просты. Хрюша придумывает слово, состоящее из букв латинского алфавита, придумывает загадку и загадывает её Степашке. Задача Степашки — отгадать слово.

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

Ход Степашки заключается в том, что Степашка называет любую букву латинского алфавита.

1. Если такая буква есть в слове и все такие буквы закрыты, то все они открываются.
2. Если такая буква есть в слове и все такие буквы открыты, то все они закрываются.
3. Если такой буквы нет в слове, то никакие буквы не открываются и не закрываются.

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

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

Входной файл содержит ровно две строки.

Первая строка входного файла состоит из маленьких букв латинского алфавита и представляет собой слово, придуманное Хрюшей.

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

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

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

Если i-я буква открыта, то i-й символ выходной строки должен совпадать с i-м символом первой строки входного файла.

Если же буква закрыта, то соответствующий символ выходной строки должен быть '.' (точка).

Ограничения

Количество букв в слове от 1 до 15.

Количество ходов Степашки от 1 до 20.

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

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

frog
or

.ro.

frog
oro

.r..

frog
fffrrroooog

fr.g

frog
golf

f.og

frog
gorf

frog

Задача B. Палка, палка, огуречик... ≡

Условие

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

Рисунок как землянина, так и марсианина состоит из окружности и пяти отрезков. Назовём отрезок торчащим из окружности, если один его конец лежит внутри или на границе окружности, а другой — снаружи.

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

Правильный рисунок землянина должен состоять из окружности, изображающей голову, с 1 торчащим отрезком, изображающим туловище. Остальные 4 отрезка, изображающие руки и ноги, должны иметь хотя бы одну общую точку с "туловищем" и лежать строго снаружи "головы".

Напишите программу, которая по данному рисунку определит, кто на нём изображён.

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

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

Выходной файл должен содержать единственную строку: TERRAN, если на рисунке землянин, MARTIAN, если на рисунке марсианин и UNKNOWN, если нарисовано ни то, ни другое.

Ограничения

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

100 100 50
80 130 80 200
90 130 90 200
100 130 100 200
110 130 110 200
120 130 120 200

MARTIAN

100 100 50
100 130 100 220
50 180 110 190
150 180 90 190
50 260 110 210
150 260 90 210

TERRAN

Задача C. Восстановить IP ≡

Условие

Корректная запись IP-адреса — это строка, состоящая из четырёх десятичных чисел в диапазоне от 0 до 255 каждое, разделённых символом "точка" (ASCII 46). Компоненты записи IP-адреса не должны содержать лидирующих нулей.

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

Помогите Пете восстановить IP-адрес.

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

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

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

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

7.2
102.
47
84.1

102.84.17.247

.0.
00
1
2.0

100.0.2.0
2.0.0.100

Задача D. Учебная разведка ≡

Условие

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

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

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

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

Требуется написать программу, которая по различным N точкам на плоскости построит непустой набор из выпуклых многоугольников, которые:

1. являются невырожденными и имеют не менее трёх вершин;
2. не имеют общих точек между собой;
3. имеют вершины только в данных точках;
4. используют в качестве вершин все имеющиеся точки, за исключением не более пяти штук.

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

Входной файл содержит число точек N, за которым следует N пар целых чисел x_i y_i — координаты точек.

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

Выходной файл должен содержать число многоугольников M, за которым следуют M описаний многоугольников. Каждое описание состоит из числа вершин K, за которым следует K чисел — номера точек, являющихся вершинами многоугольника, перечисленными в порядке обхода. Нумерация вершин начинается с 1.

Если существует более одного решения, выведите любое из них.

Ограничения

3 ≤ N ≤ 1000,  − 10⁵ ≤ x_i, y_i ≤ 10⁵

Никакие три точки не лежат на одной прямой.

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

5
-1 -1
1 1
1 -1
-1 1
3 7

0

9
-2 4  3 -2  3 2  -2 -4  2 5  -7 -3  7 2  1 -3  -4 -1

1
7  3 2 8 4 9 1 5

9
-2 4  3 -2  3 2  -2 -4  2 5  -7 -3  7 2  4 -6  -4 -1

2
4  5 1 3 7
4  9 2 8 6

Задача E. Матрёшки ≡

Условие

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

Сколькими способами можно поместить часть матрёшек внутрь других, чтобы осталось ровно K матрёшек?

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

Входной файл содержит целые числа N K.

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

Требуется вывести в выходной файл единственное целое число — искомое число способов.

Ограничения

1 ≤ K ≤ N ≤ 12.

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

3 1

1

3 2

3

4 2

7

3 3

1

Задача F. К вопросу о нумерации вагонов ≡

Условие

Поезд, идущий со станции A до станции B, остановился по пути на станции C, где к нему прицепили дополнительные вагоны.

Из A стартовали n вагонов с подряд идущими номерами 1, 2, …, n. На станции C либо в начало, либо в конец состава добавилось m вагонов с подряд идущими номерами n + 1, n + 2, …, n + m. Кроме того, вагоны как внутри первоначального, так и внутри прицепленного состава могут быть пронумерованы либо с начала, либо с конца соответствующего состава.

В билете каждого пассажира указан номер его вагона.

Имеется информация от двух пассажиров. Каждый из них помнит номер своего вагона, написанный в билете (a₁ и a₂ для первого и второго пассажира соответственно), и количество вагонов, которое ему пришлось пройти по перрону до вокзала на станции B, включая свой вагон (b₁ и b₂ соответственно). Вокзал на станции B находится в конце железнодорожных путей. Определите расположение вагонов поезда в момент прибытия на станцию B и выведите их номера в порядке удаления от вокзала.

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

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

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

Если конфигурация состава, описанная пассажирами, невозможна, выведите единственное слово IMPOSSIBLE.

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

Ограничения

1 ≤ n, m ≤ 10;

1 ≤ a_i, b_i ≤ n + m;

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

5 3 4 2 8 8

YES
5 4 3 2 1 6 7 8

5 3 4 2 7 7

NO

5 3 1 4 2 6

IMPOSSIBLE

Задача G. Катание на лифте ≡

Условие

Однажды k учеников решили прогулять школу и покататься на лифте. Для этого они направились в дом с самым большим в городе лифтом.

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

После n-го раза лифт приехал на какой-то этаж и сломался — не открыл двери. Школьники помнят, какие кнопки были ими нажаты перед каждой поездкой и в каком направлении при этом перемещался лифт (вверх или вниз). Для вызова диспетчера необходимо узнать, на каких этажах может находиться лифт. Помогите им это выяснить. Известно, что сначала лифт стоял на первом этаже.

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

Первая строка входного файла содержит целые числа n k — количество поездок на лифте и количество школьников соответственно.

Следующие n строк содержат k + 1 чисел каждая: d_i f_1,i… f_k,i — направление движения лифта и номера этажей, кнопки которых были нажаты. Этажи нумеруются с 1.

• Если d_i равно 1, то после одновременного нажатия на кнопки этажей f_1,i, …, f_k,i лифт поехал вверх, на один из этих этажей.
• Если d_i равно  − 1 — лифт поехал вниз.

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

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

Если данные школьников противоречивы (т. е. хотя бы одна из описанных поездок невозможна), выходной файл должен содержать единственное число  − 1.

Ограничения

1 ≤ n, k ≤ 100, 1 ≤ f_i,j ≤ 1000

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

4 4
 1  4 8 5 7
 1  3 6 9 3
 1  1 2 4 4
-1  1 2 1 4

-1

3 4
 1  4 8 5 4
-1  6 9 6 4
-1  3 8 5 6

3 5

2 2
1  1 1
1  1 2

-1

Задача H. Замки и ключи ≡

Условие

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

Замок звездолёта представлен в виде матрицы 10 × 10, состоящей из символов '#' и '.'. Символ '#' соответствует заполненному пространству, '.' — пустоте.

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

1. номер строки, на которой расположена ось,
2. размеры выступов для каждой колонки над и под осью (в строках).

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

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

Первая строка содержит число n — номер строки ключа, на которой расположена ось.

Вторая и третья строки содержат по 10 целых чисел — высота выступов над и под осью соответственно.

Последующие 10 строк содержат по 10 символов каждая — описание замка.

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

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

Ограничения

1 ≤ n ≤ 10

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

6
2 1 5 1 2 2 1 5 1 2
0 1 2 0 3 3 0 2 1 0
##.####.##
##.####.##
##.####.##
.#.#..#.#.
..........
..........
#..#..#..#
##.#..#.##
####..####
##########

YES