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_27_03 - Ukryty skarb

Franek i Stefan bawią się w poszukanie skarbu. Gra toczy się w pewnym obszarze, w obrębie którego Franek ukrywa skarb (w wybranym przez siebie miejscu o współrzędnych całkowitych dodatnich), a Stefan, przy użyciu specjalnego elektronicznego skanera, musi ten skarb znaleźć. Użycie skanera polega po prostu na jego włączeniu, a wtedy na wyświetlaczu pojawia się jeden z dziewięciu komunikatów: "N", "E", "S", "W", "NE", "NW", "SE", "SW" lub "OK". Jeśli Stefan zobaczy na ekranie komunikat "OK", to oznacza, że znajduje się właśnie w miejscu ukrycia skarbu. Pozostałe komunikaty informują, w którym kierunku (względem miejsca użycia skanera) skarb się znajduje. Niestety, bateria zasilająca skaner jest na wyczerpaniu, więc należy używać go bardzo oszczędnie.

Napisz program, który na podstawie informacji o rozmiarze obszaru i odpowiedzi uzyskiwanych ze skanera, będzie wyznaczał współrzędne kolejnych miejsc, w których należy dokonać skanowania, tak aby w jak najmniejszej liczbie prób znaleźć skarb. 

Wejście/Wyjście

UWAGA! W zadaniu użyty jest specjalny sędzia, symulujący działanie skanera, co wymaga odpowiedniej interakcji Twojego programu.

W pierwszej linii wejścia znajduje się liczba całkowita t oznaczająca liczbę testów (1 ≤ t10000).

Dla każdego testu należy najpierw odczytać z wejścia dwie liczby całkowite X i Y oznaczające wymiary obszaru, w którym ukryty jest skarb. X to rozpiętość w kierunku wschód-zachód, a Y - północ-południe (1X, Y109). Wysunięty najbardziej na południowy-zachód punkt obszaru ma współrzędne (1,1).
Następnie Twój program powinien podawać na standardowe wyjście po dwie liczby całkowite x, y (1xX, 1yY) oznaczające współrzędne miejsca, w którym Stefan używa skanera, po czym odczytywać z wejścia komunikat wyświetlony na jego ekranie. Odczytanie komunikatu "OK" powinno skutkować przejściem do kolejnego z t testów. Po zakończeniu ostatniego testu, Twój program musi zakończyć działanie.

Liczba dopuszczalnych użyć skanera zależy od wymiarów obszaru. Jej przekroczenie skutkuje zakończeniem działania programu i komunikatem "błąd wykonania (other)".

Przykład

Wejście: 2
Wejście: 10 12
Wyjście (Twój program): 3 6
Wejście (Skaner): NE
Wyjście: 7 8
Wejście: SW
Wyjście: 5 7
Wejście: W
Wyjście: 4 7
Wejście: OK
Wejście: 1 1
Wyjście: 1 1
Wejście: OK 

UWAGA: Program po wypisaniu każdej linii powinien opróżniać bufor wyjściowy. Np. w C++ można to zrobić poleceniem fflush(stdout), a przy wykorzystaniu strumienia cout wystarczy wypisywaną linię zakończyć używając endl.


Dodane przez:Witold Długosz
Data dodania:2016-04-25
Limit czasu wykonania programu:1s-2s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.