Написання програм PARK і CAVE (Завдання другого туру XII Всеукраїнської олiмпiади з iнформатики)

XII Всеукраїнська олімпіада з інформатики

Другий тур

1.  Парк

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

Завдання Написати програму PARK, яка буде знаходити одне з можливих розташувань дерев у парку.

Вхідні дані Вхідний текстовий файл PARK.DAT  у першому рядку містить кількість тестів. Кожен наступний рядок містить одне ціле число N - кількість видів (кольорів) дерев, які необхідно посадити в парку (3£N£100).

Приклад вхідних даних

2

3

4

Вихідні дані Вихідний текстовий файл PARK.SOL  має містити відповіді для всіх тестів з вхідного файлу в тому ж порядку. Для кожного тесту необхідно вивести або єдиний рядок з числом 0, якщо розташування неможливе, або N  рядків, перший з яких містить одне число, другий — два числа, N–й — N чисел — номерів кольорів дерев у розташуванні. Кольори нумеруються натуральними числами від 1 до N.

Приклад вихідних даних

2

3 1

1 2 3

0

2.  Печера

Гном Торин знайшов план кинутої печери, в якій мешкав гірський король Норус. На плані позначено місце, де знаходиться величезний скарб. Гірський король захистив своє багатство від шукачів скарбів, для чого розташував в печері L кам’яних блоків, що рухаються і можуть роздушити шукача, і які зупиняються коли скарб знайдено.

План подано у вигляді пpямокутної цілочисельної матpиці MxN, елементами якої може бути: -2 (скарб), -1 (стіна), 0 (порожнє місце), додатнє число K (елемент K–го блока). K–ий блок складається з усіх елементів, які позначені числом K. Блок не обов’язково зв’язаний, але всі його елементи рухаються синхронно. Нулі в крайніх рядках або стовпчиках матpиці означають входи до печери. Окремо вказано початковий напрямок руху кожного блоку (1 – вгору, 2 – праворуч, 3 – вниз, 4 – ліворуч).

Гном займає клітину-вхід. Після цього він рухається за такими правилами: на протязі кожної секунди пеpшим переміщується гном на пусту клітину з 4-х сусідніх (вгору, вниз, ліворуч чи праворуч) або залишається на місці. Потім на протязі тієї ж секунди переміщується кожен блок на одну клітину (вгору, праворуч, вниз, ліворуч): спочатку перший, за ним другий і т.д. Якщо перед будь–яким із елементів блока у напрямку його руху знаходиться стіна, край печери, скарб або інший блок, то на цьому ході блок не рухається, а напpямок його руху змінюється на протилежний. Якщо блок під час руху потрапив в клітину з гномом, то гном загине.

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

Вхідні дані Вхідний текстовий файл CAVE.DAT в першому рядку містить числа M, N та L—кількість блоків (3£M£75, 3£N£75, 0£L£1000). В наступних M рядках міститься по N цілих чисел — план печери. В наступних L рядках задано початкові напpямки руху блоків у порядку зpостання їх номерів.

Приклад вхідних даних

4 5 1

-1 -1 -1 -1 -1

-1 0 1 0 -1

0 0 0 -2 -1

-1 -1 -1 -1 -1

1

Вихідні дані Вихідний текстовий файл CAVE.SOL у першому рядку має містити число K — час пpоходження шляху в секундах. В наступних K+1 рядках — координати положення гнома в кожну секунду (починаючи з координат входу). Координати мають бути подані в порядку "рядок стовпчик". Якщо існує кілька шляхів, досить вказати один із них.

Приклад вихідних даних

5

3 1

3 2

2 2

2 3

2 4

3 4