Задача MChess

Однажды юноша, который интересуется олимпиадными задачами по программированию, пошел на прогулку в лес. Гуляя по лесу, он встретил Злого Мишку, лесного зверя, который терпеть не может тех, кто ходит по его лесу. Мишка хотел принести парня в жертву, но, узнав что юноша - программист, решил сыграть с ним в игру "Лесные шахматы".
Игра имеет такие правила: на доске размером 3хN в первой горизонтали доски находится N черных пешек Злого Мишки, в третьей горизонтали находится N белых пешек мальчика, соответственно вторая горизонталь пустая. Злой Мишка и юноша ходят по очереди, начинает юноша. На каждом шаге игрок выбирает пешку, которой либо делает ход, либо сбивает пешку противника.
В соответствии с правилами, пешки ходят на одну клетку вперед, т.е белая пешка может перейти с третьей горизонтали на вторую, а потом со второй на первую. Если пешка черная - все наоборот, она может пойти с первой горизонтали на вторую, а потом - на третью. Понятно, что клетка, на которую при ходе становится пешка, должна быть свободной.
Пешка бьет фигуры по диагонали на одну клетку. В "лесных шахматах" сбивать фигуры обязательно: т.е. если можно сбить фигуру, это следует делать при этом ходе! Проигрывает тот, кто не сможет сделать очередной ход.
Ваша задача помочь юноше указать все возможные первые ходы, которые на 100% приведут его к победе, если его дальнейшая стратегия будет оптимальной.

Технические условия. Программа считывает с клавиатуры одно число N (1<=N<=1000).
Программа выводит на экран сначала число K - количество первых ходов юноши, ведущих к победе на 100% в случае оптимальной стратегии. Если таковых нет, тогда нужно вывести 0. Далее идут K чисел в порядке возрастания, которые показывают, какой по номеру белой пешкой должен ходить юноша.
Белые пешки нумеруются от 1 до N слева направо. Все числа выводятся через пробел.

Примеры.

Ввод> 3
Вывод> 1 2

Ввод> 2
Вывод> 2 1 2

Задача Casino

Команда телевизионных игроков в "Что? Где? Когда?" села за стол для игры. Вопросы лежат каждый в своем секторе, все секторы заполнены. Секторы имеют произвольные номера. Если номера одинаковы, то цвета секторов разные. Волчок, стрелка которого вначале указывала на сектор с неким номером, раскрутили. Капитан команды запомнил не только номер этого сектора, но и всю последовательность номеров секторов, которые проходила стрелка в процессе вращения. Наиболее интересным оказалось то, что волчок, совершив целое количество оборотов, остановился, а стрелка оказалась напротив того же сектора, что вначале.
Какое минимальное количество вопросов может быть предложено для игры?

Технические условия. Программа читает с клавиатуры число N (2<=N<=30000) - количество номеров, которые запомнил капитан, а далее - N натуральных чисел, не больших 32000 - номера секторов, на которые указывала стрелка в процессе вращения. Первое число всегда совпадает с последним. Все числа разделены пробелами. Вы выводите на экран единственное число - минимально возможное количество конвертов с вопросами для игры.

Примеры.

Ввод> 13 5 3 1 3 5 2 5 3 1 3 5 2 5
Вывод> 6

Ввод> 4 1 1 1 1
Вывод> 1

Ввод> 4 1 2 3 1
Вывод> 3

Задача Casino2

В интеллектуальном казино "Что? Где? Когда?" разыгрывается N (1<= N<= 50) писем с вопросами для игроков. В начале игры письма раскладываются на круглом столе, разделенном на N секторов, по одному письму на сектор. Игра состоит из нескольких раундов, количество которых не превышает N. В начале каждого раунда определяется вопрос, который будет разыгран, по такому правилу. Запускается волчок, стоящий в центре стола; он останавливается в некотором секторе (мы считаем, что волчок никогда не останавливается на границе секторов). Если в этом секторе лежит вопрос, то он будет разыгран. В противном случае волчок вращают против часовой стрелке до первого сектора, в котором лежит письмо, и вопрос берут из этого письма. Письмо с вопросом, который разыгран, забирают со стола. Игра закончена. Вам известно, какие письма остались на столе. Выясните, сколько возможных последовательностей остановок волчка приводят к такой конфигурации в конце игры.

