זוהי בעיית תקשורת.
שתי תוכניות, 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