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

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

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

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

Вхідні дані

Перший рядок файлу містить натуральне число N (1 ≤ N ≤ 30000).
Другий рядок файлу містить N попарно різних цілих чисел, які розташовано відповідно у першому, другому, …, N-му елементі пам’яті на початку сортування. Всі числа — у межах від 0 до 30000 включно.

Вихідні дані
Файл має містити одне число M — найменшу можливу кількість операцій обміну між парами елементів пам’яті для досягнення впорядкування чисел.

Приклад

Для поданого прикладу даних можна запропонувати такі обміни:
16598 → 61598 → 51698 → 15698 → 95618 → 85619 → 15689.

2. Квадрат Рубика (автор Данило Мисак)

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

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

Комірки квадратної таблиці по 2n комірок у кожному рядку й по 2n комірок у кожному стовпчику, заповнено натуральними числами, що не перевищують 100. За один крок дозволено дзеркально відобразити («перегорнути») довільний рядок або стовпчик таблиці. Далі подано кілька прикладів здійснення такої операції: ліворуч подано початкове заповнення таблиці, а праворуч три таблиці — приклади заповнення таблиці після здійснення одного з можливих ходів. Виділено рядок або стовпчик, що було дзеркально відображено.

Невідомо, чи можливо за допомогою таких операцій отримати таблицю, у комірки кожного з чотирьох кутових квадратів розміру n на n якої було б записано однакові числа. Числа у різних кутових квадратах можуть бути відмінними одне від одного. Якщо це можливо, потрібно вказати послідовність операцій, яка приводить до бажаного результату. Наприклад, таку таблицю:

можна перетворити до потрібного вигляду за 4 кроки (виділено рядки та стовпчики, над якими було здійснено операцію на попередньому кроці):

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

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

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

У наступних 2n рядках блока міститься по 2n натуральних чисел, що задають початкове заповнення таблиці. При цьому 1 ≤ t ≤ 10, 1 ≤ n ≤ 100, а кожне з чисел, записаних в комірках таблиці, натуральне й не перевищує 100.

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

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

У наступних k рядках блоку потрібно описати відповідні операції у порядку виконання таким чином: вказати номер рядка або стовпчика, над яким було здійснено операцію. Нумерацію починають з одиниці, стовпчики рахують зліва направо, а рядки згори донизу. Якщо дзеркально відображається рядок, перед його номером ставиться знак «+» (без лапок), якщо стовпчик — знак «–».

Якщо початкове розташування чисел у комірках таблиці не дає можливості звести її до потрібного вигляду, єдиний рядок блоку має містити число «–1».

Приклад

3. Гнізда (автор Юрій Знов’як)

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

На вертикальній стіні будинку N сімей ластівок побудували свої гнізда таким чином, що жодні два гнізда не розташовані на одній вертикалі або горизонталі. Нещодавно ластівки вирішили підключити до Інтернету кожне з гнізд. Для цього у ластівки, що живе найвище, розмістили супутникову антену. Усім ластівкам, що живуть нижче, Інтернет підключать через гнізда, розташовані вище.

Технологія підключення Інтернету така. Від найвищого гнізда проводять 2 кабелі: один до найвищого гнізда ліворуч від даного і один до найвищого гнізда праворуч. Після цього дві множини гнізд (ліворуч і праворуч від найвищого) розглядаються абсолютно незалежно. Для обох частин проводиться підключення без урахування протилежної частини. Звісно, якщо в одній з частин немає гнізд, то кабель в цю сторону не протягують. Відстань між точками (x₁; y₁) та (x₂; y₂) вважається рівною |x₂ – x₁| + |y₂ – y₁|.

Завдання
Визначте найменшу загальну довжину кабелю, який потрібно придбати для підключення усіх гнізд. Розмірами гнізд знехтувати (вважайте їх точками). Розв’язання за O(N) набирає 100%, за O(N ln N) — 75%, за O(N²) — 30% балів.

