Universal Cup Judging System

Universal Cup

Time Limit: 0.5 s Memory Limit: 1024 MB Total points: 100 Communication
Statistics

זוהי בעיית תקשורת.

שתי תוכניות, 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): שליחת ערך של ביט אחד $x$ לתוכנית השנייה. קריאה זו אינה חוזרת עד שהתוכנית השנייה קוראת ל-receive().
  • receive(): קבלת ערך של ביט אחד מהתוכנית השנייה והחזרתו. קריאה זו אינה חוזרת עד שהתוכנית השנייה קוראת ל-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.