UVA-10142 - Australian Voting

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

題意概要

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

• 分析：本題為模擬題，只要按照題目說明投票歸規則做篩選即可。在篩選過程中，需要先找到最多票數 (max) 和最少票數 (min) 的候選人，其目的在沒有候選選後票數過半的時候會用到，倘若在所有的候選人中，只要有「票數過半者」則直接獲選。若未有人過半，則要檢查大家的票數是否都相同 (換句話說，就是 max == min ?)，若一樣的話，就視為平手，印出所有的候選人；若有不同的，則去掉票數最小的候選人，重新再計票。唯獨要注意的是，本題在存取票數的終止條件，是當遇到空行時，則輸入結束，建議使用 #include <sstream> 先將每一行得票數存入 string 型態的變數，再依間隔的空白，依序存給每個候選人。

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 $n \le 20$ indicating the number of candidates. The next $n$ lines consist of the names of the candidates in order. Names may be up to $80$ characters in length and may contain any printable characters. Up to $1,000$ lines follow; each contains the contents of a ballot. That is, each contains the numbers from $1$ to $n$ 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