Lot na marsa
Limit pamięci: 32 MB
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 . Jest to liczba stacji na
Marsie. Stacje są ponumerowane od do . W kolejnych wierszach
znajdują się opisy poszczególnych stacji i odległości między nimi. W
-szym wierszu znajdują się dwie liczby całkowite: oraz
(, ). Pierwsza z nich to ilość paliwa w litrach
dostępna na -tej stacji. Druga z nich to odległość w metrach pomiędzy
stacją a (oczywiście to odległość między stacją a
). Łączna ilość dostępnego paliwa, a także suma wszystkich odległości
między stacjami nie przekracza .
Wyjście
Na standardowe wyjście powinieneś wypisać wierszy. W -tym wierszu
powinno znajdować się słowo TAK, jeśli Bajtazar może wylądować w
stacji numer 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
Autor zadania: Paweł Parys.