Polish version    English version  
  O olimpiadzie -> Zadania -> VI OI 1998/1999


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
VI Olimpiada Informatyczna 1998/99

Zadanie: GRA
Autor: Grzegorz Jakacki
Gra w wielokąty

Zawody I stopnia
Plik źródłowy: GRA.??? (np. pas, c, cpp)
Plik wykonywalny: GRA.exe
Plik wejściowy: GRA.in
Plik wyjściowy: GRA.out

W grze w wielokąty uczestniczy dwóch graczy. Rekwizytem jest wielokąt wypukły o n wierzchołkach podzielony przez n-3 przekątne na n-2 trójkąty. Żadne dwie z tych przekątnych nie przecinają się poza wierzchołkami wielokąta. Jeden z trójkątów jest czarny, a pozostałe - białe. Gracze na przemian odcinają od wielokąta po jednym trójkącie, za każdym razem przecinając wielokąt wzdłuż jednej z danych przekątnych. Gracz, który odetnie czarny trójkąt wygrywa.
PRZYPOMNIENIE: Wielokąt jest wypukły, jeśli odcinek łączący dowolne dwa jego punkty jest całkowicie zawarty w wielokącie.

Zadanie

Napisz program, który:

  • czyta z pliku tekstowego GRA.IN opis rekwizytu do gry,
  • sprawdza, czy gracz rozpoczynający grę ma strategię wygrywającą,
  • zapisuje wynik do pliku GRA.OUT

Wejście

Pierwszy wiersz pliku wejściowego GRA.IN zawiera liczbę naturalną n, 4 <= n <= 50000. Jest to liczba wierzchołków wielokąta. Wierzchołki wielokąta są ponumerowane kolejnymi liczbami od 0 do n-1, zgodnie z ruchem wskazówek zegara.
Następnych n-2 wierszy zawiera opisy trójkątów w wielokącie. W wierszu o numerze i+1, 1 <= i <= n-2, znajdują się trzy liczby naturalne a, b, c oddzielone pojedynczymi odstępami. Są to numery wierzchołków i-tego trójkąta. Pierwszy trójkąt w ciągu jest czarny.

Wyjście

Plik wyjściowy GRA.OUT powinien składać się z jednego wiersza zawierającego jedno słowo:

  • TAK, jeśli gracz rozpoczynający grę ma strategię wygrywającą,
  • NIE, jeśli nie ma.

Przykład

Dla pliku wejściowego GRA.IN:

6
0 1 2
2 4 3
4 2 0
0 5 4

poprawną odpowiedzią jest plik tekstowy GRA.OUT:

TAK

Twój program powinien szukać pliku GRA.IN w katalogu bieżącym i tworzyć plik GRA.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę GRA.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonywalnej powinien być zapisany w pliku GRA.EXE




Wersja do druku