Universal Cup Judging System

Universal Cup

시간 제한: 0.5 s 메모리 제한: 1024 MB 총점: 100 커뮤니케이션
통계

이 문제는 통신(communication) 문제입니다.

두 프로그램 Alice와 Bob이 다음과 같은 협동 게임을 합니다.

$0 \le A, B < 2^{64}$를 만족하는 정수 $A$와 $B$가 주어집니다. 처음에는 Alice만 $A$를 알고 있고, Bob만 $B$를 알고 있습니다. $C := \min(A, B)$라고 합시다. 목표는 Alice와 Bob이 모두 $C$를 출력할 수 있게 하는 것입니다.

정보를 교환하기 위해 Alice와 Bob은 다음 함수들을 호출할 수 있습니다:

  • send(x): 상대 프로그램에게 1비트 값 $x$를 보냅니다. 이 호출은 상대 프로그램이 receive()를 호출할 때까지 반환되지 않습니다.
  • receive(): 상대 프로그램으로부터 1비트 값을 받아서 반환합니다. 이 호출은 상대 프로그램이 send()를 호출할 때까지 반환되지 않습니다.

Alice와 Bob이 호출한 send()의 총횟수의 합은 $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()를 호출하는 경우,
  • Alice와 Bob이 호출한 send()의 총횟수가 $76$을 초과하는 경우.

receive

receive()를 호출하려면 다음과 같이 출력합니다:

receive

그다음 전달받은 비트 $x$를 표준 입력으로부터 읽습니다:

x

이 호출은 상대 프로그램이 send()를 호출할 때까지 반환되지 않습니다. 다음 중 하나라도 발생하면 Wrong Answer를 받게 됩니다:

  • 대기하는 동안 상대 프로그램이 종료되는 경우,
  • 대기하는 동안 상대 프로그램도 receive()를 호출하는 경우,
  • Alice와 Bob이 호출한 receive()의 총횟수가 $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$ 범위의 정수를 다루게 됩니다. 오버플로에 주의하세요.

예제

예제 입력 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.