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
mishik`22 apr 2008`C++200.03415
ethanhunt`21 aug 2007`C++1100.35441
mishik`21 apr 2008`C++100.03480
topspin`16 jul 2009`Kylix300.02506
topspin`16 jul 2009`Kylix200.02517
topspin`16 jul 2009`Kylix100.02543
tomek`11 may 2006`C++309.18590
tomek`14 oct 2006`C++400.02597
ripatti`19 jun 2010`C++200.01612
rebaj`22 aug 2009`C++102.66672
JohnJones_001`03 jan 2008`C++100.01719
RAVEman`16 mar 2009`C++200.02759
dan`30 sep 2007`C++100.04831
marek.cygan`30 may 2007`C++100.21903
RAVEman`16 mar 2009`C++100.02916
 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
S → A | 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.

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

 © acm.mipt DevGroupThe page was generated in 180ms