KULE - Spheres

no tags 

Jaś ma pewną ilość kul spośród których wszystkie poza jedną są identyczne - ważą tyle samo. Kul jest bardzo dużo i sam nie potrafi stwierdzić która z nich różni się od pozostałych. Mając do dyspozycji wagę szalkową, pomóż Jasiowi w określeniu która to kula.

Wejście/Wyjście

W pierwszej linii znajduje się jedna liczba całkowita n [3 <= n <= 100 000], oznaczająca liczbę kul, które posiada Jaś. Kule są ponumerowane od 1 do n.

Masz do dyspozycji dwa rodzaje poleceń, które wydajesz Jasiowi (wypisujesz na standardowe wyjście):

  • WEIGHT m a1 a2 ... am b1 b2 ... bm

    Ważenie kul. Wszystkie liczby powinny być oddzielone spacjami i oznaczają kolejno: m - ilość kul do położenia na jednej szalce (na obu szalkach zawsze musi być tyle samo kul), a1, a2, ..., am - numery kul, które każesz Jasiowi położyć na lewej szalce, b1, b2, ..., bm - numery kul, które każesz Jasiowi położyć na prawej szalce.

    Po wykonaniu ważenia Jaś informuje Cię o wyniku (wczytujesz ze standardowego wejścia). Możliwe odpowiedzi to: LEFT - kule na lewej szalce są cięższe, RIGHT - kule na prawej szalce są cięższe, EQUAL - kule na obu szalkach ważą tyle samo.

    Po wykonaniu ważenia Jaś jest od razu gotowy, żeby wykonać następne polecenie.

    Pamiętaj jednak, że jeżeli ilość ważeń będzie zbyt duża Jaś może się znudzić...

  • ANSWER k

    Udzielenie odpowiedzi, gdzie k to numer kuli, przy czym jeżeli okazało się że szukana kula jest lżejsza od pozostałych należy tę liczbę poprzedzić znakiem '-'.

    Po tym poleceniu nie jesteś już potrzebny Jasiowi (Twój program powinien się zakończyć).

Przykład

Jaś: 3
You: WEIGHT 1 1 2
Jaś: LEFT
You: WEIGHT 1 1 3
Jaś: EQUAL
You: ANSWER -2

Uwaga: Program po wypisaniu każdej linii powinien opróżniać bufor wyjściowy, np. poleceniem fflush(stdout), bądź też na początku wykonania ustawić odpowiedni tryb buforowania, np. setlinebuf (stdout).



Added by:japi
Date:2010-09-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64