COCI '17 Contest 5 #2 Spirale

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

Little Stjepan often likes to go out with his friends and have fun in a popular nightclub in Zagreb. However, Stjepan sometimes drinks too much soda and gets light headed from all the sugar. Last night was an example of this, which is why Stjepan had the same image in his mind the whole time. It was a scribble of number spirals of some sort. Since he can't quite remember what the image looked like, but can describe it, he is asking you to reconstruct it for him.

Stjepan recalls that the image was of the shape of a table consisting of numbers written in N rows and M columns. Also, he recalls that there were K spirals in that table. For each spiral, the starting position is known, as well as the direction it's moving in, which can be clockwise and counter-clockwise. An example is shown in the images below. The spirals created Stjepan's image in exactly 10^{100} steps in the following way:

  1. Initially, the table is empty, and each spiral is in its own starting position.
  2. In each following step, each spiral moves to its next position. It is possible that, at times, the spirals leave the boundaries of the table, but also to return within it.
  3. After exactly 10^{100} steps, for each field in the table, the final value is the value of the earliest step in which one of the spirals touched that field.

Input Specification

The first line of input contains positive integers N, M (1 \leq N, M \leq 50) and K (1 \leq K \leq N \times M).

Each of the following K lines contains three positive integers X_i, Y_i, and T_i (1 \leq X \leq N, 1 \leq Y \leq M, 0 \leq T \leq 1), the starting position of the i^\text{th} spiral and its direction (0 - clockwise, 1 - counter-clockwise). No two spirals will begin in the same field.

Output Specification

You must output N lines with M numbers, representing the table after each spiral makes 10^{100} steps.


In test cases worth 50\% of total points, it will hold: N=M and K=1 and X_i=Y_i=\lfloor\frac{N+1}{2}\rfloor, i.e. X_i and Y_i will be equal to the integer division of N+1 with 2.

Sample Input 1

3 3 1
2 2 0

Sample Output 1

9 2 3
8 1 4
7 6 5

Sample Input 2

3 3 1
2 2 1

Sample Output 2

3 2 9
4 1 8
5 6 7

Sample Input 3

3 3 2
1 1 0
1 2 0

Sample Output 3

1 1 4
6 5 5
19 18 17

Explanation for Sample Output 3

For simplicity's sake, the letter A was added to the numbers from the first spiral, and the letter B to the numbers from the second spiral. Only the first 20 steps of the first spiral are shown, and 21 steps of the second spiral. The fields in gray are the fields from the table we're interested in, all other fields are out of the table's bounds, but are shown to illustrate the way the spirals move outside of the table.


There are no comments at the moment.