Universal Cup Judging System

Universal Cup

実行時間制限: 0.5 s メモリ制限: 1024 MB 満点: 100 コミュニケーション
統計

นี่คือโจทย์ประเภทการสื่อสาร (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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.