Задача 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. Искусственный интеллект ≡

Условие

Программист Петя любит играть в онлайновые игры. Но, из-за постоянной нехватки времени, он не может делать это слишком часто и долго. Поэтому, казалось бы, он обречен всегда иметь в своем распоряжении только слабых персонажей. Однако у него есть план, который непременно поможет ему заполучить одного из самых "прокачанных" героев в его любимой MMORPG Waste of Weekend (WOW).

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

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

Для того, чтобы научить свою программу различать игроков двух классов, Петр взломал один из серверов WOW и скачал информацию о некотором множестве персонажей. Поскольку ему не остается ничего другого, кроме как принять гипотезу о нормальности распределения характеристик в каждом из классов, эти данные можно использовать для оценки его параметров. Имея последние, модуль ИИ должен определять с каким противником он имеет дело в каждый момент времени и соответственно выдавать: "CAST SPELL" или "HIT BY SWORD".

Поскольку уровень знаний алгоритмов у Пети не столь высок, как его хакерские способности, ему потребуется помощь!

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

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

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

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

Следующие M строк содержат по K + 1 целому числу, первое из которых равно 0, если персонаж является бойцом, и 1, если волшебником, а остальные задают характеристики.

Оставшиеся N строк содержат по K целых чисел — характеристики персонажей, для которых нужно определить класс.

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

В выходной файл выведите N строк. Каждая из них должна содержать (без кавычек) "CAST SPELL", если соответствующий персонаж является бойцом и "HIT BY SWORD", если волшебником.

Ограничения

1 ≤ K, ≤ 10

1 ≤ N, M ≤ 1000

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

2 10 10
0 333 245
0 359 234
1 589 184
0 486 215
1 684 81
0 362 288
0 405 212
1 730 139
1 786 0
0 340 293
863 732 
0 120 
436 129 
823 318 
198 643 
605 471 
297 656 
264 636 
616 490 
595 472 

HIT BY SWORD
CAST SPELL
CAST SPELL
HIT BY SWORD
HIT BY SWORD
HIT BY SWORD
HIT BY SWORD
HIT BY SWORD
HIT BY SWORD
HIT BY SWORD