Ini adalah soal komunikasi.
Dua program, Alice dan Bob, memainkan permainan kooperatif berikut.
Diberikan bilangan bulat $A$ dan $B$ dengan $0 \le A, B < 2^{64}$. Pada awalnya, hanya Alice yang mengetahui $A$, dan hanya Bob yang mengetahui $B$. Misalkan $C := \min(A, B)$. Tujuannya adalah agar baik Alice maupun Bob dapat mengeluarkan nilai $C$.
Untuk bertukar informasi, Alice dan Bob dapat memanggil fungsi-fungsi berikut:
send(x): Mengirimkan nilai 1-bit $x$ ke program lainnya. Pemanggilan ini tidak akan kembali sampai program lainnya memanggilreceive().receive(): Menerima nilai 1-bit dari program lainnya dan mengembalikannya. Pemanggilan ini tidak akan kembali sampai program lainnya memanggilsend().
Total banyaknya pemanggilan send() yang dilakukan oleh Alice dan Bob secara gabungan tidak boleh melebihi $76$. Hal yang sama berlaku untuk receive().
Setelah komunikasi selesai, masing-masing program harus memanggil fungsi berikut tepat satu kali:
answer(x): Menyatakan bahwa nilai $C$ adalah $x$. Segera setelah memanggil fungsi ini, program harus berhenti.
Permainan berhasil jika baik Alice maupun Bob menjawab $C$ dengan benar.
Tulislah dua program, Alice dan Bob, yang selalu berhasil dalam permainan tersebut.
Protokol Interaksi
Ini adalah soal komunikasi interaktif (program-program Anda dan juri berkomunikasi melalui masukan/keluaran standar). Program Anda yang berperan sebagai Alice dan program Anda yang berperan sebagai Bob akan memainkan permainan melalui juri.
Permulaan Program
Program Anda pertama-tama menerima masukan dalam format berikut:
Player X
Di sini, Player adalah string Alice atau Bob, dan $X$ adalah bilangan bulat dengan $0 \le X < 2^{64}$.
- Jika
PlayeradalahAlice, maka $A = X$. Mulai titik ini, program Anda harus berperilaku sebagai Alice. - Jika
PlayeradalahBob, maka $B = X$. Mulai titik ini, program Anda harus berperilaku sebagai Bob.
Setelah itu, panggil send, receive, dan terakhir answer sebagaimana dijelaskan di bawah ini.
send
Untuk memanggil send(x), keluarkan:
send x
Di sini, $x$ harus bernilai $0$ atau $1$.
Pemanggilan ini tidak akan kembali sampai program lainnya memanggil receive(). Anda akan dinilai Wrong Answer jika salah satu dari hal berikut terjadi:
- program lainnya berhenti saat Anda sedang menunggu,
- program lainnya juga memanggil
send()saat Anda sedang menunggu, - total banyaknya pemanggilan
send()oleh Alice dan Bob melebihi $76$.
receive
Untuk memanggil receive(), keluarkan:
receive
Kemudian bacalah bit $x$ yang diterima dari masukan standar:
x
Pemanggilan ini tidak akan kembali sampai program lainnya memanggil send(). Anda akan dinilai Wrong Answer jika salah satu dari hal berikut terjadi:
- program lainnya berhenti saat Anda sedang menunggu,
- program lainnya juga memanggil
receive()saat Anda sedang menunggu, - total banyaknya pemanggilan
receive()oleh Alice dan Bob melebihi $76$.
Jika Anda dinilai Wrong Answer selama interaksi, masukan yang diberikan adalah $-1$. Jika Anda membaca $-1$, segera hentikan program Anda, atau Anda mungkin mendapatkan Time Limit Exceeded.
answer
Untuk memanggil answer(x), keluarkan:
answer x
Di sini, $x$ harus sama dengan $\min(A, B)$. Setelah memanggil fungsi ini, segera hentikan program Anda.
Catatan
- Setelah setiap keluaran, program Anda harus melakukan flush pada keluaran standar; jika tidak, Anda mungkin mendapatkan Time Limit Exceeded.
- Program juri, program Anda yang berperan sebagai Alice, dan program Anda yang berperan sebagai Bob berjalan secara bersamaan. Batas waktu dan memori diukur sebagai jumlah dari ketiganya, jadi sisakan ruang yang cukup baik untuk waktu maupun penggunaan memori.
- Program juri menghabiskan paling banyak sekitar $50$ ms dan $5$ MiB.
- Anda akan menangani bilangan bulat dalam rentang $0$ hingga $2^{64} - 1$. Berhati-hatilah terhadap overflow.
Contoh
Contoh Masukan 1
Alice 31 1
Contoh Keluaran 1
send 0 receive send 1 answer 25
Contoh Masukan 2
Bob 25 0 1
Contoh Keluaran 2
receive send 1 receive answer 25