34159번 - 감그레이 점수인터랙티브

문제

勘ぐれい(감그레이): '의심하여 억측하다' 라는 뜻의 '勘ぐる' 와 회색(グレー)의 합성어

감그레이 왕국에는 세 종류의 사람이 있다. 흰색 옷을 입는 사람은 진실만을 말하고, 회색 옷을 입는 사람은 진실 혹은 거짓을 말하며, 검은색 옷을 입는 사람은 거짓만을 말한다. 감그레이 왕국의 왕은 참된 사람을 좋아하기에 항상 진실만을 말하는 흰 옷을 입은 사람만을 고용하고 싶어한다. 그러나 면접장에 모인 지원자들은 모두 검은색 정장을 입고 있어 왕은 누가 어떠한 색의 옷을 입고 있는지 전혀 알 수 없다. 다행히도 모든 지원자들은 서로 무슨 옷을 입고 있는지 알고 있기에, 왕은 이 난처한 상황을 질문을 통해 해결하고자 한다. 왕은 각 지원자 $i$에게 다음과 같은 질문을 정확히 한 번 한다.

• $j$번째 지원자는 흰색/회색/검은색 옷을 입은 사람인가?

왕은 모든 지원자에게 위와 같은 질문을 한 뒤, 흰 옷이 아니라고 판단되는 한 사람을 탈락시킬 수 있다. 탈락자는 더 이상 정장을 입을 필요가 없으므로 옷을 벗고 나가게 되는데, 이때 왕은 그 사람이 실제로 무슨 색 옷을 입었는지 확인할 수 있다. 왕은 탈락자에게는 질문을 할 수 없고, 질문의 대상으로 탈락자를 정할 수 없다. 만약 남아 있는 지원자들이 전부 흰 옷을 입었다고 판단되면 왕은 과정을 멈춘다. 왕의 목표는 흰 옷을 입은 사람만을 남기되, 남은 흰 옷을 입은 사람의 수가 최대이도록 하는 것이다. 왕이 모든 지원자에게 질문하고 응답을 취합해 한 사람을 탈락시키거나 종료하는 절차를 반복할 수 있도록 프로그램을 작성하자.

인터랙션

당신이 작성한 프로그램은 채점 프로그램과 아래와 같이 상호작용해야 한다.

먼저 당신의 프로그램은 면접을 보러 온 지원자의 수 $N$을 입력받는다. $(2 \leq N \leq 500)$

이후에는 매 단계마다 모든 지원자들에게 질의를 전송하고 응답을 수집한 뒤, 탈락 대상을 결정하는 동일한 절차를 반복한다.

질문을 하기 위해서는 $N$개의 줄에 걸쳐 $i$번째 줄에 지원자 $i$에게 물어볼 질문을 $?,円j,円a$ 형식으로 출력해야 한다. $(1 \leq i \leq N)$ 여기서 $j$는 지원자 $i$에게 질문할 지원자의 번호를, $a$는 질문의 종류를 의미한다. $a$가 1ドル$이면 흰색 옷, 2ドル$이면 회색 옷, 3ドル$이면 검은색 옷을 입고 있는지 질문한다. 이미 탈락한 지원자에 대해서는 질문할 수 없다. 만약 지원자 $i$가 이미 탈락했다면, $i$번째 줄에는 질문하지 않고 $?,0円,0円$을 출력해야 한다.

당신이 질문을 전송하면, 채점 프로그램은 모든 지원자에 대한 응답을 나타내는 $N$개의 정수를 질문한 순서대로 한 줄에 공백으로 구분해 반환한다. 각 질문의 응답으로 입력받은 정수가 1ドル$이면 질문에 '네', 2ドル$이면 질문에 '아니오'라고 응답한 것을 의미한다. 이미 탈락한 지원자에 대해서는 0ドル$을 반환한다.

질문을 전송한 뒤 응답을 수집하여 탈락 대상을 결정한다.

• 탈락 대상이 없는 경우(즉 남아 있는 지원자가 모두 흰 옷을 입었다고 판단해 과정을 멈추려는 경우)에는 아무도 탈락시키지 않고, 즉시 $!,0円$을 출력한 뒤 프로그램을 종료한다.
• 탈락 대상이 있는 경우에는 탈락시킬 지원자 $k$ $(1 \leq k \leq N)$를 선택하고 탈락 처리하기 위해 $!,円k$를 출력한다. 채점 프로그램은 $k$가 입은 옷의 색깔 $c$를 반환한다. $c$가 1ドル$이라면 흰색, 2ドル$라면 회색, 3ドル$이라면 검은색 옷임을 의미한다. $k$번 지원자가 탈락한 이후 남은 지원자가 0명이면 옷의 색 $c$를 입력 받은 이후 $!,0円$을 한 줄에 출력한 뒤 프로그램을 종료한다. 그렇지 않을 경우 위 과정을 반복한다.

질문의 순서를 지키지 않거나 탈락한 지원자와 관련된 정보를 묻거나 출력할 시 인터랙터가 $-1$을 반환한다. 이 경우 즉시 프로그램을 종료해야 된다.

점수

흰 옷을 입은 지원자만을 올바르게 남겼다면 다음과 같이 점수를 받을 수 있다.

• 마지막에 남은 흰 옷을 입은 지원자 수가 초기 흰 옷 지원자 수와 5ドル$명 이하만큼 차이가 날 경우 50ドル$점을 받는다.
• 마지막에 남은 흰 옷을 입은 지원자 수가 초기 흰 옷 지원자 수와 1ドル$명 이하만큼 차이가 날 경우 100ドル$점을 받는다.

입력

출력

제한

노트

각 줄을 출력한 뒤에는 표준 출력 버퍼를 flush해 주어야 한다. 언어별로 표준 출력 버퍼를 flush하는 방법은 다음과 같다.

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