1. Кубики (автор — Олександр Рибак)

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

Незважаючи на те, що Петрик П’яточкін ходить до школи, він все ще продовжує гратися з кубиками. З однакових кубиків він викладає сходинки вздовж стіни. Для цього складає стовпчики з кубиків таким чином:

• перший стовпчик стоїть впритул до стіни;

• другий стовпчик стоїть впритул до стіни і впритул до першого стовпчика праворуч від нього;

• третій стовпчик стоїть впритул до стіни і впритул до другого стовпчика праворуч від нього і так далі…

Висоти стовпчиків не зростають при розгляданні сходинок зліва направо. Інакше кажучи, якщо h_i — висота i-го стовпчика, то h₁ ≥ h₂ ≥ h₃ ≥  …

Петрик встановлює кубики у деякій послідовності. Він встановив для себе такі правила:

1. Кубик, розташований не на підлозі, можна поставити лише після кубика, на якому він має стояти. Інакше кажучи, не можна підсовувати кубики під вже поставлені;

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

Завдання
Знайти кількість різних способів послідовного встановлення кубиків, у результаті яких виникнуть сходи з заданими висотами стовпчиків h₁, h₂, …, h_k. Врахувати лише ті способи, що задовольняють умови 1 і 2.

Вхідні дані
Перший рядок вхідного файлу містить натуральне число k — кількість стовпчиків (1 ≤ k ≤ 6).

Другий рядок вхідного файлу містить k натуральних чисел h₁, h₂, ... , h_k — кількості кубиків відповідно у першому, другому, … , k-му стовпчику сходів (6 ≥ h₁ ≥ h₂ ≥ … ≥ h_k ≥ 1).

Вхідні дані
Єдиний рядок вихідного файлу має містити кількість різних способів розташування кубиків у задану конфігурацію згідно з вказаними правилами 1 і 2 при даних висотах стовпчиків.

Приклад

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

2. Подорож у темряві (автор — Михайло Рибак)

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

Петро П’яточкін увесь вечір блукав цікавим лабіринтом та й не помітив, як настала ніч. Опинившись у темряві, він не бачить нічого, крім плану лабіринту на своєму мобільному та зоряного неба, на якому він одразу знайшов Полярну зірку. План лабіринту має форму прямокутної таблиці символів, у якій крапки «.» позначають порожні ділянки-квадрати з довжиною сторони в один крок, а ґратки «#» — стіни. Верхній край плану відповідає напряму на північ, правий — на схід.

Петрику потрібно потрапити до виходу, позначеному на плані хрестиком. Цей єдиний вихід займає окрему ділянку і є отвором, у який Петрик впаде одразу, як ступить на ділянку. На жаль, Петрик не знає, у центрі якої саме ділянки він знаходиться.

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

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

Вхідні дані
Перший рядок вхідного файлу містить натуральні числа H та W (1 ≤ H, W ≤ 10).

Кожний з наступних H рядків містить по W символів «.», «#» або «+», які позначають відповідно порожню ділянку, стіну та вихід. Таким чином подано план лабіринту, у якому перший рядок відповідає північному краю лабіринту, а останні символи кожного рядка — східному краю лабіринту.

Вихідні дані
Єдиний рядок вихідного файлу містить послідовність символів, що містить лише символи «N», «S», «E» та «W», які задають напрямок руху відповідно на північ, на південь, на схід і на захід. Цей рядок задає маршрут, дотримуючись якого, Петрик за скінченну кількість кроків прийде до виходу незалежно від свого початкового розташування. Таких маршрутів може бути кілька. Вивести потрібно будь-який із них, у якому кількість кроків не перевищує 10 000.

Якщо такого маршруту немає, вихідний файл має містити 2 символи: «NO».

Приклади

Розглянемо останній приклад. Легко перевірити, що, з якої клітини ми б не почали, рано чи пізно опинимося у виході. Наприклад, почнемо з ділянки (2; 1) у другому рядку і першому стовпчику.

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

3. Шахи (автор — Ярослав Твердохліб)

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

Петро П’яточкін захопився грою в шахи. З метою познайомитися з грою визнаних майстрів він вирішив спостерігати всі ігри товариського матчу столичної команди проти команди села Великі Олімпійці.

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

Петрику кортить побувати на якомога більшій кількості зустрічей. Тому він попрохав знайомого чарівника втрутитися: змінити рівень гри усім гравцям сільської команди на одну й ту саму кількість одиниць (ціле число) таким чином, щоб максимально збільшити кількість можливих ігор. Зауважимо, що після втручання чарівника рівні деяких гравців можуть стати від’ємними.

Завдання
Знаючи рівні гри усіх гравців і d, вкажіть:

• на яку величину потрібно змінити рівень гри сільських гравців так, щоб було зіграно найбільшу кількість ігор;

