นี่คือโจทย์ประเภทการสื่อสาร (communication problem)
โปรแกรมสองโปรแกรม คือ 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 บิต $x$ ไปยังอีกโปรแกรมหนึ่ง การเรียกนี้จะไม่คืนค่าจนกว่าอีกโปรแกรมหนึ่งจะเรียกreceive()receive(): รับค่าขนาด 1 บิตจากอีกโปรแกรมหนึ่งและคืนค่านั้นกลับมา การเรียกนี้จะไม่คืนค่าจนกว่าอีกโปรแกรมหนึ่งจะเรียกsend()
จำนวนครั้งรวมของการเรียก send() โดย Alice และ Bob รวมกันจะต้องไม่เกิน $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()เช่นกันในขณะที่คุณกำลังรออยู่, - จำนวนครั้งรวมของการเรียก
send()โดย Alice และ Bob เกิน $76$ ครั้ง
receive
ในการเรียก receive() ให้พิมพ์:
receive
จากนั้นให้อ่านบิต $x$ ที่ได้รับจากข้อมูลนำเข้ามาตรฐาน:
x
การเรียกนี้จะไม่คืนค่าจนกว่าอีกโปรแกรมหนึ่งจะเรียก send() คุณจะถูกตัดสินเป็น Wrong Answer หากเกิดเหตุการณ์ใดเหตุการณ์หนึ่งต่อไปนี้:
- อีกโปรแกรมหนึ่งหยุดทำงานในขณะที่คุณกำลังรออยู่,
- อีกโปรแกรมหนึ่งเรียก
receive()เช่นกันในขณะที่คุณกำลังรออยู่, - จำนวนครั้งรวมของการเรียก
receive()โดย Alice และ Bob เกิน $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