Завдання № 20
відбірково-тренувальних зборів
команди міста Києва


за матеріалами ІІІ (міського) етапу 2007 року

1. Квадрат Рубика

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


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

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

 5  5  1  3 
 3  4  5  4 
 1  5  1  4 
 4  1  3  3 
 5  5  1  3 
 4  5  4  3 
 1  5  1  4 
 4  1  3  3 
 4  5  1  3 
 1  4  5  4 
 3  5  1  4 
 5  1  3  3 
 5  5  1  3 
 3  4  5  4 
 1  5  1  4 
 4  1  3  3 

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

 3  4  1  1 
 4  1  4  2 
 1  2  3  3 
 2  3  2  4 

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

 2  4  1  1 
 1  1  4  2 
 4  2  3  3 
 3  3  2  4 
 1  1  4  2 
 1  1  4  2 
 4  2  3  3 
 3  3  2  4 
 1  1  4  2 
 1  1  4  2 
 3  3  2  4 
 3  3  2  4 
 1  1  2  2 
 1  1  2  2 
 3  3  4  4 
 3  3  4  4 

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

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

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

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

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

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

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

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

Приклад

square.insquare.out
2
2
3 4 1 1
4 1 4 2
1 2 3 3
2 3 2 4
3
5 5 5 5 5 5
5 1 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
4
-1
+1
+3
-3
-1







2. Гнізда

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


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

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

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

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

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

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

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

Приклад

nests.innests.outілюстрація
9
0 8
1 7
2 4
3 9
4 5
5 6
6 2
7 3
8 1
27