這是一道通信題。
兩個程式 Alice 與 Bob 進行以下的合作遊戲。
給定兩個整數 $A$ 與 $B$,滿足 $0 \le A, B < 2^{64}$。起初,只有 Alice 知道 $A$,只有 Bob 知道 $B$。設 $C := \min(A, B)$。目標是讓 Alice 與 Bob 都能輸出 $C$。
為了交換資訊,Alice 與 Bob 可以呼叫以下函式:
send(x):向另一個程式發送一個 1 位元(1-bit)的值 $x$。該呼叫在另一個程式呼叫receive()之前不會返回。receive():從另一個程式接收一個 1 位元的值並返回它。該呼叫在另一個程式呼叫send()之前不會返回。
Alice 與 Bob 呼叫 send() 的總次數之和不能超過 $76$。對於 receive() 也是如此。
通信結束後,每個程式必須恰好呼叫一次以下函式:
answer(x):宣告 $C$ 的值為 $x$。呼叫此函式後,程式必須立即終止。
如果 Alice 與 Bob 都正確回答了 $C$,則遊戲成功。
請編寫兩個程式 Alice 與 Bob,使它們在遊戲中總是成功。
互動格式
這是一道互動式通信題(你的程式與評測機透過標準輸入/輸出進行通信)。你扮演 Alice 的程式與扮演 Bob 的程式將透過評測機進行遊戲。
程式啟動
你的程式首先接收以下格式的輸入:
Player X
這裡,Player 是字串 Alice 或 Bob,而 $X$ 是一個滿足 $0 \le X < 2^{64}$ 的整數。
- 如果
Player是Alice,則 $A = X$。從此時起,你的程式必須表現為 Alice。 - 如果
Player是Bob,則 $B = X$。從此時起,你的程式必須表現為 Bob。
之後,請按照下文所述呼叫 send、receive,並最終呼叫 answer。
send
若要呼叫 send(x),請輸出:
send x
這裡,$x$ 必須是 $0$ 或 $1$。
該呼叫在另一個程式呼叫 receive() 之前不會返回。如果發生以下任何一種情況,你將被判定為 Wrong Answer:
- 另一個程式在你等待時終止,
- 另一個程式在你等待時也呼叫了
send(), - Alice 與 Bob 呼叫的
send()總次數超過 $76$。
receive
若要呼叫 receive(),請輸出:
receive
然後從標準輸入讀取接收到的位元 $x$:
x
該呼叫在另一個程式呼叫 send() 之前不會返回。如果發生以下任何一種情況,你將被判定為 Wrong Answer:
- 另一個程式在你等待時終止,
- 另一個程式在你等待時也呼叫了
receive(), - Alice 與 Bob 呼叫的
receive()總次數超過 $76$。
如果你在互動過程中被判定為 Wrong Answer,提供的輸入將為 $-1$。如果你讀取到 $-1$,請立即終止程式,否則可能會獲得 Time Limit Exceeded。
answer
若要呼叫 answer(x),請輸出:
answer x
這裡,$x$ 必須等於 $\min(A, B)$。呼叫此函式後,請立即終止程式。
說明
- 每次輸出後,你的程式必須重新整理標準輸出(flush);否則,你可能會獲得 Time Limit Exceeded。
- 評測程式、你扮演 Alice 的程式以及你扮演 Bob 的程式是同時執行的。時間限制與記憶體限制是這三者之和,因此請在時間與記憶體使用上留出足夠的餘量。
- 評測程式最多消耗約 $50$ ms 與 $5$ MiB。
- 你需要處理 $0$ 到 $2^{64} - 1$ 範圍內的整數。請注意溢位問題。
範例
範例輸入 1
Alice 31 1
範例輸出 1
send 0 receive send 1 answer 25
範例輸入 2
Bob 25 0 1
範例輸出 2
receive send 1 receive answer 25