Universal Cup Judging System

Universal Cup

حد الوقت: 0.5 s حد الذاكرة: 1024 MB مجموع النقاط: 100 تواصل
الإحصائيات

Dies ist ein Kommunikationsproblem.

Zwei Programme, Alice und Bob, spielen das folgende kooperative Spiel.

Gegeben sind ganze Zahlen $A$ und $B$ mit $0 \le A, B < 2^{64}$. Zu Beginn kennt nur Alice den Wert $A$, und nur Bob kennt den Wert $B$. Sei $C := \min(A, B)$. Das Ziel ist es, dass sowohl Alice als auch Bob den Wert $C$ ausgeben können.

Um Informationen auszutauschen, dürfen Alice und Bob die folgenden Funktionen aufrufen:

  • send(x): Sende einen 1-Bit-Wert $x$ an das andere Programm. Dieser Aufruf kehrt erst zurück, wenn das andere Programm receive() aufruft.
  • receive(): Empfange einen 1-Bit-Wert vom anderen Programm und gib ihn zurück. Dieser Aufruf kehrt erst zurück, wenn das andere Programm send() aufruft.

Die Gesamtzahl der Aufrufe von send() durch Alice und Bob zusammen darf $76$ nicht überschreiten. Dasselbe gilt für receive().

Nachdem die Kommunikation beendet ist, muss jedes Programm genau einmal die folgende Funktion aufrufen:

  • answer(x): Erkläre, dass der Wert von $C$ gleich $x$ ist. Unmittelbar nach dem Aufruf dieser Funktion muss sich das Programm beenden.

Das Spiel ist erfolgreich, wenn sowohl Alice als auch Bob den Wert $C$ korrekt angeben.

Schreibe zwei Programme, Alice und Bob, die in dem Spiel immer erfolgreich sind.

Interaktionsprotokoll

Dies ist ein interaktives Kommunikationsproblem (deine Programme und der Judge kommunizieren über die Standardein- und -ausgabe). Dein Programm in der Rolle von Alice und dein Programm in der Rolle von Bob spielen das Spiel über den Judge.

Programmstart

Dein Programm erhält zuerst eine Eingabe im folgenden Format:

Player
X

Hierbei ist Player die Zeichenkette Alice oder Bob, und $X$ ist eine ganze Zahl mit $0 \le X < 2^{64}$.

  • Wenn Player gleich Alice ist, gilt $A = X$. Von diesem Zeitpunkt an muss sich dein Programm wie Alice verhalten.
  • Wenn Player gleich Bob ist, gilt $B = X$. Von diesem Zeitpunkt an muss sich dein Programm wie Bob verhalten.

Rufe danach wie unten beschrieben send, receive und schließlich answer auf.

send

Um send(x) aufzurufen, gib Folgendes aus:

send x

Hierbei muss $x$ gleich $0$ oder $1$ sein.

Dieser Aufruf kehrt erst zurück, wenn das andere Programm receive() aufruft. Du erhältst das Urteil Wrong Answer, wenn eines der folgenden Ereignisse eintritt:

  • das andere Programm beendet sich, während du wartest,
  • das andere Programm ruft ebenfalls send() auf, während du wartest,
  • die Gesamtzahl der Aufrufe von send() durch Alice und Bob überschreitet $76$.

receive

Um receive() aufzurufen, gib Folgendes aus:

receive

Lies anschließend das empfangene Bit $x$ von der Standardeingabe ein:

x

Dieser Aufruf kehrt erst zurück, wenn das andere Programm send() aufruft. Du erhältst das Urteil Wrong Answer, wenn eines der folgenden Ereignisse eintritt:

  • das andere Programm beendet sich, während du wartest,
  • das andere Programm ruft ebenfalls receive() auf, während du wartest,
  • die Gesamtzahl der Aufrufe von receive() durch Alice und Bob überschreitet $76$.

Falls dein Programm während der Interaktion als Wrong Answer gewertet wird, wird als Eingabe $-1$ bereitgestellt. Wenn du $-1$ einliest, beende dein Programm sofort, da du sonst Time Limit Exceeded erhalten kannst.

answer

Um answer(x) aufzurufen, gib Folgendes aus:

answer x

Hierbei muss $x$ gleich $\min(A, B)$ sein. Beende dein Programm unmittelbar nach dem Aufruf dieser Funktion.

Hinweis

  • Nach jeder Ausgabe muss dein Programm die Standardausgabe leeren (flushen); andernfalls kannst du Time Limit Exceeded erhalten.
  • Das Judge-Programm, dein Programm als Alice und dein Programm als Bob laufen gleichzeitig. Zeit- und Speicherlimit werden als Summe aller drei Prozesse gemessen, lasse also sowohl bei der Laufzeit als auch beim Speicherverbrauch genügend Spielraum.
    • Das Judge-Programm verbraucht bis zu etwa $50$ ms und $5$ MiB.
  • Du arbeitest mit ganzen Zahlen im Bereich von $0$ bis $2^{64} - 1$. Achte auf Überläufe (Overflow).

Beispiele

Beispieleingabe 1

Alice
31
1

Beispielausgabe 1

send 0
receive
send 1
answer 25

Beispieleingabe 2

Bob
25
0
1

Beispielausgabe 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.