An election has c candidates and v ballots. Each ballot lists one or more candidate names in order of preference, and it need not list every candidate. The first line gives c and v, and the second line gives the c candidate names separated by single spaces. Each of the next v lines gives one ballot. At first every candidate remains, and the following count is repeated round by round.
1. For each ballot, give one vote to the candidate written earliest on it among those who still remain. A ballot that lists no remaining candidate is exhausted and is not counted this round.
2. Print, on one line, "name:votes" for each remaining candidate in the order of the second line, separated by single spaces. A candidate with no votes is printed as "name:0".
3. If some candidate has more than half of the ballots counted this round (exactly half is not enough), or only one candidate remains, that candidate wins. Print the winner's name on the next line and stop.
4. Otherwise eliminate the one candidate with the fewest votes and go to the next round. If several candidates share the fewest votes, eliminate the one written last on the second line among them.
Input
1 ≤ c ≤ 20, 1 ≤ v ≤ 1000. Candidate names are 1 to 10 lowercase English letters or digits and are distinct. A ballot lists 1 to c distinct candidate names separated by single spaces
Output
One "name:votes" line per round, then the winner's name on the last line
Example 1 · stdin
4 9
kim lee park choi
kim lee
kim
lee park
lee kim
park lee
park
choi park
choi
kim park
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Each round you count votes in a map, separately count the ballots that are not exhausted, and ask whether a name is in the list of remaining candidates. The key to the vote map is putting every remaining candidate in at 0 first: Python {name: 0 for name in remaining}, JS/TS new Map(remaining.map(name => [name, 0])), Java put(name, 0) then merge(name, 1, Integer::sum), C# remaining.ToDictionary(name => name, name => 0), C++ std::mapvotes[name] = 0, Craykon votes[name] = 0; (Dict(), 사전()). C uses an array with one slot per candidate number, int votes[20] = {0}. Trap one: counting only received votes with Python Counter() leaves zero-vote candidates out of the map. votes[name] gives 0 for a missing name, so the line still looks right, but min(votes.values()) never sees the 0 and the wrong candidate is eliminated instead of the zero-vote one. List membership: Python in, JS/TS includes, Java contains, C# Contains, C++ std::find(...) != end(), Craykon Contains (있나). Trap two: the values of Java Map<String, Integer> are Integer boxes, so if fewest is an Integer too, votes.get(a) == fewest compares whether they are the same box. Boxes for -128 to 127 are shared, so it seems to work, but ties at 128 votes or more are missed. Unbox to int or use equals. Trap three: the base for a majority is the ballots counted this round, not all ballots, and exactly half is not a majority, so the test is 2 * votes > counted.
Pythonmain.py · 25 lines
import syslines = sys.stdin.read().split("\n")c, v = map(int, lines[0].split())remaining = lines[1].split() # 남은 후보, 처음 적힌 차례대로ballots = [lines[2 + i].split() for i in range(v)]while True: votes = {name: 0 for name in remaining} # 0표인 후보도 먼저 넣어 둔다 active = 0 # 남은 후보를 하나라도 적은 투표지 수 for ballot in ballots: for name in ballot: if name in remaining: # 이 투표지에서 가장 앞에 적힌 남은 후보 votes[name] += 1 active += 1 break print(" ".join(f"{name}:{votes[name]}" for name in remaining)) leader = max(remaining, key=lambda name: votes[name]) if 2 * votes[leader] > active or len(remaining) == 1: print(leader) break fewest = min(votes.values()) loser = [name for name in remaining if votes[name] == fewest][-1] # 동점이면 뒤에 적힌 후보 remaining.remove(loser)
JavaScriptmain.js · 29 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [c, v] = lines[0].trim().split(" ").map(Number);const remaining = lines[1].trim().split(" "); // 남은 후보, 처음 적힌 차례대로const ballots = lines.slice(2, 2 + v).map((line) => line.trim().split(" "));const out = [];while (true) { const votes = new Map(remaining.map((name) => [name, 0])); // 0표인 후보도 먼저 넣어 둔다 let active = 0; // 남은 후보를 하나라도 적은 투표지 수 for (const ballot of ballots) { const first = ballot.find((name) => remaining.includes(name)); // 가장 앞에 적힌 남은 후보 if (first !== undefined) { votes.set(first, votes.get(first) + 1); active++; } } out.push(remaining.map((name) => `${name}:${votes.get(name)}`).join(" ")); const count = (name) => votes.get(name); const best = Math.max(...remaining.map(count)); if (2 * best > active || remaining.length === 1) { out.push(remaining.find((name) => count(name) === best)); break; } const fewest = Math.min(...remaining.map(count)); const loser = remaining.filter((name) => count(name) === fewest).pop(); // 동점이면 뒤에 적힌 후보 remaining.splice(remaining.indexOf(loser), 1);}console.log(out.join("\n"));
TypeScriptmain.ts · 30 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [c, v] = lines[0].trim().split(" ").map(Number);const remaining: string[] = lines[1].trim().split(" "); // 남은 후보, 처음 적힌 차례대로const ballots: string[][] = lines.slice(2, 2 + v).map((line) => line.trim().split(" "));const out: string[] = [];while (true) { const votes = new Map<string, number>(remaining.map((name): [string, number] => [name, 0])); // 0표인 후보도 먼저 넣어 둔다 let active = 0; // 남은 후보를 하나라도 적은 투표지 수 for (const ballot of ballots) { const first = ballot.find((name) => remaining.includes(name)); // 가장 앞에 적힌 남은 후보 if (first !== undefined) { votes.set(first, (votes.get(first) ?? 0) + 1); active++; } } const count = (name: string): number => votes.get(name) ?? 0; out.push(remaining.map((name) => `${name}:${count(name)}`).join(" ")); const best = Math.max(...remaining.map(count)); if (2 * best > active || remaining.length === 1) { out.push(remaining.find((name) => count(name) === best) ?? ""); break; } const fewest = Math.min(...remaining.map(count)); const tied = remaining.filter((name) => count(name) === fewest); remaining.splice(remaining.indexOf(tied[tied.length - 1]), 1); // 동점이면 뒤에 적힌 후보}console.log(out.join("\n"));
JavaMain.java · 47 lines
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] first = br.readLine().trim().split(" "); int v = Integer.parseInt(first[1]); List<String> remaining = new ArrayList<>(Arrays.asList(br.readLine().trim().split(" "))); // 처음 적힌 차례대로 List<String[]> ballots = new ArrayList<>(); for (int i = 0; i < v; i++) ballots.add(br.readLine().trim().split(" ")); StringBuilder out = new StringBuilder(); while (true) { Map<String, Integer> votes = new HashMap<>(); for (String name : remaining) votes.put(name, 0); // 0표인 후보도 먼저 넣어 둔다 int active = 0; // 남은 후보를 하나라도 적은 투표지 수 for (String[] ballot : ballots) { for (String name : ballot) { if (remaining.contains(name)) { // 가장 앞에 적힌 남은 후보 votes.merge(name, 1, Integer::sum); active++; break; } } } StringJoiner line = new StringJoiner(" "); for (String name : remaining) line.add(name + ":" + votes.get(name)); out.append(line).append('\n'); // Integer 상자끼리 ==로 비교하지 않도록 int로 꺼내 둔다 int best = -1, fewest = Integer.MAX_VALUE; String leader = "", loser = ""; for (String name : remaining) { int n = votes.get(name); if (n > best) { best = n; leader = name; } if (n <= fewest) { fewest = n; loser = name; } // <=: 동점이면 뒤에 적힌 후보 } if (2 * best > active || remaining.size() == 1) { out.append(leader).append('\n'); break; } remaining.remove(loser); } System.out.print(out); }}
C#Main.cs · 42 lines
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ static void Main() { int v = int.Parse(Console.ReadLine().Trim().Split(' ')[1]); var remaining = Console.ReadLine().Trim().Split(' ').ToList(); // 처음 적힌 차례대로 var ballots = new List<string[]>(); for (int i = 0; i < v; i++) ballots.Add(Console.ReadLine().Trim().Split(' ')); var sb = new StringBuilder(); while (true) { var votes = remaining.ToDictionary(name => name, name => 0); // 0표인 후보도 먼저 넣어 둔다 int active = 0; // 남은 후보를 하나라도 적은 투표지 수 foreach (string[] ballot in ballots) { string first = ballot.FirstOrDefault(name => remaining.Contains(name)); // 가장 앞에 적힌 남은 후보 if (first != null) { votes[first]++; active++; } } sb.Append(string.Join(" ", remaining.Select(name => $"{name}:{votes[name]}"))).Append('\n'); int best = remaining.Max(name => votes[name]); if (2 * best > active || remaining.Count == 1) { sb.Append(remaining.First(name => votes[name] == best)).Append('\n'); break; } int fewest = remaining.Min(name => votes[name]); remaining.Remove(remaining.Last(name => votes[name] == fewest)); // 동점이면 뒤에 적힌 후보 } Console.Write(sb); }}
C++main.cpp · 52 lines
#include <algorithm>#include <iostream>#include <map>#include <sstream>#include <string>#include <vector>int main() { int c, v; std::cin >> c >> v; std::vector<std::string> remaining(c); // 남은 후보, 처음 적힌 차례대로 for (auto& name : remaining) std::cin >> name; std::string line; std::getline(std::cin, line); // 후보 줄의 끝 std::vector<std::vector<std::string>> ballots(v); for (auto& ballot : ballots) { std::getline(std::cin, line); std::istringstream in(line); for (std::string name; in >> name;) ballot.push_back(name); } auto is_left = [&](const std::string& name) { return std::find(remaining.begin(), remaining.end(), name) != remaining.end(); }; while (true) { std::map<std::string, int> votes; for (const auto& name : remaining) votes[name] = 0; // 0표인 후보도 먼저 넣어 둔다 int active = 0; // 남은 후보를 하나라도 적은 투표지 수 for (const auto& ballot : ballots) { auto first = std::find_if(ballot.begin(), ballot.end(), is_left); // 가장 앞에 적힌 남은 후보 if (first != ballot.end()) { votes[*first]++; active++; } } for (size_t i = 0; i < remaining.size(); i++) std::cout << (i ? " " : "") << remaining[i] << ":" << votes[remaining[i]]; std::cout << "\n"; int best = -1, fewest = v + 1; std::string leader, loser; for (const auto& name : remaining) { if (votes[name] > best) { best = votes[name]; leader = name; } if (votes[name] <= fewest) { fewest = votes[name]; loser = name; } // <=: 동점이면 뒤에 적힌 후보 } if (2 * best > active || remaining.size() == 1) { std::cout << leader << "\n"; break; } remaining.erase(std::find(remaining.begin(), remaining.end(), loser)); }}
Cmain.c · 63 lines
#include <stdio.h>#include <string.h>#define MAXC 20#define MAXV 1000static char cand[MAXC][11]; /* 후보 이름, 처음 적힌 차례 */static int left[MAXC]; /* 1이면 아직 남은 후보 */static int ballot[MAXV][MAXC]; /* 투표지마다 후보 번호 */static int len[MAXV];static int cand_id(const char *name, int c) { for (int i = 0; i < c; i++) if (strcmp(cand[i], name) == 0) return i; return -1;}int main(void) { int c, v; scanf("%d %d", &c, &v); for (int i = 0; i < c; i++) { scanf("%10s", cand[i]); left[i] = 1; } getchar(); /* 후보 줄의 끝 */ char line[256]; for (int b = 0; b < v; b++) { fgets(line, sizeof line, stdin); len[b] = 0; for (char *tok = strtok(line, " \r\n"); tok; tok = strtok(NULL, " \r\n")) ballot[b][len[b]++] = cand_id(tok, c); } int count_left = c; while (1) { int votes[MAXC] = {0}; /* 후보 번호마다 표 수 */ int active = 0; /* 남은 후보를 하나라도 적은 투표지 수 */ for (int b = 0; b < v; b++) { for (int k = 0; k < len[b]; k++) { if (left[ballot[b][k]]) { /* 가장 앞에 적힌 남은 후보 */ votes[ballot[b][k]]++; active++; break; } } } int best = -1, fewest = v + 1, leader = -1, loser = -1, printed = 0; for (int i = 0; i < c; i++) { if (!left[i]) continue; printf("%s%s:%d", printed++ ? " " : "", cand[i], votes[i]); if (votes[i] > best) { best = votes[i]; leader = i; } if (votes[i] <= fewest) { fewest = votes[i]; loser = i; } /* <=: 동점이면 뒤에 적힌 후보 */ } putchar('\n'); if (2 * best > active || count_left == 1) { printf("%s\n", cand[leader]); break; } left[loser] = 0; count_left--; } return 0;}
Craykonmain.cray · 62 lines
first = Console.ReadLine().Trim().Split();v = first[1].ToNumber();remaining = Console.ReadLine().Trim().Split(); // 남은 후보, 처음 적힌 차례대로ballots = [];for (i = 0; i < v; i++){ ballots.Add(Console.ReadLine().Trim().Split());}끝남 = false;while (!끝남){ votes = Dict(); foreach (name in remaining) { votes[name] = 0; // 0표인 후보도 먼저 넣어 둔다 } active = 0; // 남은 후보를 하나라도 적은 투표지 수 foreach (ballot in ballots) { foreach (name in ballot) { if (remaining.Contains(name)) { votes[name] = votes[name] + 1; active++; break; } } } parts = []; best = -1; fewest = v + 1; leader = ""; loser = ""; foreach (name in remaining) { parts.Add(name + ":" + votes[name]); if (votes[name] > best) { best = votes[name]; leader = name; } if (votes[name] <= fewest) { fewest = votes[name]; loser = name; } } Console.WriteLine(parts.Join(" ")); if (2 * best > active || remaining.Count == 1) { Console.WriteLine(leader); 끝남 = true; } else { remaining.Remove(loser); }}