1. Сновида-2 (автор — Володимир Ткачук)

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам'ять: 32 MБ
Вхідний файл: sleep2.in
Вихідний файл: sleep2.out
Програма: sleep2.*

Грабіжникам стало відомо про звичку президента Першого національного Банку майора Томаса Б. Кiнгмена кожну ніч перекладати вміст сейфів, у яких клієнти банку зберігають свої коштовності. Шляхом погроз і підкупу співробітників банку злочинці з'ясували як змінилось розташування коштовностей після двох ночей. На жаль для грабіжників, ця інформація не дозволяє однозначно встановити алгоритм, за яким майор перекладає вміст сейфів.

Завдання
Створіть програму sleep2.* , яка обчислює кількість можливих алгоритмів перекладання, що за дві ночі приводять до відомого злочинцям результату, якщо алгоритм перекладання щоночі однаковий.

Вхідні дані
В першому рядку файлу sleep2.in записано єдине натуральне число N — кількість сейфів у банку (N ≤ 100). У другому рядку через прогалину записано N натуральних чисел a₁, a₂, …, a_N, що описують вміст сейфів після другої ночі. Кожне таке число належить діапазону [1..N] і зустрічається в рядку лише один раз. Тут a_i — номер сейфа в який коштовності потрапили з i-го сейфа за дві ночі перекладань.

Вихідні дані Єдиний рядок вихідного файлу sleep2.out має містити одне ціле число — результат обчислень.

Приклади

