| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 | 512 MB | 261 | 94 | 82 | 34.599% |
준혁이는 번호가 1ドル$부터 $N$까지 쓰여 있는 금화 $N$개를 가지고 있다. 쓰여 있는 번호가 그 동전의 번호이다.
어느 날 준혁이는 자신이 가지고 있는 금화 중 하나가 가짜 금화라는 소식을 알았다. 진짜 금화들의 무게는 모두 같지만 가짜 금화는 진짜 금화보다 무게가 가볍다.
준혁이는 가짜 금화를 찾아내기 위해 양팔 저울을 빌렸다. 양팔 저울을 이용하면 두 금화 묶음의 무게를 비교할 수 있다. 금화 묶음은 서로 다른 금화를 여러 개 모아놓은 것이다. 금화 묶음의 크기는 0ドル$ 이상 $N$ 이하여야 한다.
알고리즘 공부를 하느라고 바쁜 준혁이는 양팔 저울을 최대 5ドル$회만 사용하려고 한다. 준혁이를 도와 양팔 저울을 적절히 활용하여 가짜 금화가 몇 번 금화인지 찾아내자.
첫째 줄에 동전의 수 $N$이 입력된다. $(1 ≤ N ≤ 128)$
$N$이 입력된 후로는 프로그램과 채점 시스템이 상호작용하며 실행된다.
프로그램은 채점 시스템에게 다음과 같은 질문을 최대 5ドル$회 할 수 있다.
? A 0 B 0: 첫번째 금화 묶음 A와 두번째 금화 묶음 B의 무게를 비교해 결과를 물어보는 질문이다. 금화 묶음을 출력할 때는 금화 묶음에 속한 금화들을 아무 순서로 공백으로 구분하여 출력하고 금화 묶음에 있는 동전을 모두 출력했음을 의미하는 0을 출력하면 된다. 금화의 번호는 1ドル$과 $N$ 사이 정수이고 하나의 금화 묶음에 같은 동전이 2개 있을 수 없고, 금화 하나가 두 묶음에 전부 포함될 수 없다.채점 시스템에 질문을 출력하면 채점 시스템의 답변이 입력된다.
<: 금화 묶음 A가 더 가볍다.>: 금화 묶음 B가 더 가볍다.=: 두 금화 묶음의 무게가 같다.정답을 알아냈을 때는 다음과 같이 출력한다.
! $x$: 가짜 금화의 번호가 $x$이다.이 출력 이후에는 프로그램을 종료한다. 더 자세한 입출력 형식은 예제를 참고하자.
모든 출력 이후에는 버퍼를 flush 해야 한다. 언어별 표준 출력 버퍼를 flush 하는 방법은 다음과 같다.
fflush(stdout)std::cout << std::flushSystem.out.flush()sys.stdout.flush()4 > < > >
? 1 2 0 3 4 0 ? 1 3 0 2 4 0 ? 2 4 0 1 3 0 ? 1 4 0 2 3 0 ! 3
예제에서 가짜 금화는 3번 금화이다.
첫 번째 질문은 금화 묶음 {1, 2}와 금화 묶음 {3, 4}를 비교한 결과를 묻는다. 가짜 금화가 3번 금화이므로 오른쪽 금화 묶음이 더 가볍다.
두 번째 질문은 금화 묶음 {1, 3}와 금화 묶음 {2, 4}를 비교한 결과를 묻는다. 왼쪽 금화 묶음이 더 가볍다.
세 번째 질문은 금화 묶음 {2, 4}와 금화 묶음 {1, 3}를 비교한 결과를 묻는다. 오른쪽 금화 묶음이 더 가볍다.
네 번째 질문은 금화 묶음 {1, 4}와 금화 묶음 {2, 3}를 비교한 결과를 묻는다. 왼쪽 금화 묶음이 더 가볍다.
예제에서는 질문을 4번 하였으며 4번째 질문 후에 금화 3이 가짜 금화인 것을 알아내었다.
채점 프로그램은 처음에 가짜 금화를 결정한 후 처음 정한 가짜 금화에 따라 답변한다. 즉 채점 프로그램은 실행 도중에 가짜 금화의 번호를 바꾸지 않는다.