<ПРЕД Задача:
СЛЕД>
Задачу решили 19 пользователей: tomek, DD, marek.cygan, ethanhunt, dan, JohnJones_001, Romka, Stefan.Bialucha, mishik, WsemirZ, tourist, zloy_mipt, MIKseR, RAVEman, defrager, topspin, rebaj, ripatti, Dest.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Разрезание прямоугольника, I

Time limit = 10 секунд(ы)

Однажды Петя забыл убрать со стола в мастерской прямоугольный лист фанеры. На следующий день на том самом месте он обнаружил несколько фрагментов фанеры прямоугольной формы. Пила в мастерской позволяет распилить прямоуголный кусок фанеры на два прямоугольных куска. И, видимо, кто-то ночью практиковался в распиливании фанеры. Кусок фанеры было жалко. Петя собирался наклеить на него фотографии с последнего чемпионата ACM ... К сожалению, исходный кусок фанеры уже не восстановишь ... Но Петя не стал падать духом. Его заинтересовала следующая программистская задача: как из этих обрезков составить прямоугольный лист, который он вчера оставил? Помогите Пете: напишите программу, которая определяет схему складывания фрагментов, если, конечно, это возможно.
Composition sample and its description

Вход В первой строке числа Lx и Ly — исходного листа фанеры. Вторая строка содержит N, столько прямоугольников обнаружил Петя. Далее в N строках идёт N пар чисел (WIDTH и HEIGHT), задающих размеры найденных фрагментов (ширину и высоту). Все размеры целые в диапазоне [1..10000]. 2 ≤ N ≤ 20.

Выход. Выведите описание того, как нужно соединить кусочки, чтобы получить прямоугольник исходного размера. Описание определяется рекурсивно. Если S1 и S2 — описания некоторых промежуточных прямоугольников с одинаковой шириной, то [S1 S2] — это описания прямоугольника, составленного из этих двух путём постановки S1 над S2. Если S1 и S2 — описания некоторых промежуточных прямоугольников с одинаковой высотой, то (S1 S2) — это прямоугольник, составленный из этих двух путём постановки S2 справа от S1. Кроме того, перед описанием можно поставить знак минус "-" чтобы повернуть соответствующий прямоугольник на 90 градусов. Кроме того описание прямоугольника может быть просто номером кусочка. Таким образом, грамматика S описаний прямоугольников, составленных из кусочков, задается следующими правмилами

A → ( S+ )
B → [ S+ ]
RS → -S
SA | B | RS | <номер>
Где <номер> — это номер [1..N] фрагмента в том порядке, в котором они описаны на входе. Если невозможно сложить все прямоугольники в исходный лист, то выведите одну строчку, содержащую слово 'NO' без кавычек.

Вход#1
3 4
4
3 2
1 1
2 2
1 1
Выход#1
YES
[1 ([4 -2] 3)]

Вход#2
5 3
3
3 2
1 1
2 4
Выход#2
NO

Вход#3
5 6
6
3 3
3 2
2 2
2 3
1 3
1 2
Выход#3
YES
([-6 [4 -3]] [-5 [1 2]])

Автор:
Кошман Сергей
7 мая 2006

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 3.235.172.213