Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_16_06 - Znaki dymne

Północno-zachodnie rejony Bajtocji są wciąż zamieszkiwane przez rdzenną ludność indiańską. Najpotężniejsze plemię Bajtohikanów przejawia ostatnio wrogie zamiary względem równie walecznego plemienia Bitrokezów. W związku z tym naczelny wódz Bitrokezów - Rączy Gigabit nakazał opracowanie szybkiego systemu przekazu informacji pomiędzy wioskami plemienia, na wypadek ataku ze strony Bajtohikanów.

Najmędrsi z plemiennej starszyzny opracowali system, który zapewnia, że wiadomość o zagrożeniu dotrze do wszystkich wiosek. Ustalono, że do przekazu informacji wykorzystana zostanie sprawdzona metoda znaków dymnych. W każdej wiosce przy gotowym do podpalenia stosie stale czuwać będą strażnicy. Jeśli osada stanie w obliczu zagrożenia, strażnicy rozpalą ogień i znakami dymnymi przekażą informację do innych wiosek znajdujących się w pobliżu. Mieszkańcy tych wiosek w taki sam sposób przekażą wiadomość dalej. Strażnicy w poszczególnych wioskach mogą różnić się sprawnością w rozpalaniu ogniska i nadawaniu znaków, dlatego czas potrzebny na przekazanie informacji oraz jej zasięg są wielkościami charakterystycznymi dla każdej osady.

System przewiduje również, że do przekazywania informacji można wykorzystywać posłańców. Jest to metoda, z której należy korzystać tylko wtedy, jeśli dzięki temu informacja szybciej dotrze do jakiejś osady niż za pomocą znaków dymnych. W pewnych sytuacjach może to też być jedyny sposób poinformowania wioski, jeśli ta nie leży w zasięgu znaków dymnych żadnej z pozostałych osad. Posłaniec porusza się na galopującym koniu i na przekazanie wiadomości potrzebuje tyle sekund, ile wynosi odległość pomiędzy wioskami wyrażona w sekundach końskiego galopu (skg), zaokrąglona w dół do liczby całkowitej. Jeśli miałaby zajść sytuacja, że kilku posłańców dociera jednocześnie do tej samej wioski, to jest to bezcelowe - należy wysłać tylko jednego posłańca.

Ponieważ do działania systemu ważne jest też dokładne określenie położenia wszystkich wiosek, starszyzna zadecydowała, aby wykorzystać do tego Pradawną Skałę Bogini Nieba i Ziemi Ataensic, znajdującą się na terenie zamieszkiwanym przez Bitrokezów. Dla każdej wioski obliczono dwie wartości: odległość jaka dzieli ją od Skały (wyrażoną w skg) oraz kierunek w jakim trzeba wyruszyć z osady, aby dojść do Skały. Kierunki oznaczono liczbami od 0 do 359 zaczynając od północy i zgodnie z ruchem Słońca na niebie (0 - północ, 90 - wschód, 180 - południe, 270 - zachód). Każda wioska leży w innym miejscu.

Na podstawie danych dotyczących wiosek oraz wiedząc, która z nich jest zagrożona (czyli rozpoczyna nadawanie informacji) można odpowiedzieć na pytania dotyczące czasu, po jakim wszystkie wioski plemienia zostaną powiadomione oraz ilu posłańców trzeba będzie wykorzystać.

Wejście

W pierwszej linii liczba wiosek Bitrokezów n (2 ≤ n1111).
W n kolejnych liniach po cztery liczby całkowite charakteryzujące wioskę: d - odległość wioski od Skały wyrażona w skg (0 < d109), k - kierunek z wioski do Skały (0k < 360), t - czas (w sekundach) jaki strażnicy potrzebują na nadanie znaków dymnych (0 < t ≤ 106), r - zasięg znaków dymnych wyrażony w skg (0 < r ≤ 109)

Następnie liczba zapytań q (1q100).
W każdej z kolejnych q linii jedna liczba całkowita w (1 ≤ w n) oznaczająca numer zagrożonej wioski.

Wyjście

Dla każdego zapytania w osobnej linii dwie liczby całkowite: liczba sekund potrzebnych, aby informacja o zagrożeniu dotarła do wszystkich wiosek oraz liczba posłańców wykorzystanych do przekazania informacji.

Przykład

Wejście:
9
180 180 30 300
300 120 151 240
240 270 130 180
480 210 55 120
360 255 180 240
540 270 20 120
420 135 160 180
600 135 40 60
225 180 100 75
1
1 Wyjście: 341 2

Uwaga: W zadaniu obowiązują dość restrykcyjne limity czasowe.

Rysunek do przykładu:

Zagrożona jest wioska nr 1. Obok numeru każdej wioski w nawiasie okrągłym podano czas jaki strażnicy z tej osady potrzebują na nadanie znaków dymnych. W nawiasie kwadratowym podano czas po jakim informacja o zagrożeniu dociera do danej wioski.

Wioska nr 4 znajduje się poza zasięgiem znaków dymnych z innych osad, konieczne jest więc wysłanie do niej posłańca. Najkorzystniej jest go wysłać od razu z wioski nr 1 (na podróż trzeba 336 sekund) lub po 30 sekundach z wioski nr 9 (stąd posłaniec przybyłby po 306 sekundach). W obu przypadkach efekt będzie taki sam - informacja do wioski nr 4 dotrze po 336 sekundach.

Informacja do wioski nr 6 dotarłaby za pomocą znaków dymnych z wioski nr 5 po 340 sekundach. Korzystniejsze jest jednak wysłanie kogoś już po 30 sekundach z wioski nr 3. Posłaniec będzie miał do pokonania 300 skg.

Na przekazanie informacji z wioski nr 2 do wioski nr 7 przez posłańca, potrzeba 151 sekund. Dokładnie tyle samo czas zajmuje strażnikom z wioski 2 nadanie znaków dymnych. Angażowanie posłańca jest tu więc bezcelowe.


Dodane przez:Witold Długosz
Data dodania:2014-05-22
Limit czasu wykonania programu:1s-3s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.