呢道係一道通信題。
兩個程式 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$ 範圍內嘅整數。請小心溢位(overflow)。
範例
範例輸入 1
Alice 31 1
範例輸出 1
send 0 receive send 1 answer 25
範例輸入 2
Bob 25 0 1
範例輸出 2
receive send 1 receive answer 25