UVA-10142 - Australian Voting

  • UVa Online Judge 解題結果請於 Submit 後,參閱 uHunt
  • 如果你有任何建議與指教,歡迎於下方留言一起討論喔!
  • 本題選為「20171219 大學程式能力檢定 CPE」題目。

題意概要

本題要模擬澳洲的投票制度。簡單來說,假設有 位候選人和 位公民,每一位公民對每位候選人有一個期望的優先序,在選舉過程中,先按照第一優先序分配選票,而得票最少的候選人的的票數,將剔除該輪選舉,並將按照投票人的優先序,重新分给剩下的候選人,直到有候選人得票數超過全體的 % 選票,則該候選人獲選,或是剩下的候選人的得票數相同時,視為一起獲選。


Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. The first line of input is an integer indicating the number of candidates. The next lines consist of the names of the candidates in order. Names may be up to characters in length and may contain any printable characters. Up to lines follow; each contains the contents of a ballot. That is, each contains the numbers from to in some order. The first number indicates the candidate of first choice; the second number indicates candidate of second choice, and so on.


Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. The Output consists of either a single line containing the name of the winner or several lines containing the names of the candidates who tied.


Sample Input

1
3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

Sample Output

John Doe
profile-image
Yung-Sheng Lu
Hello, I'm Yung-Sheng Lu. I am a graduate student in Department of Computer Science at National Chiao Tung University, Taiwan. I am in the Networking and Sensing Systems (NSS) Lab at NCTU.
comments powered by Disqus