34219번 - 진짜 금화 찾기 인터랙티브

문제

준혁이는 번호가 1ドル$부터 $N$까지 쓰여 있는 금화 주머니 $N$개를 가지고 있다. $i$번째 금화 주머니에는 번호가 $i$인 금화가 5ドル$개씩 들어 있다.

어느 날 준혁이는 자신이 가지고 있는 금화 중 $x$번째 주머니에 들어있는 $x$번 금화 5ドル$개를 제외한 다른 모든 금화들이 가짜 금화라는 소식을 알았다. 진짜 금화의 무게는 10ドル$이지만, 가짜 금화는 무게가 9ドル$이다.

준혁이는 진짜 금화를 찾아내기 위해 전자 저울을 빌렸다. 전자 저울을 이용하면 올려놓은 모든 금화의 무게 합을 알 수 있다.

알고리즘 공부를 하느라고 바쁜 준혁이는 전자 저울을 최대 3ドル$회만 사용하려고 한다. 준혁이를 도와 전자 저울을 적절히 활용하여 진짜 금화가 몇 번 금화인지 찾아내자.

입력

첫째 줄에 금화 주머니의 수 $N$이 주어진다. $(1 \leq N \leq 200)$

이후 채점 시스템과 프로그램이 상호작용하며 실행된다.

출력

제한

인터랙션

당신은 표준 출력에 다음 연산을 각 줄에 출력하는 것으로, 채점 시스템과 인터랙션할 수 있다. 각 토큰은 공백으로 구분하며, 각 연산의 끝에 개행문자를 출력하여야 한다.

당신은 채점 시스템에게 다음과 같은 연산을 최대 3ドル$회 할 수 있다.

• ? $a_1\ a_2\ \ldots\ a_N$: $i$번 금화를 $a_i$개씩 전자 저울에 올려놓은 후 올려놓은 금화의 무게의 합을 묻는다.
  • 전자 저울에 올려놓은 금화 무게의 합이 다음 줄에 입력된다.
  • 전자 저울에 올려놓은 금화는 무게를 측정 한 이후 다시 돌려받을 수 있다.
  • 0ドル \leq a_i \leq 5$

만약 정답을 알아냈다면 다음 연산을 통해 답을 제출할 수 있다.

• ! $x$: 진짜 금화의 번호가 $x$임을 제출한다.
  • 해당 출력 이후에는 프로그램을 종료하여야 한다.
  • 이 연산은 연산 제한에 포함되지 않는다.

만약 연산이 잘못된 출력이거나 제한을 초과하였다면 당신은 -1을 다음 줄에 입력받으며 이 입력이 주어질 경우 프로그램을 즉시 종료해야 한다.

채점 시스템은 적응적이지 않다. 즉 처음에 진짜 금화의 번호는 정해져 있으며 상호작용 도중에 진짜 금화의 번호를 바꾸지 않는다.

각 연산 이후에는 표준 출력 버퍼를 비워야 한다.

각 언어별로 표준 출력 버퍼를 비우는 방법은 다음과 같다. 기타 언어의 경우, 언어의 레퍼런스 페이지를 참조하여라.

• C: fflush(stdout)
• C++: std::cout << std::flush
• Java, Kotlin: System.out.flush()
• Python: sys.stdout.flush()

힌트