<PREV Problem:
NEXT>
Solved by 19 users: tomek, DD, marek.cygan, ethanhunt, dan, JohnJones_001, Romka, Stefan.Bialucha, mishik, WsemirZ, tourist, zloy_mipt, MIKseR, RAVEman, defrager, topspin, rebaj, ripatti, Dest.
UserDateAttemptTimeCMSC
mishik22 apr 2008C++200.03415 
ethanhunt21 aug 2007C++1100.35441 
mishik21 apr 2008C++100.03480 
topspin16 jul 2009Kylix300.02506 
topspin16 jul 2009Kylix200.02517 
topspin16 jul 2009Kylix100.02543 
tomek11 may 2006C++309.18590 
tomek14 oct 2006C++400.02597 
ripatti19 jun 2010C++200.01612 
rebaj22 aug 2009C++102.66672 
JohnJones_00103 jan 2008C++100.01719 
RAVEman16 mar 2009C++200.02759 
dan30 sep 2007C++100.04831 
marek.cygan30 may 2007C++100.21903 
RAVEman16 mar 2009C++100.02916 
Languages
C++
12
Kylix
4
FPC
2
C
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Cutted rectangle

Time limit = 10 second(s)

One day Petya forgot to take a sheet of veneer off the table in the workshop. The next day he found there some rectangle pieces. Too pitty... Looks like sombody was practising at night with new bougth fast saw. This saw can cut one rectangle into two rectangles... But Petya did not think much about this sheet, because of interesting algorithmic problem took his minds: Can he bring all those pieces together so that they would form sheet. Help Petya, compose a program that will determine the scheme of composing pieces together to form initial sheet, if it is possible.

Input In the first line you read Lx и Ly — OX and OY dimensions of the source veneer sheet. In the second line is N, the number of rectangles Petya has found. Next N lines have N number pairs WIDTH HEIGHT , describing sizes of the result rectangle pieces. All the sizes are integer in range [1..10000]. 2 ≤ N ≤ 20.

Output. First line should contain YES or NO. If Yes, than second line should contain description of composition scheme. It is bracket structure S with the following gramma:

A → ( S+ )
B → [ S+ ]
RS → -S
SA | B | RS | <номер>

Every S describes a rectangle, arranged of one or more fragments Petya had found. <number> is a number of a fragments (1, 2, .. N) in input data.
Composition sample and its description
Description "-S" corresponds to the rectangle S turned on 90 degrees. Two rectangles s1 and s2 coud be connected. Description "[s1 s2]" corresponds to putting s1 over s2. Description "(s1 s2)" corresponds to putting s2 to the right of s1. You can compose two rectangles, if they have equal lengths of corresponding sides. If there is no composing scheme of given fragments then output one line with 'NO'.

Input#1
3 4
4
3 2
1 1
2 2
1 1
Output#1
YES
[1 ([4 -2] 3)]

Input#2
5 3
3
3 2
1 1
2 4
Output#2
NO

Input#3
5 6
6
3 3
3 2
2 2
2 3
1 3
1 2
Output#3
YES
([-6 [4 -3]] [-5 [1 2]])

Author:
Koshman Sergey
7 May 2006

<PREV | Problem set | Search related messages | NEXT>


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

SW soft NIX
ID = 3.230.154.129