• як поєднати гравців команд-суперників у пари, щоб провести цю найбільшу кількість ігор (потрібно вказати лише один варіант такого поєднання).

Вхідні дані
Перший рядок вхідного файлу містить 3 цілих числа:
N — кількість гравців сільської команди (1 ≤ N ≤ 200);
M — кількість гравців столичної команди (1 ≤ M ≤ 200);
d — верхня межа різниці рівнів гравців, які можуть зіграти партію (0 ≤ d ≤ 10⁹).

Усі наступні числа натуральні і не перевищують 10⁹.
Другий рядок містить N чисел — рівні гравців сільської команди.
Третій рядок містить M чисел — рівні гравців столичної команди.

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

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

Приклади

4. Сервери (автор — Юрій Знов’як)

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

Корпорація має N серверів, які занумеровано натуральними числами від 1 до N. Кожен сервер займає одну полицю в серверній стійці. Всього у стійці N полиць, і їх також занумеровано натуральними числами від 1 до N. У зв’язку з заміною обладнання виникла потреба переставити сервери. Проблему ускладнено тим, що деякі пари серверів потрібно з’єднати кабелем напрямý. Довжина кабелю, що з’єднує пару серверів, дорівнює різниці номерів полиць, на яких розташовані ці сервери. Допоможіть розмістити сервери так, щоб сумарна довжина затраченого кабелю була найменшою.

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

Вхідні дані
Перший рядок вхідного файлу містить натуральне число N (2 ≤ N ≤ 20).

Другий рядок вхідного файлу містить ціле число M — кількість пар серверів, що потрібно з’єднати напрямý.

Наступні M рядків містять по одній парі різних натуральних чисел — номери серверів, що потрібно з’єднати напрямý. Кожна така пара зустрічається у переліку лише один раз.

Вихідні дані

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

Другий рядок вихідного файлу повинен містити перестановку чисел 1, 2, …, N, що відповідає оптимальному розташуванню серверів: на j-му місці має стояти номер сервера, який потрібно встановити на j-ту полицю.

Приклад

5. Стіна (автор — Данило Мисак)

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

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

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

Вхідні дані
У першому рядку вхідного файлу вказано натуральне число t ≤ 5 — кількість тестів у файлі. Далі йде t блоків, що відповідають t різним тестам. Блоки не розділено порожніми рядками.

У першому рядку кожного блоку вказано натуральне число n ≤ 10 000 — кількість рекламних оголошень на стіні.

У (i + 1)-му рядку блоку (1 ≤ i ≤ n) вказано параметри i-го оголошення: натуральні числа x_i , y_i , w_i , h_i , що не перевищують 10 000,— відповідно відстань від лівої сторони оголошення до лівого краю стіни, відстань від верхньої сторони оголошення до верхньої межі стіни, ширина й висота i-го оголошення.

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

Приклад

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

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

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

У третьому тесті до двох оголошень із другого тесту додається ще одне. Хоч оголошення можуть наклеїти в такому порядку, що Петрик однозначно зможе його відновити (наприклад, у порядку, в якому вони вказані у вхідному файлі), але їх можуть наклеїти й так, що порядок однозначно відновити неможливо (приміром, спочатку «середнє» оголошення, а потім два інших).

6. ЗНО (автор — Дмитро Кордубан)

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

Аудиторія для проведення ЗНО (зовнішнього незалежного оцінювання) містить N рядів по M парт в кожному. За кожною партою сидить не більше ніж один учень, а місця визначаються жеребкуванням. Незважаючи на це, може трапитись, що учні з однієї школи сидять поруч одне з одним. Відповідальний за проведення ЗНО в одному класі нудьгує і вирішує визначити «якість» розташування учнів за партами.

Запровадимо прямокутні координати парт таким чином: (ряд, місце). Назвемо відстанню між учнями за партами з координатами (x, y) та (x', y') таку величину:

Назвемо якістю розсадки у класі найменшу відстань між двома учнями з однієї школи.

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

Вхідні дані
Перший рядок вхідних даних містить два натуральних числа N, M — кількість рядів у класі й кількість парт в одному ряді.

Наступні N рядків містять по M цілих чисел, що задають розташування учнів: j-те число (i + 1)-го рядка дорівнює нулеві, якщо парта з координатами (i, j) порожня, інакше — номеру школи учня, який сидить за цією партою. Номери шкіл — натуральні числа від 1 до 2³¹ – 1 включно.

Вхідний файл містить принаймні два однакових номери шкіл.

В усіх тестах NM ≤ 2∙10⁵. У 30% тестів NM ≤ 10³.

Вихідні дані

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

Приклад

3 5
145 171 0  38 100
 38   0 0 208 171
  0 145 0 100 145