COCI 2019/2020 - Contest 2 - Checker

View as PDF

Submit solution

Points: 1.45 (partial)
Time limit: 3.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2019/2020 - Contest 2
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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

Trong bài toán này, chúng ta sẽ quan sát một hình đa giác đều có ~N~ cạnh, mỗi cạnh được tô ~1~ trong ~3~ màu và các đỉnh được đánh số từ ~1~ đến ~N~ theo chiều kim đồng hồ. Phép chia tam giác của đa giác là sự phân chia đa giác thành các tam giác không chồng nhau sao cho các cạnh của các tam giác đó là cạnh của đa giác hoặc các đường chéo trong của đa giác đó. Tất nhiên, trong bài toán này, mỗi đường chéo được dùng vào phép chia tam giác trong đa giác cũng được tô ~1~ trong ~3~ màu.

Phép chia tam giác được gọi là hoàn hảo nếu với mỗi ~N - 2~ tam giác trong phép chia đó, ~3~ cạnh của tam giác đó thuộc vào ~3~ màu khác nhau. Nhiệm vụ của bạn là xác định xem với một đa giác cho trước cùng với các đường chéo của nó, phép chia tam giác đó có hoàn hảo hay không.

Input

Dòng đầu tiên chứa ~1~ số cho biết bộ thử nghiệm này thuộc về subtask bao nhiêu (xem bảng phân bố subtask). Nếu cách làm của bạn không quan tâm đến chuyện đó, chỉ cần nhập số bất kì và bỏ qua nó.

Dòng thứ hai chứa số nguyên ~N~.

Dòng thứ ba chứa số nguyên có ~N~ chữ số biểu diễn màu các cạnh của đa giác. Chữ số thứ nhất biểu diễn màu của cạnh ~(1, 2)~, chữ số thứ hai biểu diễn màu của cạnh ~(2, 3)~, cứ tiếp tục như vậy cho đến chữ số thứ ~N~ biểu diễn màu của cạnh ~(N, 1)~. Các màu sẽ được đánh số là ~1~, ~2~, và ~3~.

~N - 3~ dòng sau mỗi dòng chứa ~3~ số nguyên ~X, Y, C~ mô tả một trong các đường chéo, trong đó ~X~ và ~Y~ là đỉnh của đa giác và ~C~ là màu của đường chéo đó ~(1 \le X, Y \le N, 1 \le C \le 3)~. Mỗi dòng sẽ mô tả một đường chéo hợp lệ, nghĩa là, các đỉnh ~X~ và ~Y~ sẽ không trùng nhau hoặc kề nhau.

Output

Nếu phép chia tam giác trong input không hợp lệ, xuất ra neispravna triangulacija ("phép chia tam giác không hợp lệ" trong tiếng Croatia).

Nếu phép chia tam giác trong input hợp lệ nhưng phép chia đó không hoàn hảo, xuất ra neispravno bojenje ("tô màu không hợp lệ" trong tiếng Croatia).

Nếu phép chia tam giác trong input hợp lệ và phép chia đó hoàn hảo, xuất ra tocno ("chính xác" trong tiếng Croatia).

Sample Input 1

1
5
12113
1 3 3
2 5 2

Sample Output 1

neispravna triangulacija

Sample Input 2

1
4
1212
1 3 2

Sample Out 2

neispravno bojenje

Sample Input 3

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

Sample Output 3

tocno

Subtask:

  • Subtask ~1~: ~7~ test có ~4 \le N \le 300~.
  • Subtask ~2~: ~7~ test có ~4 \le N \le 2000~.
  • Subtask ~3~: ~9~ test có ~4 \le N \le 2 \times 10^5~, kết quả xuất ra là neispravna triangulacija hoặc tocno.
  • Subtask ~4~: ~9~ test có ~4 \le N \le 2 \times 10^5~, kết quả xuất ra là neispravno bojenje hoặc tocno.
  • Subtask ~5~: ~11~ test có ~4 \le N \le 2 \times 10^5~.

Giải thích các ví dụ:


Comments

Please read the guidelines before commenting.


There are no comments at the moment.