눈치게임
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- 출처
- 분류
문제
ICU Programming Club RUN은 ICPC 시즌을 맞아, 대전 근교 장태산으로 엠티를 갔다. 밤이 되고 함께 술을 마시며 놀다가, 그들은 눈치 게임을 시작했다. 눈치게임은 다음과 같은 방식으로 진행한다.
N명의 사람이 있다. 편의상 각 사람을 1...N 번 사람이라고 부른다.
이들은 서로 눈치를 보며 1부터 K까지 순서대로 숫자를 외친다. K는 N보다 작다
두 사람 이상이 동시에 같은 숫자를 외치면 그 사람들은 게임에 지게 된다.
한 번 숫자를 외친 사람은 더 이상 다른 숫자를 외치지 않는다.
K 까지 숫자를 외치는 동안 패자가 없으면, 숫자를 외치지 못한 나머지 사람들이 지게 된다.게임이 시작하면 1을 외칠 수 있고, 누군가 j를 외치면 그 순간부터 j+1을 외칠 수 있다. i번 사람은 숫자 j를 외칠 수 있는 순간부터 W(i,j) 시간만큼 기다리며 눈치를 본다. 그리고 그 시간동안 아무도 숫자를 외치지 않으면 j를 외친다.
N명이 각각 숫자에 대해서 기다리는 시간이 주어졌을 때 눈치게임에서 지는 사람은 누구인가?
입력
첫 줄에는 게임의 회수 T가 주어진다. (1 ≤ T ≤ 100 )
각 테스트 케이스의 첫 줄에는 정수 N과 K가 주어진다. (1 ≤ K < N ≤ 500)
다음 줄부터 N 줄에 걸쳐서 N x K 의 행렬이 주어진다.
i행의 j열에 있는 수는 W(i,j)를 나타낸다. (0 ≤ W(i,j) ≤ 60, 1 ≤ i ≤ N, 1 ≤ j ≤ K)
출력
각각의 게임에 대하여 지는 사람의 목록을 오름차순으로 한 줄에 출력한다.
각 사람은 한 칸의 공백으로 구분하도록 한다.
예제 입력
3 4 3 0 1 3 7 0 1 5 1 3 1 2 3 3 2 1 1 1 2 1 3 5 3 0 1 2 2 0 1 1 2 0 1 2 3 1 1 1
예제 출력
3 4 1 2 3 4 5
노트
입력 개수가 매우 많으니, 빠른 입출력 함수를 사용하세요.
