Od przybytku głowa (nie) boli»Zadanie 1
o zadaniu...
- Zadanie olimpijskie: VI Olimpiada Informatyczna
- Zadanie pochodzi z artykułu Od przybytku głowa (nie) boli
- Publikacja w Delcie: marzec 2008
- Publikacja elektroniczna: 20-12-2010
Dana jest triangulacja n-kąta wypukłego za pomocą nieprzecinających
się przekątnych. Jeden z trójkątów tej triangulacji jest pomalowany
na czarno. Dwaj gracze na przemian odcinają od wielokąta po jednym
trójkącie. Gracz, który odetnie czarny trójkąt, wygrywa. Na wejściu
mamy liczbę n oraz opis triangulacji w postaci listy
trójek
definiujących kolejne trójkąty (wierzchołki wielokąta są
ponumerowane kolejno od 1 do n). Czarny trójkąt jest wymieniony jako
pierwszy. Musimy odpowiedzieć na pytanie: który gracz ma strategię
wygrywającą?


(jeśli
jest parzyste wygrywa gracz, który rozpoczyna grę), a i sama
strategia jest prosta i brzmi: odcinaj cokolwiek, byle nie odsłonić czarnego
trójkąta z dwóch stron. Całe zadanie można więc rozwiązać w czasie stałym,
sprawdzając jedynie czy czarny trójkąt leży na brzegu (jego współrzędne
to wówczas trzy kolejne liczby modulo
), a jeśli nie, to czy
. Nie trzeba, a wręcz nie warto, wczytywać nadmiarowego opisu
triangulacji!