In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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.
Napisz program, który:
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
.
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.
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.