COCI '19 Contest 2 #3 Checker

View as PDF

Points: 12 (partial)
Time limit: 3.0s
Memory limit: 512M

Problem types

"…fool me once, shame on — shame on you. Fool me — you can't get fooled again."" – W.

In this task, we will observe regular polygons that have each of their sides coloured in one of three colours and whose vertices are denoted from to in clockwise order. A triangulation of a polygon is a decomposition of its area into a set of non-overlapping triangles whose sides either lie on the sides of the polygon or its internal diagonals. Of course, in this task, each of the diagonals used for polygon triangulation is also coloured in one of three colours.

The triangulation is said to be patriotic if each of its triangles has all three sides of different colours. Your task is to determine whether a given polygon with its diagonals is triangulated and whether that triangulation is patriotic.

Input

The first line contains the subtask number this particular test case belongs to (see the table in the scoring section). If your solution doesn't care about that, simply read the number and feel free to ignore it.

The second line contains an integer from the task description.

The third line contains an integer consisting of digits which represent the colours of polygon sides. More precisely, the first digit represents the colour of side , the second digit represents the colour of side , and so on until the -th digit which represents the colour of side . The colours will always be denoted with digits , and .

Each of the next lines contain a description of one diagonal in the form X Y C, where and are polygon vertices and is the colour of the diagonal . Each line describes a valid diagonal, i.e., vertices and will neither be equal nor neighbouring.

Output

If the input polygon is not correctly triangulated, you should output neispravna triangulacija (invalid triangulation in Croatian).

If the input polygon is correctly triangulated but the triangulation is not patriotic, you should output neispravno bojenje (invalid colouring in Croatian).

If the input polygon is correctly triangulated and that triangulation is patriotic, you should output tocno (correct in Croatian).

Scoring

1 12 2 17 3 23 , the output is either neispravna triangulacija or tocno
4 23 , the output is either neispravno bojenje or tocno
5 35 Unlike the task Trobojnica from round 1, if your program correctly outputs the first line in each test case of a certain subtask, you will score of the points allocated for that subtask.

1
5
12113
1 3 3
2 5 2

Sample Output 1

neispravna triangulacija

1
4
1212
1 3 2

Sample Output 2

neispravno bojenje

1
7
1223121
1 3 3
3 5 1
5 7 3
7 3 2

tocno

Explanations 