Задача A. Политическая карта ≡

Условие

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

Археологам стало очень интересно, сколько же государств существовало на планете Земля в те отдаленные геологические эпохи, когда эта игра занимала умы множества несостоявшихся политиков каждый вечер. Кто знает, может тогда еще не прошло время феодальной раздробленности и их счет шел на тысячи... Чтобы удовлетворить свое любопытство, ученые сделали множество скриншотов, прокрутив карту на различные позиции, а потом склеили их. В результате получился двумерный массив пикселей, слишком большой, чтобы посчитать количество стран вручную. И как только эти древние люди могли держать в голове информацию о таком количестве игроков глобальной геополитики...

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

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

Первая строка входного файла содержит числа W и H — ширину и высоту массива, соответственно.

Следующие H строк содержат по W целых чисел от 1 до 4 — цвета пикселей.

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

В выходной файл выведите единственное целое число — количество стран на карте

Ограничения

1 ≤ W, H ≤ 1000

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

4 1
1 2 1 2

4

3 3
1 1 2
2 1 1
2 1 2

4

Задача B. Лотерея ≡

Условие

Недавно организация ACM (Association Consuming Money) объявила о проведении лотереи по новой схеме. Участник, купив билет, должен написать в нем последовательность чисел некоторой длины. При розыгрыше случайным образом выбирается другая последовательность, причем ее элементы могут повторяться.

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

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

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

Первая строка входного файла содержит числа N и M — длины первой и второй последовательностей.

Вторая строка содержит N целых чисел a_i разделенных пробелами — последовательность участника.

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

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

В выходной файл выведите длину наибольшей общей подпоследовательности.

Ограничения

1 ≤ N, M ≤ 1000

0 ≤ a_i, b_i ≤ 10⁹

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

5 3
1 2 3 4 5
2 4 4

2

Задача C. Площадь пирога ≡

Условие

Раз на раз не приходится. И теперь пирог получился в форме невыпуклого многоугольника с N вершинами. Пытаться разрезать его на треугольники, теперь, кажется, совсем бесполезно. Поэтому хозяйка решила поделить его, руководствуясь иными, ничуть не менее очевидными соображениями. А именно — пусть всем достанутся куски одинаковой площади. Однако теперь, чтобы претворить ее план в жизнь нужно посчитать площадь всего пирога. Напишите такую программу.

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

Первая строка входного файла содержит число N — количество вершин многоугольника.

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

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

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

Ограничения

3 ≤ N ≤ 500

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

6
0 0 1 1 2 1 3 0 2 -1 1 -1

4.0000

Задача D. Обход доски конем ≡

Условие

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

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

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

Ограничения

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

1 1

A1

1 2

No solution

3 4

A1 B3 C1 A2 B4 C2 A3 B1 C3 A4 B2 C4

Задача E. Бюрократия ≡

Условие

В некотором государстве различные официальные вопросы решаются с помощью мощного бюрократического аппарата. Программист Василий хочет получить разрешение на открытие своей фирмы, но он еще не знает с какими сложностями ему придется столкнуться! Для того, чтобы оформить разрешение на свою деятельность Василий должен получить определенный набор справок, каждую из которых выдает специально предназначенный для этого чиновник. Задача усложняется тем, что многие из этих госслужащих не дают свои справки просто так. А именно, для каждого из них известно, справки от каких других чиновников нужно иметь при себе, чтобы получить справку от этого. Чтобы помочь Василию, напишите программу, которая выдаст последовательность посещения чиновников, которая бы гарантировала, что никто из них ему не откажет.

Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".

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

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

Ограничения

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

4 3
1 2
1 3
3 4

1 3 2 4