Zadanie tygodnia
runda 19; kategoria Hard
Limit czasowy: 1s; Limit pamięciowy: 32MB
Czy pamiętacie zadanie Robaki [1] z Zawodów Stałych? Tym razem stoimy przed trudniejszym zadaniem!
Na pręcie długości umieszczono w pewnych miejscach wiele robaczków. Każdy z nich ma określony kierunek poruszania się - w kierunku lewego końca pręta, lub w kierunku prawego końca pręta. Każdy porusza się z tą samą stałą prędkością.
Robaczki są całkiem masywne (choć rozmiarem równe punktowi!) i gdy dwa spotkają się na pręcie idąc w przeciwne strony, oba w mgnieniu oka zmieniają kierunki - tak, jakby odbiły się od siebie. Jeśli jakiś robak dotrze do lewego lub prawego końca pręta, spada zeń i nie ma już po nim śladu.
Zadanie, jakie nasuwa się szybko - znająć początkowe położenia robaczków na pręcie i kierunki, w których zmierzają, odpowiedz, który z nich spadnie z pręta jako ostatni? Możesz założyć, że dane będą dobrane w ten sposób, że nie dojdzie do sytuacji, w której kilka robaków spadałoby w ostatniej chwili.
Wejście:
Pierwsza linia wejścia zawiera dwie liczby - oraz - odpowiednio liczbę robaków oraz długość pręta (, ). W kolejnych liniach znajdują się pary liczb cakowitych - odpowiednio położenie i kierunek robaczka. Pręt traktujemy jak odcinek . Wartość oznacza punkt na tym odcinku na którym znajduje się robaczek, za to wyznacza kierunek - mówi, że robaczek zmierza w kierunku punktu , , że w kierunku punktu . (, ).
Wyjście:
Wyjście powinno zawierać jedną liczbę - numer robaka, który spadnie z pręta jako ostatni. Robaki numerowane są od do zgodnie z kolejnością na wejściu.
Przykład:
Wejście:
Wyjście:
Odnośniki:
[1] http://informatyka.wroc.pl/node/542
[2] http://informatyka.wroc.pl/user
[3] http://informatyka.wroc.pl/user/register