asyan.org
добавить свой файл
  1 2 3



вихідний файл необхідно видати K рядків. Кожен рядок повинен описувати відповідний її номеру прямокутник чотирма числами R C H W (R і C повинні описувати координати лівого нижнього кута прямокутника, а H і W — координати правого верхнього кута). Числа повинні розділятися пропуском.

Осі координат влаштовані таким чином: початок координат знаходиться в нижньому лівому кутку поля, а осі координат направлені уздовж сторін поля (вісь Ox — уздовж нижньої сторони, а вісь Oy — уздовж лівої сторони). Клітки поля мають розмір 1x1. Таким чином, координати лівого нижнього кута поля — (0,0), правого верхнього — (M,N). Відмітьте, що ви повинні вивести координати кутів прямокутників (як крапок) в цій системі координат, а не координати кутових кліток, покритих прямокутниками.

Приклад

f.in

f.out

4 5 2

0 2 2 2 2

0 2 2 2 2

1 1 2 2 2

1 1 0 0 0

0 0 2 2

1 1 5 4



  1. Різноколірні трикутники

Ім'я вхідного файлу:

g.in

Ім'я вихідного файлу:

g.out

Максимальний час роботи на одному тесті:

3 секунди

Максимальний об'єм використовуваної пам'яті:

16 мегабайт

Опуклий N-угольник розбитий непересічними діагоналями на трикутники. (Багатокутник називається опуклим, якщо будь-яка його діагональ лежить усередині нього.) Потрібно пофарбувати кожну сторону і кожну проведену діагональ в червоний або синій колір так, щоб у кожного трикутника були сторони як червоного, так і синього кольору.

Потрібно привести будь-яке з допустимих розфарбовувань.

Формат вхідних даних

У першому рядку записано одне число N (4N100) - кількість вершин багатокутника.

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

Формат вихідних даних

У вихідному файлі повинні бути 2N–3 рядки. Кожен рядок містить 3 числа: номери вершин, які сполучає дана сторона або діагональ і колір (1 - синій, 2 - червоний), в який Ви фарбуєте дану сторону або діагональ.

Приклади

g.in

g.out

4

1 3

1 2 1

2 3 1

3 4 1

4 1 1

1 3 2

6

1 3

3 5

5 1

1 2 1

2 3 1

3 4 1

3 5 2

4 5 1

5 6 2

5 1 1

6 1 2

1 3 2




  1. Втеча з космічної станції

Ім'я вхідного файлу:

h.in

Ім'я вихідного файлу:

h.out

Максимальний час роботи на одному тесті:

3 секунди

Максимальний об'єм використовуваної пам'яті:

16 мегабайт

Уявіть, що ви перебуваєте на службі в зовнішній розвідці Міжгалактичного Альянсу Республіканських Сил (МАРС). Одному з агентів розвідки крупно не повезло, і він був захоплений на засекреченій космічній базі. На щастя, зовнішній розвідці МАРС вдалося дістати план цієї бази. І ось тепер вам доручено розробити план втечі.

База є прямокутником розміром NхM, з усіх боків оточений стінами, і що складається з квадратних відсіків одиничної площі. База забезпечена K виходами, до одного з яких агентові необхідно добратися. У деяких відсіках бази знаходяться стіни. Ваш агент може переміщатися з відсіку в будь-якій з чотирьох сусідніх з ним, якщо в тому відсіку, куди він хоче переміститися, немає стіни.

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

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

Формат вхідних даних

У першому рядку вхідного файлу записані числа N і M (2N100, 2M100), задаючі розміри бази: N — кількість рядків в плані бази, M — кількість стовпців. У другому рядку записані початкові координати агента XA, YA (1XAN, 1YAM). Перша координата задає номер рядка, друга — номер стовпця. Рядки нумеруються зверху вниз, стовпці зліва направо.

Далі слідують N рядків по M чисел, задаючих опис стенів усередині бази: 1 відповідає стінці, 0 — її відсутності.

