問題
Pottery Palace에서는 예술가 Cody-Jamal의 값비싼 항아리들을 내건 복권을 진행하려 한다. 복권은 다음과 같이 진행된다:
- 100명이 복권에 참여한다. 각 참가자는 1부터 100 사이의 서로 다른 번호를 하나씩 가지며, 그 번호가 적힌 토큰 1개를 받는다.
- 테이블 위에는 비어 있는 점토 항아리 20개가 있고, 항아리에는 1부터 20까지 번호가 매겨져 있다. 항아리의 입구는 토큰이 들어갈 만큼은 크지만, 참가자가 안을 들여다보며 내용물을 확인할 수 없을 만큼은 작다.
- 복권의 i번째 날에는 토큰 번호가 i인 참가자가 항아리 하나를 골라 그 항아리에 자신의 토큰을 넣는다. 항아리들은 (라벨을 제외하면) 모두 동일하므로, 각 참가자는 20개 중 하나를 균등한 확률로 무작위로 선택하며, 다른 참가자들의 선택과는 독립적으로 선택한다.
- 100번째 날, 100번 참가자가 토큰을 넣은 뒤, 주최 측은 항아리를 흔들어 각 항아리 안에 토큰이 몇 개 들어 있는지 알아낸다. 다른 어떤 항아리보다도 토큰 수가 엄격히 더 적은 항아리가 정확히 하나 존재한다면, 그 항아리를 "당첨 항아리"라고 한다. 그러면 주최 측은 그 항아리 안의 토큰을 모두 쏟아내고, 쏟아낸 토큰들 중 하나에라도 자신의 번호가 적혀 있는 모든 참가자는 항아리 하나씩을 받는다! 최소 토큰 수를 가진 항아리가 여러 개라면 아무도 당첨되지 않는다.
당신은 이 복권의 보안을 시험하기 위해 고용되었고, 몇 번의 시험 운영(trial run)에 참가하게 된다. 회사는 언제나 당신에게 100번을 배정한다. 즉, 당신이 100번 참가자를 대신한다.
당신은 밤에 복권을 조작할 수 있는 몇 가지 방법을 찾아냈지만, 보안이 엄격해서 할 수 있는 일이 많지 않다! 구체적으로, 복권의 첫 99일 각각이 끝난 뒤(즉, 매일 밤), 당신은 다음 중 정확히 하나의 행동만 할 수 있다:
- (1부터 100까지, 포함)에서 원하는 참가자 번호로 토큰을 위조해 원하는 항아리에 추가로 넣는다. 당신은 매우 뛰어난 위조범이어서, 당첨 항아리가 존재한다면 그 안에 있는 위조 토큰은(아래에서 설명할 한 가지 예외를 제외하고) 해당 번호의 참가자가 당첨되는 결과를 만든다.
- 특수 카메라로 원하는 항아리 하나 안에 들어 있는 모든 토큰의 번호를 확인한다.
밤마다 다른 행동을 할 수도 있고, 미리 모든 행동을 정해 둘 필요 없이 상황에 따라 동적으로 선택할 수도 있다.
100번째 날에는 당신의 토큰을 원하는 항아리에 넣을 차례다. (반드시 균등 무작위로 고를 필요는 없다.) 그 날에는 다른 어떤 행동도 할 수 없다.
당신은 만약 당첨 항아리 안에 같은 참가자에 대한 토큰이 2개 이상 존재하면, 부정행위가 드러나서 아무도 당첨되지 않는다는 것을 알고 있다. 하지만 다른 항아리들에 같은 참가자의 토큰이 2개 이상 들어 있는 것은 상관없다. 주최 측은 그 토큰들을 보지 못하기 때문이다.
당신의 목표는 전체 테스트 케이스 중 최소 90%에서 당첨자가 되는 것이다.
入力
이 문제는 인터랙티브 문제이다. 프로그램은 입력/출력 규약을 정확히 따라야 한다.
입력의 첫 줄에는 테스트 케이스 수 T가 주어진다. 각 테스트 케이스의 시작에서 심판은 현재 날짜를 나타내는 정수 한 줄을 출력한다(1일부터 시작하여 i번째 날에는 i를 출력).
당신이 어떤 날에 P = 0을 출력해 꽃병 V를 검사하면, 심판은 한 줄을 출력한다. 첫 번째 정수는 꽃병 V의 토큰 개수 N이고, 이어서 N개의 정수가 비내림차순으로 주어진다(꽃병 V에 들어 있는 플레이어 번호).
1 ≤ i ≤ 99인 i번째 날에는 당신의 행동 전에 심판이 i번째 플레이어의 행동을 먼저 시뮬레이션한다.
잘못된 출력을 하면 심판은 -1을 출력하고 이후에는 아무 출력도 하지 않는다.
이 경우 프로그램은 즉시 종료해야 한다.
出力
각 날의 날짜를 읽은 뒤, V P 두 정수를 한 줄에 출력한다.
1 ≤ V ≤ 20, 0 ≤ P ≤ 100이다.
1 ≤ P ≤ 100이면 플레이어 P의 토큰을 꽃병 V에 넣는다(이 경우 심판의 추가 출력은 없다).
P = 0이면 꽃병 V를 검사한다(입력 형식 참고).
100번째 날에는 반드시 P = 100이어야 하며, 그 날에는 검사(P = 0)를 할 수 없다.
100번째 날의 출력을 보낸 뒤, 마지막 테스트 케이스가 아니면 다음 테스트 케이스의 입력을 계속 읽어야 한다. 심판은 각 케이스의 정답 여부를 알려주지 않으므로 중간에 종료하면 오답 처리된다.
ログインしないとコードを書けません。