Polish version    English version  
  Historia OI -> XII OI 2004/2005


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodników
Przydatne zasoby
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN

Zadanie: Lot na marsa


Bajtazar postanowił polecieć na Marsa, aby zwiedzić istniejące tam stacje badawcze. Wszystkie stacje na Marsie leżą na okręgu. Bajtazar ląduje w jednej z nich, a następnie porusza się za pomocą specjalnego pojazdu, który jest napędzany odpowiednim paliwem. Litr paliwa starcza na metr jazdy. Zapasy paliwa są jednak niewielkie, różne jego ilości znajdują się w różnych stacjach. Bajtazar może tankować paliwo na stacji, na której w danym momencie się znajduje, nie więcej jednak, niż dostępna tam jego ilość (pojemność baku jest nieograniczona). Musi mu to wystarczyć na dojazd do następnej stacji. Bajtazar musi zdecydować, gdzie powinien wylądować, tak żeby mógł zwiedzić wszystkie stacje. Na koniec Bajtazar musi wrócić do stacji, w której wylądował. W czasie podróży Bajtazar musi poruszać się po okręgu, stale w wybranym jednym z dwóch kierunków.

Zadanie

Napisz program, który:
  • wczyta ze standardowego wejścia liczbę stacji na Marsie, odległości między nimi i ilości paliwa dostępne w każdej z nich,
  • dla każdej stacji sprawdzi, czy Bajtazar może tam wylądować, czyli czy zaczynając tam i jadąc w wybranym przez siebie kierunku, może objechać wszystkie stacje i wrócić do swojej rakiety,
  • wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia zapisana jest jedna liczba całkowita N (3 <=  N <=  1 000 000). Jest to liczba stacji na Marsie. Stacje są ponumerowane od 1 do N. W kolejnych N wierszach znajdują się opisy poszczególnych stacji i odległości między nimi. W i + 1-szym wierszu znajdują się dwie liczby całkowite: pi oraz di (pi<= 0, di > 0). Pierwsza z nich to ilość paliwa w litrach dostępna na i-tej stacji. Druga z nich to odległość w metrach pomiędzy stacją i a i + 1 (oczywiście dN to odległość między stacją N a 1). Łączna ilość dostępnego paliwa, a także suma wszystkich odległości między stacjami nie przekracza 2 000 000 000.

Wyjście

Na standardowe wyjście powinieneś wypisać N wierszy. W i-tym wierszu powinno znajdować się słowo TAK, jeśli Bajtazar może wylądować w stacji numer i lub NIE w przeciwnym wypadku.

Przykład

Dla danych wejściowych:
5
3 1
1 2
5 2
0 1
5 4
poprawną odpowiedzią jest:
TAK
NIE
TAK
NIE
TAK




Wersja do druku