Online MIPT programming contest | РУССКИЙ |
<PREV Problem: | NEXT> |
< |
---|
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#13 4 4 3 2 1 1 2 2 1 1 |
Output#1YES [1 ([4 -2] 3)] |
Input#25 3 3 3 2 1 1 2 4 |
Output#2NO |
Input#35 6 6 3 3 3 2 2 2 2 3 1 3 1 2 |
Output#3YES ([-6 [4 -3]] [-5 [1 2]]) |
Author:
Koshman Sergey
7 May 2006
© acm.mipt DevGroup The page was generated in 170ms |