2. Карти (автор — Юрій Знов'як)

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам'ять: 32 MБ
Вхідний файл: cards.in
Вихідний файл: cards.out
Програма: cards.*

Колода складається з парної кількості карт. Карти занумеровано послідовними натуральними числами від 1 до 2N (для певного натурального N) включно. З колодою роблять таке:

1. Спочатку колоду ділять на дві рівні частини. У першу частину потрапляють карти, що стояли на непарних місцях, в другу — ті карти, що були на парних місцях:
   (1, 2, …, 2N) → (1, 3, 5, …, 2N – 1) + (2, 4, …, 2N).

2. З обох утворених частин викидають карту, що розташована у відповідній частині на місці 1 + [aN/b] при 0 ≤ a < b ≤ 1000. Наприклад, якщо a = 0, b = 1, то буде викинуто першу карту:
   (1, 3, 5, …, 2N – 1) → (3, 5, 7, …, 2N – 1);
   (2, 4, 6, …, 2N) → (4, 6, 8, …, 2N).

3. Другу частину кладуть поверх першої:
   (3, 5, 7, …, 2N – 1) + (4, 6, 8, …, 2N) → (3, 5, 7, …, 2N – 1, 4, 6, 8, …, 2N).

Дії 1–3 повторюють доти, поки в колоді не залишиться лише 2 карти. Наприклад, якщо a = 1, b = 2, а початкова кількість карт — 2 · 5, маємо:

(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) → (1, 3, 5, 7, 9) + (2, 4, 6, 8, 10) → (1, 3, 7, 9) + (2, 4, 8, 10)  → (1, 3, 7, 9, 2, 4, 8, 10) → (1, 7, 2, 8) + (3, 9, 4, 10) → (1, 7, 8) + (3, 9, 10) → (1, 7, 8, 3, 9, 10) → (1, 8, 9) + (7, 3, 10) → (1, 9) + (7, 10) → (1, 9, 7, 10) → (1, 7) + (9, 10) → (1) + (9) → (1, 9),

бо 1 + [5·1/2] = 3, 1 + [4·1/2] = 3, 1 + [3·1/2 ] = 2, 1 + [2·1/2] = 2.

Завдання
Визначте кінцевий стан колоди.

Вхідні дані
Вхідний файл містить 3 невід'ємні цілі числа N, a, b. 2 ≤ N ≤ 500 000.

Вихідні дані
Вихідний файл має містити два натуральних числа: номери карт, що залишаться. Номер нижньої карти потрібно вказати першим.

Приклад

3. Гра (автор — Михайло Рибак)

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам'ять: 32 MБ
Вхідний файл: game.in
Вихідний файл: game.out
Програма: game.*

Полем гри є декартова площина із двома групами занумерованих точок. Точки першої групи мають координати (0; і), де і — номер точки в групі (нумерація починається з 0). Точки другої групи мають координати (1; j), де j — номер точки в групі (нумерація також починається з 0).

Кожну точку пофарбовано у білий або у чорний колір.

Гравці ходять по черзі. За один хід гравець сполучає відрізком деяку точку А з першої групи з деякою точкою В з другої групи. При цьому справджуються такі умови:

• точки А і В — одного кольору;
• відрізок АВ не має спільних точок з довільним уже проведеним відрізком.

Гравець, що не може зробити наступний хід, програє.

Завдання

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

Вхідні дані
Перший рядок містить число M (0 ≤ M ≤ 20) — кількість точок у першій групі.
Другий рядок містить число N (0 ≤ N ≤ 20) — кількість точок у другій групі.
Третій рядок містить M чисел, що задають розфарбування точок першої групи (0 — чорний колір, 1 — білий колір).
Четвертий рядок містить N чисел, що задають розфарбування точок другої групи таким самим чином.

Вихідні дані
Якщо виграє другий гравець, єдиний рядок вихідного файлу містить слово LOSE.
Якщо виграє перший гравець, перший рядок вихідного файлу містить слово WIN, а наступні рядки перераховують виграшні перші ходи. Кожний рядок містить один з можливих ходів у такому форматі:

I J

Тут I — номер точки з першої групи, J — номер точки з другої групи. Кожен виграшний хід повинен зустрічатися один та лише один раз. Пари (I; J) потрібно подати в лексико­графічному порядку.

Приклади

4. Школа (автор — Данило Мисак)

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: school.in
Вихідний файл: school.out
Програма: school.*

Петро П’яточкін учиться у школі, а тому має кожен день до неї ходити. Він живе у місті Ідеальне, що відоме у тому числі й своєю розвинутою тролейбусною мережею (щоправда, іншого транспорту в Ідеальному немає). Зокрема, відомо, що всі тролейбусні маршрути у місті мають n-цифрові номери, і кожне n-цифрове число є номером деякого тролейбусного маршруту. Крім того, на двох маршрутах є спільна зупинка тоді й лише тоді, коли з номера одного маршруту можна шляхом переставляння цифр або зменшення однієї з ненульових цифр на одиницю отримати номер іншого. Для чотирицифрових номерів можна подати такі приклади.

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

Завдання
Допоможіть Петрикові їздити до школи, роблячи якомога менше пересадок.

Вхідні дані
У першому рядку вхідного файлу вказані три натуральні числа:
n — кількість цифр у номерах тролейбусних маршрутів Ідеального;
m — кількість різних маршрутів, які проходять повз будинок Петрика;
k — кількість маршрутів, що проходять повз школу, в якій Петрик учиться.

У другому рядку перераховано m, а у третьому — k різних чисел, що є номерами відповідних маршрутів. Відомо, що 2 ≤ n ≤ 1000 та 1 ≤ m, k ≤ 100.

Вихідні дані
Перший рядок вихідного файлу має містити єдине число x — найменшу можливу кількість пересадок, що доведеться зробити Петрику на шляху до школи.

Другий рядок має містити перелік із x + 1 числа, де у порядку пересадок зазначено номери маршрутів, якими Петрик П’яточкін їздитиме до школи. Якщо є кілька варіантів пересадок, необхідно вказати лише один із них.

Вхідні дані гарантують існування вихідних даних обсягом до 2Мб.

Приклад

5. Коло (автор — Андрій Гриненко)

Максимальна оцінка: 100 балів
Обмеження на час: 6 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: circle.in
Вихідний файл: circle.out
Програма: circle.*

На площині задано N різних точок, жодні три з яких не лежать на одній прямій.

Завдання
Знайдіть найменший радіус кола, всередині якого і на якому разом розташовано не менше ніж K даних точок.

Вхідні дані
Перший рядок вхідного файлу містить два натуральні числа N, K при 1 ≤ K ≤ N ≤ 200.

Наступні N рядків містять по два дійсних числа, які не перевищують 1000, — координати даних точок.

Вихідні дані
Єдиний рядок вихідного файлу має містити шуканий радіус, округлений до трьох знаків після крапки, яку використовують замість десяткової коми.

Приклад

6. Канікули (автор — Дмитро Кордубан)

Максимальна оцінка: 100 балів
Обмеження на час: 3 сек.
Обмеження на пам’ять: 32 МБ
Вхідний файл: vacation.in
Вихідний файл: vacation.out
Програма: vacation.*

Петрик успішно склав зимову сесію. Тепер він має вдосталь вільного часу, і хоче перетворити цей час на гроші, працюючи фотографом на сільських весіллях. Точніше, Петрик хоче виїхати з Києва, відвідати декілька сіл і повернутися додому. У кожному новому селі він заробить сталу суму грошей Т — вартість зйомки весілля. Але лише при першому візиті до цього села — подальші візити прибутку не приносять. Відома вартість проїзду між населеними пунктами. Вважаємо, що початковий капітал Петрика достатній для того, щоб дістатись до будь-якого села будь-яким простим шляхом.

Завдання
Визначте найменше ціле значення Т, за якого існує шлях селами з початком і кінцем у Києві, що принесе Петрику додатний прибуток. Існування такого шляху гарантовано вхідними даними при певному Т.

Вхідні дані
Перший рядок вхідних даних містить натуральне число N — кількість сіл (N ≤ 16). Села занумеровано натуральними числами від 1 до N. Київ має номер 0.

Кожний з наступних N + 1 рядка містять по N + 1 цілому числу — x_ij, де j — номер числа у i-му рядку у відповідній прямокутній таблиці чисел. У цій таблиці нумерацію рядків і нумерація чисел у кожному з рядків починають з нуля, 0 ≤ i, j ≤ N. Число x_ij дорівнює вартості проїзду між населеними пунктами i та j. Ці вартості не перевищують 10 000, x_ij = x_ji, x_ii = 0 при всіх i та j. Від’ємна величина x_ij вказує на відсутність прямого шляху між пунктами i та j.

Вихідні дані
Єдиний рядок вихідного файлу має містити одне ціле число — найменше ціле значення Т, за якого існує прибутковий цикл.

Приклади