이 문제는 통신(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