समस्या
Instant runoff चुनाव में हर मतदाता सभी उम्मीदवारों को रैंक करता है। गिनती दौरों में होती है:
- हर मतपत्र उस उम्मीदवार के लिए एक वोट गिना जाता है जो उस पर सबसे ऊँची रैंक पर है और अभी भी दौड़ में है।
- अगर किसी उम्मीदवार के पास कुल मतपत्रों के आधे से ज़्यादा वोट हैं, तो वह जीत जाता है।
- नहीं तो, अगर बचे हुए सभी उम्मीदवारों के वोट बराबर हैं, तो वे सब बराबरी पर हैं और चुनाव ख़त्म हो जाता है।
- नहीं तो, सबसे कम वोट वाले हर बचे उम्मीदवार को बाहर कर दिया जाता है (अगर कई के वोट सबसे कम हैं तो सब एक साथ), और नया दौर शुरू होता है।
runoff_election(candidates, ballots) लिखिए।
इनपुट
candidates: उम्मीदवारों के नाम। उम्मीदवार i है candidates[i]।
ballots: हर मतदाता के लिए एक पंक्ति: उम्मीदवारों के नंबर (0 से शुरू), सबसे पसंदीदा से सबसे कम पसंदीदा तक। हर पंक्ति में हर उम्मीदवार ठीक एक बार आता है।
आउटपुट
विजेता के नाम वाली list लौटाइए, या अगर चुनाव बराबरी पर ख़त्म हो, तो बराबरी वाले सभी उम्मीदवारों के नाम उसी क्रम में जिसमें वे candidates में हैं। कोई मतपत्र न हो तो सभी उम्मीदवार बराबरी पर हैं।
सीमाएँ
1 ≤ candidates की लंबाई ≤ 9
0 ≤ मतपत्रों की संख्या ≤ 200
उदाहरण
इनपुट:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 2, 1],
[1, 2, 0],
[1, 0, 2],
[2, 0, 1]
]
अपेक्षित आउटपुट:
expected = ["Ana"]
इनपुट:
std::vector<std::string> candidates = {"Ana", "Bo", "Cy"};
std::vector<std::vector<long long>> ballots = {
{0, 1, 2},
{0, 2, 1},
{1, 2, 0},
{1, 0, 2},
{2, 0, 1}
};
अपेक्षित आउटपुट:
std::vector<std::string> expected = {"Ana"};
इनपुट:
string[] candidates = new string[] {"Ana", "Bo", "Cy"};
long[][] ballots = new long[][] {
new long[] {0, 1, 2},
new long[] {0, 2, 1},
new long[] {1, 2, 0},
new long[] {1, 0, 2},
new long[] {2, 0, 1}
};
अपेक्षित आउटपुट:
string[] expected = new string[] {"Ana"};
व्याख्या
पहला दौर: Ana 2, Bo 2, Cy 1; किसी के पास 2.5 से ज़्यादा नहीं, इसलिए Cy बाहर। Cy का मतपत्र Ana को जाता है, जो 5 में से 3 वोट से जीतती है: ["Ana"]।
इनपुट:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 1, 2],
[1, 2, 0],
[1, 2, 0],
[2, 1, 0],
[2, 1, 0]
]
अपेक्षित आउटपुट:
expected = ["Ana", "Bo", "Cy"]
इनपुट:
std::vector<std::string> candidates = {"Ana", "Bo", "Cy"};
std::vector<std::vector<long long>> ballots = {
{0, 1, 2},
{0, 1, 2},
{1, 2, 0},
{1, 2, 0},
{2, 1, 0},
{2, 1, 0}
};
अपेक्षित आउटपुट:
std::vector<std::string> expected = {"Ana", "Bo", "Cy"};
इनपुट:
string[] candidates = new string[] {"Ana", "Bo", "Cy"};
long[][] ballots = new long[][] {
new long[] {0, 1, 2},
new long[] {0, 1, 2},
new long[] {1, 2, 0},
new long[] {1, 2, 0},
new long[] {2, 1, 0},
new long[] {2, 1, 0}
};
अपेक्षित आउटपुट:
string[] expected = new string[] {"Ana", "Bo", "Cy"};
व्याख्या
हर उम्मीदवार के पास 6 में से 2 पहली पसंद के वोट हैं, इसलिए तीनों बराबरी पर हैं: ["Ana", "Bo", "Cy"]।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
कौन अभी दौड़ में है, इसकी true/false list रखिए और हर दौर में शुरू से दोबारा गिनिए।
संकेत 2
बहुमत का मतलब है वोट × 2, मतपत्रों की संख्या से ज़्यादा हो।
संकेत 3
सबसे कम वोट सिर्फ़ बचे उम्मीदवारों में ढूँढिए; अगर सभी बचे उम्मीदवारों के उतने ही वोट हैं, तो चुनाव बराबरी पर है।
अपेक्षित जटिलता
समय O(c^2 × b), अतिरिक्त स्थान O(c)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।