To jest zadanie komunikacyjne.
Dwa programy, Alice i Bob, grają w następującą grę kooperacyjną.
Dane są liczby całkowite $A$ i $B$ spełniające $0 \le A, B < 2^{64}$. Początkowo tylko Alice zna $A$, a tylko Bob zna $B$. Niech $C := \min(A, B)$. Celem jest, aby zarówno Alice, jak i Bob byli w stanie wypisać $C$.
Aby wymieniać informacje, Alice i Bob mogą wywoływać następujące funkcje:
send(x): Wyślij 1-bitową wartość $x$ do drugiego programu. To wywołanie nie kończy się, dopóki drugi program nie wywołareceive().receive(): Odbierz 1-bitową wartość od drugiego programu i zwróć ją. To wywołanie nie kończy się, dopóki drugi program nie wywołasend().
Łączna liczba wywołań send() wykonanych przez Alice i Boba razem nie może przekroczyć $76$. To samo dotyczy receive().
Po zakończeniu komunikacji każdy program musi wywołać dokładnie jeden raz następującą funkcję:
answer(x): Zadeklaruj, że wartością $C$ jest $x$. Natychmiast po wywołaniu tej funkcji program musi zakończyć działanie.
Gra kończy się sukcesem, jeśli zarówno Alice, jak i Bob poprawnie podadzą wartość $C$.
Napisz dwa programy, Alice i Bob, które zawsze odnoszą sukces w tej grze.
Protokół interakcji
To jest interaktywne zadanie komunikacyjne (twoje programy oraz sprawdzarka komunikują się przez standardowe wejście/wyjście). Twój program działający jako Alice oraz twój program działający jako Bob rozegrają grę za pośrednictwem sprawdzarki.
Uruchomienie programu
Twój program najpierw otrzymuje wejście w następującym formacie:
Player X
Tutaj Player jest napisem Alice lub Bob, a $X$ jest liczbą całkowitą spełniającą $0 \le X < 2^{64}$.
- Jeśli
PlayertoAlice, wówczas $A = X$. Od tego momentu twój program musi zachowywać się jak Alice. - Jeśli
PlayertoBob, wówczas $B = X$. Od tego momentu twój program musi zachowywać się jak Bob.
Następnie wywołuj send, receive oraz na końcu answer zgodnie z poniższym opisem.
send
Aby wywołać send(x), wypisz:
send x
Tutaj $x$ musi wynosić $0$ lub $1$.
To wywołanie nie kończy się, dopóki drugi program nie wywoła receive(). Otrzymasz werdykt Wrong Answer, jeśli zajdzie którakolwiek z poniższych sytuacji:
- drugi program zakończy działanie, podczas gdy ty czekasz,
- drugi program również wywoła
send(), podczas gdy ty czekasz, - łączna liczba wywołań
send()wykonanych przez Alice i Boba przekroczy $76$.
receive
Aby wywołać receive(), wypisz:
receive
Następnie wczytaj odebrany bit $x$ ze standardowego wejścia:
x
To wywołanie nie kończy się, dopóki drugi program nie wywoła send(). Otrzymasz werdykt Wrong Answer, jeśli zajdzie którakolwiek z poniższych sytuacji:
- drugi program zakończy działanie, podczas gdy ty czekasz,
- drugi program również wywoła
receive(), podczas gdy ty czekasz, - łączna liczba wywołań
receive()wykonanych przez Alice i Boba przekroczy $76$.
Jeśli podczas interakcji otrzymasz werdykt Wrong Answer, na wejściu zostanie podana wartość $-1$. Jeśli wczytasz $-1$, natychmiast zakończ działanie programu, w przeciwnym razie możesz otrzymać Time Limit Exceeded.
answer
Aby wywołać answer(x), wypisz:
answer x
Tutaj $x$ musi być równe $\min(A, B)$. Po wywołaniu tej funkcji natychmiast zakończ działanie programu.
Uwaga
- Po każdym wypisaniu twój program musi opróżnić bufor standardowego wyjścia (flush); w przeciwnym razie możesz otrzymać Time Limit Exceeded.
- Program sprawdzarki, twój program działający jako Alice oraz twój program działający jako Bob działają jednocześnie. Limity czasu i pamięci są mierzone jako suma dla wszystkich trzech procesów, dlatego zostaw odpowiedni zapas zarówno dla czasu, jak i pamięci.
- Program sprawdzarki zużywa maksymalnie około $50$ ms oraz $5$ MiB.
- Będziesz operować na liczbach całkowitych z przedziału od $0$ do $2^{64} - 1$. Uważaj na przepełnienie typu (overflow).
Przykłady
Przykładowe wejście 1
Alice 31 1
Przykładowe wyjście 1
send 0 receive send 1 answer 25
Przykładowe wejście 2
Bob 25 0 1
Przykładowe wyjście 2
receive send 1 receive answer 25