Laserowy bilard [A]
Limit pamięci: 256 MB
Laserowy bilard jest ostatnim krzykiem mody wśród najbardziej snobistycznej części mieszkańców Bajtocji.
Stół do tej gry ma wymiary . Przy jego brzegach przymocowano bandę o szerokości , w której
zamocowano par nadajników laserowych. Po włączeniu wszystkich nadajników, stół zostaje pokryty poziomymi
promieniami laserowymi i pionowymi, tak że -ty promień poziomy () przecina się z -tym promieniem
pionowym () w punkcie o współrzędnych . Nadajniki są od siebie niezależne, zatem
można w danym momencie włączyć ich wybrany podzbiór.
Do gry w laserowy bilard używa się bili o średnicy . W momencie, gdy leżąca na stole bila przecina co najmniej
jeden z promieni lasera, zapala się sygnalizator trafienia.
Początkowo bila znajduje się w punkcie . Bilę wprawiono w ruch tak, że
jej początkowy wektor prędkości wynosił , i pozwolono jej toczyć się bez tarcia
przez jednostek czasu.
W przypadku trafienia w bandę, bila odbija się idealnie sprężyście.
Ile razy podczas tej operacji zapalił się sygnalizator trafienia
(wliczając, potencjalnie, chwilę początkową ruchu bili)?
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i ()
oznaczające wymiary stołu.
W drugim wierszu znajduje się słowo długości złożone z liter 0 i 1:
-ta litera tego słowa opisuje stan nadajnika emitującego -ty promień poziomy - litera 0
oznacza, że nadajnik jest wyłączony, zaś litera 1, że włączony.
W trzecim wierszu znajduje się -literowe słowo opisujące w analogiczny sposób nadajniki dla promieni pionowych.
W czwartym wierszu wejścia znajduje się liczba całkowita () oznaczająca liczbę
przypadków testowych. W kolejnych wierszach znajduje się po pięć liczb całkowitych
, , , , (, , ,
) wyznaczających początkową pozycję i prędkość bili oraz czas gry.
Wyjście
Na standardowe wyjście należy wypisać dokładnie wierszy, będących odpowiedziami dla kolejnych przypadków testowych.
Każda odpowiedź powinna zawierać liczbę całkowitą,
oznaczającą, ile razy zapalił się sygnalizator trafienia.
Przykład
Dla danych wejściowych:
4 6
1010
010110
1
5 2 1 1 8
poprawną odpowiedzią jest:
6
Autor zadania: Tomasz Idziaszek.