COCI '23 Contest 5 #1 Zlagalica

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Little Maja has always loved puzzles. And since everyone knew that for a long time now, it is no wonder that one sunny day, Maja received an odd puzzle as a gift.

This puzzle has n pieces. Each piece has a rectangular shape and is of a certain color. Also, each piece has 2 numbers written on its back: u and d. After a period of skillfully combining pieces and trying to fit them together, Maja figured out the meaning of those numbers.

She found out that the number u represents "direction", in other words, does the next piece of the puzzle connect with the current one from the upper or from the right side of the current piece. The number d specifies the starting column/row where we connect the next piece of the puzzle with the current one. In more detail:

  • If u is equal to 0, we add the next piece above the current one by connecting its bottom left corner with the current piece's top edge at column d.
  • If u is equal to 1, we add the next piece to the right by connecting its bottom left corner with the current piece's right edge at row d.

Let's demonstrate this for pieces colored in colors a and b. Picture 1 shows the case where u = 0, and d = 3. Picture 2 shows the case when u = 1 and d = 3. (In both cases, u and d represent the numbers written on the back of the piece colored a).

Picture 1

Picture 2

Maja has grown tired of this puzzling puzzle, but her curiosity knows no bounds! That's why she's asking for your help. She's interested in knowing, for a given description of every piece of the puzzle and the sequence of their placement, what will the completed puzzle look like? Write a program that prints the dimensions (height and width) of the completed puzzle, as well as its final appearance within a rectangle of the same height and width, where . represents places where there is no part of the puzzle.

Input Specification

In the first row, there is a single integer n (1 \le n \le 20), the number of puzzle pieces.

In the i-th of next n rows, there is 1 character and 4 integers, in the order b_i, r_i, s_i, u_i, d_i, the description of the i-th piece:

  • b_i will always be a lowercase letter of the english alphabet, and it represents the color of the i-th puzzle piece.
  • r_i and s_i (1 \le r_i, s_i \le 10) represent the number of rows and the number of columns of the i-th puzzle piece.
  • u_i and d_i (0 \le u_i \le 1, 1 \le d_i \le r_i, s_i (depends on u_i)) are the numbers on the back of i-th puzzle piece, same as in the task statement.

In the last row of input there are n integers, the order in which pieces are connected, where the i-th (1 \le i \le n) number represents the i-th puzzle piece in the input. Each puzzle piece will appear in the sequence exactly once.

Output Specification

Print the height and width of the completed puzzle. After that, print the appearance of the puzzle within a rectangle of the same height and width. In the places within the rectangle where there is no part of the puzzle, print ..

Constraints

Subtask Points Constraints
1 17 The order of connecting the puzzle pieces will be identical to the order of inputting them.
2 12 For each puzzle piece: u = 0.
3 12 For each puzzle piece: u = 1.
4 9 No additional constraints.

Sample Input 1

2
a 3 4 0 3
b 2 5 1 1
1 2

Sample Output 1

5 7
..bbbbb
..bbbbb
aaaa...
aaaa...
aaaa...

Sample Input 2

2
a 3 4 0 3
b 2 5 1 1
2 1

Sample Output 2

4 9
.....aaaa
.....aaaa
bbbbbaaaa
bbbbb....

Sample Input 3

4
g 9 5 0 2
a 3 2 1 1
c 5 10 0 2
p 8 7 1 6
4 3 2 1

Sample Output 3

18 17
..........ggggg..
..........ggggg..
..........ggggg..
..........ggggg..
..........ggggg..
..........ggggg..
..........ggggg..
..........ggggg..
........aaggggg..
........aa.......
ppppppp.aa.......
pppppppcccccccccc
pppppppcccccccccc
pppppppcccccccccc
pppppppcccccccccc
pppppppcccccccccc
ppppppp..........
ppppppp..........

Comments

There are no comments at the moment.