Polish version    English version  
  Olympic camps


 News
 About Olympic
 History of OI
 OI books
 National team
 Olympic camps
III camp 2002
IV camp 2003
V camp 2005
VI camp 2005
 Photo gallery
 Links
 SIO
 MAIN
This document is not available in English version.

III Obóz im. A. Kreczmara 2002

Zadanie: ogr
Autor: Marcin Stefaniak
Ogród

dzień pierwszy 5 sierpnia 2002
Plik źródłowy: ogr.??? (np. pas, c, cpp)
Plik wejściowy: ogr.in
Plik wyjściowy: ogr.out

Architekt Numernabis buduje pałac dla Cezara. Rzecz jasna, taki pałac nie może się obejść bez wspaniałego kolistego ogrodu. W ogrodzie wytyczono ścieżki. Ścieżki spotykają się w skrzyżowaniach. Każda ścieżka łączy dwa różne skrzyżowania albo prowadzi od skrzyżowania do jednego z wyjść z ogrodu. Do każdego z wyjść prowadzi dokładnie jedna ścieżka. Z jednego skrzyżowania prowadzi najwyżej jedna bezpośrednia ścieżka do wyjścia. Ścieżki nie przecinają się, nie ma też tuneli ani estakad. Z każdego skrzyżowania można dojść wzdłuż ścieżek do każdego innego skrzyżowania oraz do wyjścia.

Poletka między ścieżkami mogą być obsadzone palmami, kwiatami albo też oliwkami (na więcej nie pozwala klimat i umiejętności Numernabisa). Każde poletko będzie obsiane jednym rodzajem roślinności.

Ponieważ są 3 rodzaje roślin, więc Numernabis (a jest on nowoczesnym architektem) zaplanował, że w każdym skrzyżowaniu zejdą się dokładnie 3 ścieżki. Co więcej, zamierza on tak rozplanować roślinność, żeby w każdym skrzyżowaniu spotykały się pola obsiane wszystkimi trzema rodzajami roślin ozdobnych. Coś mu jednak nie wychodzi, może nie da się tego zrobić?

Pomóż biednemu Numernabisowi i uratuj go od krokodyli! Napisz program, który wyznaczy, czy dla danego planu ogrodu da się tak posadzić rośliny, jak wymaga nowoczesna sztuka konstruowania ogrodów.

Wejście

W pliku ogr.in znajduje się opis ogrodu:

  • W pierwszym wierszu znajduje się liczba całkowita n (1 <=
  • n <= 10000) oznaczająca liczbę skrzyżowań ogrodu. Skrzyżowania ponumerowane są od 1 do n.
  • W każdym z kolejnych n wierszy znajdują się trzy liczby całkowite x, y, z rozdzielone pojedynczymi odstępami (0 <= x,y,z <= n). Liczby w wierszu o numerze i+1 oznaczają, dokąd prowadzą ścieżki z i-tego skrzyżowania, podane zgodnie z ruchem wskazówek zegara. Przy tym 0 oznacza, że dana ścieżka prowadzi do wyjścia, a każda inna liczba oznacza nr skrzyżowania.

Wyjście

Plik wyjściowy ogr.out powinien zawierać odpowiedź - jedno słowo TAK lub NIE, będące odpowiedzią na pytanie, czy w ogrodzie da się tak posadzić roślinność, jak chce architekt.

Przykład

Dla pliku wejściowego ogr.in:

4
0 2 4
1 0 3
2 0 4
1 3 0

poprawną odpowiedzią jest plik wyjściowy ogr.out:

TAK



Print friendly version