Задача 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