Election
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- 출처
- 분류
문제
Given the voting preferences of a population of \(M\) people, you are to determine the winner of an election among \(N\) candidates, numbered \(1, \cdots ,N\). For this problem, the \(M\) people are partitioned into \(G\) “groups”where all members within a group have the same voting preferences. The candidate preferences for a group are specified by listing candidates from most preferred to least preferred. Election results are determined by an instant-runoff voting procedure.
In this method, the first choices of the M people in the population are counted and the least popular candidate is eliminated. In the event of a tie, the highest-numbered candidate is eliminated. Then, the eliminated candidate is removed from the preference list of all \(M\) individuals in the population, and again the least popular candidate is eliminated. This process repeats until only a single candidate is left.
입력
The input test file will contain multiple test cases. Each input test case begins with a single line containing the integers \(G\) and \(N\) where \(2 \le N \le 5\) and \(1 \le G \le 20\). The next \(G\) lines are of the format “\(M_i\;a_{i_1}\;a_{i_2}\; \cdots a_{i_N}\)” where \(1 \le Mi \le 20\) and \(a_{i_1}, \cdots , a_{i_N}\) is a permutation of the integers \(1, \cdots ,N\). \(M_i\) is the number of individuals in the \(i\)th group, and \(a_{i_1}, \cdots , a_{i_N}\) is the ordering of the \(N\) candidates from most preferred to
least preferred for the \(i\)th group. The end-of-file is marked by a test case with \(G = N = 0\) and should not be processed.
출력
For each input case, the program should print the winner of the election on a single line.
예제 입력
3 4 10 1 4 2 3 15 3 2 1 4 12 4 3 2 1 3 2 10 1 2 10 1 2 20 2 1 0 0
예제 출력
4 1
노트
