Problems
호주 선거 방식에서 투표하는 사람은 모든 후보들을 선호에 따라 나열해야 한다. 당선자를 선정하는 방법은 다음과 같다. 먼저 모든 투표용지에서 1위를 차지한 이름들의 수를 센다. 만약 어떤 한 후보가 과반수 초과, 즉 50%보다 많은 투표용지에서 1위를 차지하면 그 사람이 당선자가 된다. 만약 그런 사람이 없다면 득표수가 가장 적은 사람(들)을 지운다. 만약 지워진 사람이 어떤 용지에서 1위로 적혀있다면 그 이름을 지우고 다음이름을 그 투표지의 1위로 삼는 것이다. 이렇게 모두 제거한 후에 다시 같은 방법으로 과반수 초과 후보가 있는지 다시 확인하는 작업을 한다. 또 다시 득표수가 적은 사람들을 지운다. 이렇게 과반수이상의 득표자가 나오거나 모든 후보가 지워질 때까지 반복하여 당선자를 뽑는 방식이다.
당선자가 있다면 당선자를 찾고 만약 모든 후보가 지워진 경우라면 마지막으로 지워진 후보들의 이름을 출력한다.
Input
후보들의 수를 의미하는 n≤20 이 먼저 입력되며 다음 n줄에 걸쳐 후보들의 이름이 주어진다. 후보의 이름은 80 글자 이내이다. 다음 행에 투표지의 개수 t가 입력된다. 다음 줄부터는 투표지의 정보가 입력된다. 투표지는 1,000 장 이하이다. 투표지 마다 투표지에 적힌 순서가 정수로 n개씩 입력된다.
Output
당선자가 있을 경우 당선자 이름을 당선자가 없다면 타이를 이룬 후보들의 이름을 한 줄에 한 명씩 입력된 순서대로 출력한다.
Example #1
3
John Doe
Jane Smith
Sirhan Sirhan
5
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2
John Doe
Example #2
3
Tourist
Gennady Korotkevich
Henatzi Karatkevich
3
1 2 3
2 3 1
3 1 2
Tourist
Gennady Korotkevich
Henatzi Karatkevich
Hint
Source
Waterloo's local Programming Contests - 17 October, 1998 D번
You must sign in to write code.