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

Квадратики однієї паркетної плитки можуть бути забарвлені по-різному. Може існувати декілька типів плиток однакової форми, але забарвлених по-різному. Плитки різних типів можуть мати різну вартість. Кількість плиток кожного типу не обмежена. Плитки вирішується як завгодно повертати (на кути, кратні 90 градусам). Не дозволяється розламувати плитки, а також класти їх лицьовою стороною вниз.

Спочатку, якась частина підлоги може вже бути викладена плиткою.

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

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

У першому рядку вхідного файлу записано три числа: N, M (розміри кімнати) і K (кількість доступних видів плитки). 1N8, 1M8, 1K10. Далі йде опис бажаного розфарбовування підлоги. Опис є N строчок по M чисел в кожній, де 0 позначає білий колір, 1 — чорний, 2 — те, що квадрат вже викладений плиткою. У останніх строчках K знаходяться описи доступних типів плитки в наступному форматі:

<форма> <вартість> <забарвлення>

<Форма> — це число від 1 до 4, що описує форму плитки (див. малюнок вищий)

<Вартість> — це натуральне число, що не перевершує 10000, задаюче вартість однієї плитки такого типу

<Забарвлення> — це від одного до трьох чисел 0 або 1. Кількість чисел співпадає з кількістю квадратиків, з яких складається плитка. Числа задають кольори квадратиків плитки в тому порядку, в якому квадратики пронумеровані на малюнку.

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

У вихідний файл виведіть однину — мінімальну вартість укладання або –1, якщо необхідним чином укласти плитку неможливо.

Приклад

j.in

j.out

4 3 3

2 2 2

2 0 0

2 1 2

2 2 2

2 10 0 0

1 5 1

4 6 0 0 1

15



  1. Склад

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

до.in

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

до.out

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

3 секунди

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

16 мегабайт

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

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

Розміщувати вироби на складі дозволяється тільки так, щоб хоч би одна сторона виробу була паралельна якійсь із стенів складу, і, додатково, всі кути виробу знаходилися в точках перетину ліній розмітки складу. Малюнки 1,2,3 ілюструють неправильне положення виробів, а 4,5 – правильне.



Керівництво фірми дізналося, що склад планує відвідати Комісія з неефективного використання складських приміщень. Щоб уникнути виплати крупного штрафу, фірма вирішила в терміновому порядку помістити на склад вироби так, щоб на складі не залишилося вільного місця. При цьому було вирішено, що продукція, яка вже знаходиться на складі, переміщатися не буде.

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

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

У першому рядку вхідного файлу записано три цілі числа: N, M (розміри складу) і K (кількість виробів, які вже знаходяться на складі). Наступні K рядків містять по 6 цілих чисел — координати кутів відповідного виробу. Система координат введена так, що осі координат паралельні стінам складу і при цьому один з кутів складу має координати (0,0), а протилежний — (N,M).

Обмеження

1N4, 1M4

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

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

до.in

до.out

3 3 1

0 1 1 2 2 1

5

0 1 1 2 0 3

0 3 3 3 3 0

1 0 2 1 3 0

0 1 2 1 1 0

0 0 1 0 0 1



  1. Кубічний готель

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

l.in

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

l.out

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

3 секунди

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

16 мегабайт

У зв'язку з проведенням міжпланетного шашкового турніру було ухвалено рішення про будівництво орбітального готелю. Вона повинна була бути великим кубом з N*N*N блоків – маленьких кубиків 1*1*1, і кожен блок повинен був бути забарвлений зовні з усіх боків в якійсь один колір. При цьому деякі блоки могли бути пофарбовані в один і той же колір.

Через рік були зроблені фотографії готелю з кожною з 6 сторін: спереду, зліва, ззаду, справа, зверху, знизу. За рік експлуатації могло трапитися так, що із-за неміцного кріплення деякі блоки, з яких був побудований готель, відірвалися і відлетіли у відкритий космос. Комісія з відновлення готелю хоче по зроблених знімках встановити максимальну можливу кількість блоків, що залишилися.

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

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

У першому рядку вхідного файлу знаходиться число N — розмір готелю (1≤N≤10). На наступних рядках N записані види готелю з 6 сторін (у наступному порядку: спереду, зліва, ззаду, справа, зверху, знизу). Кожен такий вигляд є таблицею N*N, в якій різними заголовними латинськими буквами позначені різні кольори, а символом «.» (крапка) — те, що в цьому місці можна буде дивитися прямо крізь готель. Два послідовні види відділяються один від одного рівно одним пропуском в кожній з N рядків.

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

Вхідні дані коректні, тобто у вхідному файлі описаний стан, який може вийти.

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

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

Приклад

l.in

l.out

3

.R. YYR .Y. RYY .Y. .R.

GRB YGR BYG RBY GYB GRB

.R. YRR .Y. RRY .R. .Y.

11

2

ZZ ZZ ZZ ZZ ZZ ZZ

ZZ ZZ ZZ ZZ ZZ ZZ

8


Сторінка из



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