Вхідні дані
Перший рядок містить натуральне число N. Наступні N рядків містять прямокутні цілі координати гнізда (x;y). Усі числа вхідного файлу за абсолютною величиною не перевищують 1 000 000 000. Гнізда подано у порядку збільшення їхніх абсцис x.

Тести
У всіх тестах N ≤ 250 000. У 30% тестів N ≤ 3 000, а у 75% тестів N ≤ 125 000.

Вихідні дані
Єдиний рядок файлу містить шукану найменшу загальну цілу довжину кабелю. Відповідь на всі тести не перевищує 10¹⁸.

Зауваження для учасників, що використовують С++
В цій задачі можливі дуже великі вхідні данні, тому не радимо користуватись модулем iostream для введення даних. Також printf() та fprintf() неправильно виводить числа типу long long.

Приклад

4. Згортка (автор Михайло Рибак)

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

Згорткою кортежу (a₁; a₂; ... ; a_k) називають таку суму добутків:

Послідовність додатних чисел {a_j} задано таким чином: згортка перших j членів дорівнює 4 ^j – 1. Легко впевнитись, що ця послідовність починається так: 1, 2, 6, 20, 70.

Завдання
Обчислити a_N  за даним N.

Вхідні дані
Єдиний рядок файлу містить число N, де 0 < N < 2000. Принаймні у половині тестів N < 200.

Вихідні дані
Єдиний рядок файлу містить цілу частину a_N.
Приклади

5. Комарі (автор Дмитро Кордубан)

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

Нахабні комарі атакували кімнату Петрика й розсілись на стелі перед початком своїх підступних дій. Перед тим як лягти спати, Петрик хоче знищити максимальну кількість комарів. Для цього він бере улюблений підручник з програмування і сильно підкидає його вгору. Всі комарі, що потрапили під удар, гинуть (навіть ті, що знаходилися на границі області влучання).

Стеля кімнати має форму прямокутника, на якому запроваджено прямокутну систему координат. Осі абсцис ОХ та ординат OY розташовано паралельно стінам кімнати. Товщиною підручника нехтуємо. В момент удару підручник знаходиться у площині стелі, а його сторони паралельні осям OX та OY.

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

Вхідні дані
Перший рядок вхідних даних містить невід’ємне ціле число N — кількість комарів на стелі. Наступні N рядків містять пари невід'ємних цілих чисел x_j і y_j — координати j-го комара на стелі. Останній (N + 2)-ий рядок містить 2 натуральних числа w і h — лінійні розміри підручника.

В усіх тестах N ≤ 10⁵, max{x_j, y_j} ≤ 10⁹, max{w, h} ≤ 10⁹.
В 70% тестів N ≤ 10⁴, max{x_j, y_j} ≤ 10⁴.
В 50% тестів N ≤ 10³, max{x_j, y_j} ≤ 10³.

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

Приклади

6. Пірати й золото (автор Володимир Ткачук)

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

Команда з N піратів знайшли скарб з M однакових золотих монет і хоче його розділити. Всі пірати мають різний вік, при чому пірат з номером j + 1 старший за пірата з номером j. Першим пропозицію, про те як поділити скарб висуває найстарший пірат. Він вказує, скільки золотих монет має отримати кожен учасник команди. Якщо цю пропозицію підтримує не менше половини всіх піратів, то її приймають, і гроші розподіляють відповідним чином. Інакше найстаршого з живих пірата вбивають, а скарб ділять між собою вже N – 1 пірат за таким самим принципом. Кожен пірат (перераховано у порядку важливості):

• хоче вижити;

• хоче отримати максимальну кількість монет;

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

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

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

Завдання
За відомими N і M визначте, скільки монет отримає кожний пірат.

Вхідні дані
В єдиному рядку файлу записано два цілих числа: N і M (1 ≤ N ≤10000, 0 ≤ M ≤ 1 000 000 000).

Вихідні дані
Файл містить N рядків по одному цілому числу в кожному рядку. У j-му рядку потрібно записати кількість монет, які отримає j-ий пірат. Якщо j-го пірата вб’ють, то в j-му рядку потрібно записати число –1.

Приклади