Технические условия. Вы вводите с клавиатуры число N, а далее - последовательность из N чисел 0 (письмо отсутствует) и 1 (письмо в секторе есть). Секторы пронумерованы против часовой стрелки. Вы выводите на экран единственное число - ответ на задачу.

Примеры.

Ввод> 3 0 1 0
Вывод> 3

Ввод> 6 1 0 1 0 0 0
Вывод> 64

Задача CRANE

На станции Глупов-Товарный используются подъемные краны специальной конструкции "Мостовой-Глуповский". Крюк такого крана подвешен к нескольким блокам, которые ездят по рельсу, размещенному горизонтально (на некоторой высоте). Благодаря этому, крюк можно перемещать в любую точку части плоскости, ограниченной многоугольником специального вида: верхняя сторона многоугольника совпадает с рельсом крана, оба внутренние угла многоугольника при этой стороне острые, остальные вершины многоугольника размещены произвольно, но так, что многоугольник оказывается выпуклым. Кроме этого, станция имеет в распоряжении устройство, которое позволяет комбинировать действие двух кранов такого типа: пространство достижимости крюка скомбинированного механизма точно такой, если бы рельс второго крана подвесили (с сохранением горизонтальности) на крюк первого.

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

Технические условия. Введите с клавиатуры сначала 1 или 2 (в зависимости от того, какую задачу требуется решить), затем идут две области. Если решается задача "1", то это области достижимости первого и второго кранов, если "2", то вначале нужную область достижимости, а затем область достижимости первого крана. Все области достижимости задаются в таком формате: вначале число N (3<=N<=1000) - количество вершин в многоугольнике, а далее N групп по 2 числа x_i и y_i - координаты вершин этой области в порядке возрастания x - координаты. Система координат всегда выбирается так, что первая вершина имеет координаты (0; 0), ось y направлена сверху вниз. Все входные координаты - целые числа, не превышающие по модулю 10⁶. Если решается задача "2" и подобрать второй кран невозможно, то вывести на экран единственное число 0. Иначе вывести построенную область достижимости (в том же формате, что для входных данных).
Все числа разделяются пробелами. Если какие-то координаты нецелые, достаточно округлить до ближайшего целого.

Примеры.

Ввод>
2 5 0 0 10 40 20 50 30 40 40 0 3 0 0 10 10 20 0
Вывод> 3 0 0 10 40 20 0

Ввод> 2 3 0 0 10 10 20 0 3 0 0 10 10 40 0
Вывод> 0

Ввод> 1 3 0 0 10 10 20 0 3 0 0 10 10 40 0
Вывод> 4 0 0 20 20 50 10 60 0

Задача Hard

В компании Megasoft сотрудники начали жаловаться на недостаток места на жестких дисках. Каждый сотрудник может иметь в своем распоряжении только один диск. Владелец компании Гилл Бейтс предложил решение проблемы: некоторые сотрудники поменяются ЖД с другими, а остальным приобрести новые ЖД. Он составил список имеющихся ЖД и потребностей сотрудников. Гилл Бейтс программирует только на Basic, а этот язык не используется на NetOI. Hапишите за него программу для нахождения минимального количества ЖД, которые необходимо приобрести, чтобы удовлетворит потребности всех сотрудников.

Технические условия. Программа вводит с клавиатуры количество сотрудников N, (1<=N<=10000), а дале - N пар чисел в одну строку: первое число - емкость имеющегося ЖД, второе - потребность сотрудника. Все числа натуральные, не большие 1000, разделенные пробелами. Программа выводит на экран единственное число - ответ задачи.

Пример.

Ввод> 4 2 4 4 1 5 4 7 8
Вывод> 1