이 문제는 인터랙티브 문제이다.
길이가 인 숨겨진 수열 가 있다. 각 원소는 , , 중 하나이며, 세 값은 각각 한 번 이상 등장한다.
공격자는 최대 번 서로 다른 두 위치 를 골라 와 의 대소 관계를 물을 수 있다. 수비자는 작음, 같음, 큼 중 하나로 답한다. 수비자는 수열을 미리 정하지 않고 이전 질의에 따라 적응적으로 답해도 된다. 단, 지금까지의 모든 답변과 일치하는 유효한 수열이 항상 하나 이상 존재해야 한다.
공격자가 비교 결과만으로 수열을 유일하게 확정하면 공격자의 승리이다. 최대 번의 비교 후에도 가능한 수열이 둘 이상이면 수비자의 승리이다. 단순히 수열을 추측하는 것은 공격자의 승리로 인정하지 않는다.
을 보고 반드시 이길 수 있는 역할을 선택한 뒤, 그 역할의 전략을 수행하여라. 상대는 채점 프로그램이 맡는다. 전략은 상대의 모든 유효한 행동에 대해 승리를 보장해야 한다.
수비자로 플레이할 때는 종료 시 모든 답변과 일치하는 서로 다른 유효한 수열 두 개를 제출해야 한다.
처음에 정수 이 다음 형식으로 주어진다.
하나의 실행에서 하나의 게임만 진행한다. 이후 입력은 선택한 역할에 따라 주어지며, 아래 통신 규약을 따른다.
역할 선택
첫 줄에 공격자라면 A, 수비자라면 D를 출력한다. 상대의 유효한 모든 행동에 대해 승리를 보장할 수 없는 역할을 선택하면 오답이다.
공격자 비교하려면 다음 형식으로 출력한다.
?
, 여야 한다. 채점 프로그램은 이면 , 같으면 , 크면 을 돌려준다. 같은 위치 쌍을 여러 번 물어도 되지만 매번 비교 횟수에 포함된다. 질의는 최대 번 할 수 있다.
공격자를 선택한 통신 예시이다. 비교 결과로 수열은 로 확정된다. 예제 입력은 채점 프로그램이 보내는 메시지를, 예제 출력은 참가자가 보내는 메시지를 순서대로 모은 것이다. 실제 통신에서는 서로 번갈아 메시지를 주고받는다.
수비자를 선택한 통신 예시이다. 두 증거 수열 , 은 모두 첫 번째 원소가 두 번째보다 작고, 두 번째가 세 번째보다 크다. 실제 질의 순서는 예시와 다를 수 있다.
-101수열이 유일하게 확정되었다면 다음 형식으로 출력하고 즉시 종료한다.
!
출력한 수열은 지금까지의 답변과 일치하는 유일한 유효한 수열이어야 한다. 다른 가능한 수열이 남아 있으면 오답이다.
수비자 채점 프로그램은 최대 번 다음 형식의 질의를 보낸다.
?
각 질의에 대해 , , 를 뜻하는 -1, 0, 1 중 하나를 출력한다. 답변들은 하나 이상의 유효한 수열과 일치해야 한다.
채점 프로그램이 ! 한 개를 보내면 질의가 종료된다. 채점 프로그램은 번보다 적게 질의하고 종료할 수도 있다. 다음 형식으로 서로 다른 수열 를 출력한 뒤 즉시 종료한다.
!
두 수열은 각각 길이가 이며, 원소는 , , 이고 각 값이 한 번 이상 등장해야 한다. 적어도 한 위치에서 여야 하며, 두 수열 모두 이전의 모든 답변과 일치해야 한다.
모든 출력 뒤에는 반드시 버퍼를 flush해야 한다. 비교 제한 초과, 잘못된 위치나 토큰, 모순된 답변, 잘못된 최종 출력은 오답 처리될 수 있다. flush하지 않거나 입력 없이 대기하면 시간 초과가 발생할 수 있다. 입력이 종료되면 즉시 프로그램을 종료한다. 최종 출력 후에는 추가 입력을 기다리지 않는다. 토큰 사이의 연속된 공백과 마지막 줄바꿈 유무는 채점에 영향을 주지 않는다.