가짜 동전

이것은 상호작용형 문제이다.

디아르타냥은 발렌타인데이에 콘스탄시아에게 다이아몬드 목걸이를 선물하려고 한다. 모아 둔 돈을 세어 보니 동전이 정확히 2a+1개 있었다. 동전은 대략 절반이 금화이고 나머지가 은화이다(금화 a개와 은화 a+1개, 또는 그 반대). 디아르타냥은 원래 동전 개수가 짝수였다고 확신한다. 누군가 동전을 하나 더 넣었으니 그 동전이 가짜이다.

진짜 금화와 진짜 은화는 무게가 같다. 가짜 금화는 진짜보다 가볍고, 가짜 은화는 진짜보다 무겁다.

디아르타냥에게는 양팔 저울이 있다. 동전 두 무더기를 왼쪽 접시와 오른쪽 접시에 올려 어느 쪽이 무거운지, 또는 무게가 같은지 알 수 있다. 저울은 t번만 쓸 수 있다. 가짜 동전을 찾아라.

출력 명령을 실행할 때마다 반드시 다음 작업을 수행해야 한다.

• Pascal: flush(output);
• C/C++: fflush(stdout);
• Java: System.out.flush();
• Python: sys.stdout.flush();

또한 출력하는 줄마다 끝에 줄바꿈을 넣어야 한다.