Далі в окремому рядку записано число H (0H1000) — кількість гіпертунелів. У подальших H рядках йдуть описи гіпертунелів. Кожен гіпертунель задається 4 числами: X1, Y1, X2, Y2 (1X1,X2N; 1Y1,Y2M) — координатами входу і виходу гіпертунеля. Ніякі два гіпертунелі не мають загального входу.

Після цього в окремому рядку слідує число K (1K10)— кількість виходів з бази. У подальших K рядках йдуть описи виходів з бази. Кожен вихід задається двома координатами X і Y (1XN; 1YM).

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

Формат вихідних даних

Якщо втеча неможлива, виведіть єдиний рядок з написом "Impossible". Інакше в першому рядку видайте число L - кількість відсіків в найкоротшому шляху втечі. У подальших L рядках послідовно виведіть координати відсіків найкоротшого шляху втечі. Якщо рішень декілька, то виведіть будь-яке з них.

Приклад

h.in

h.out

4 5

2 1

0 0 0 0 0

0 1 0 0 0

0 0 0 0 0

0 0 0 0 0

2

1 2 1 4

3 1 1 4

1

2 4


4

2 1

3 1

1 4

2 4


  1. Нерухома точка карти

Ім'я вхідного файлу:

i.in

Ім'я вихідного файлу:

i.out

Максимальний час роботи на одному тесті:

3 секунди

Максимальний об'єм використовуваної пам'яті:

16 мегабайт

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

Наситивши свій шлунок, Петя повернувся в кімнату і виявив, що його творіння здуло вітром на підлогу. Спочатку він занепокоївся тим, чи в порядку малюнок, але упевнившись, що все нормально, не почав поспішати і піднімати план з підлоги. Він пригадав слова вчителя географії, який в кінці уроку повідав їм якесь нетривіальне твердження і запропонував цікавим перевірити його на дозвіллі.

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

Формат вхідних даних

Кімната Петі і її план мають форму прямокутника. Перший рядок вхідного файлу містить два дійсні числа: ширину X і довжину Y кімнати Петі (1X1000, 1Y1000). Кімната розташована в декартовій прямокутній системі координат так, що кути кімнати розташовані в крапках з координатами (0,0) (X,0) (X,Y) (0,Y).

Другий рядок містить вісім дійсних чисел, що описують положення кутів плану кімнати в тій же самій системі координат. Спочатку задаються координати того кута плану, який відповідає куту кімнати з координатами (0,0), потім — (X,0), (X,Y), нарешті (0,Y). Гарантується, що вхідні дані коректні, тобто план є прямокутником, лінійні розміри плану знаходяться в повній відповідності з лінійними розмірами кімнати, план не виходить за межі кімнати.

Всі числа у вхідному файлі речові, задано з точністю 5 знаків після десяткової крапки. План виконаний в масштабі не менше 0.0001 і не більше 1. Масштаб не може бути рівний 1. Карта розташована лицьовою стороною вгору.

Формат вихідних даних

У перший рядок вихідного файлу виведіть 2 дійсних числа — координати нерухомої точки плану і підлоги. Відповідь потрібно видати з 3 знаками після десяткової крапки.

Приклад

i.in

i.out

10.00000 5.00000

3.00000 2.50000 1.00000 2.50000 1.00000 1.50000 3.00000 1.50000

2.500 2.083



  1. Узор

Ім'я вхідного файлу:

j.in

Ім'я вихідного файлу:

j.out

Максимальний час роботи на одному тесті:

5 секунд

Максимальний об'єм використовуваної пам'яті:

16 мегабайт

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

Плитки паркету, якими викладається пів кімнати, складаються з квадратиків 1x1, кожен з яких може бути або білим, або чорним. У свою чергу, кімната має розміри NXM. На плані кімнати вказано, який квадрат кімнати якого кольору повинен бути.

Існує декілька форм паркетних плиток:

1




1

2




1

2

3




1

2































3

Форма 1

Форма 2




Форма 3




Форма 4



<< предыдущая страница   следующая страница >>