هذه مسألة تواصل (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): إرسال قيمة مكونة من بت واحد $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$ مللي ثانية و $5$ ميغابايت.
- ستتعامل مع أعداد صحيحة في النطاق من $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