Elections
SRM 251 · 2005-07-12 · by Vedensky
SRM 251 · 2005-07-12 · by Vedensky · Brute Force
Problem Statement
Problem Statement
There are two candidates campaigning to be president of a country.
From newspaper polls, it is clear what percentages of people plan to vote for each candidate in each state.
Candidate 1 wants to campaign in one last state, and needs to figure out which state that should be.
You are given aString[] likelihoods, each element of which corresponds to a state. Each element consists of the characters '1' and '2', where '1' represents some number of votes for candidate 1, and '2' represents votes for candidate 2 (in each element every character represents the same number of votes). You are to return an int representing the 0-based index of the state where the lowest percentage of people are planning on voting for candidate 1 (lowest percentage of '1' characters in that element of the input). If there are multiple such states, return one with the lowest index in likelihoods.
You are given a
Constraints
- likelihoods will contain between 1 and 50 elements inclusive.
- Each element of likelihoods will contain between 1 and 50 characters inclusive, and each character will be '1' or '2'.
Examples
0)
{"1222","1122","1222"}
Returns: 0
In the first state only 25% of people prefer candidate 1, while in the second and third, 50% and 25% prefer him, respectively.
1)
{"1222111122","2222222111","11111222221222222222"}
Returns: 1
The percentages of people, prefering candidate 1 to candidate 2 are (in order): 50%, 30%, 30%
2)
{"111","112","121","122","211","212","221","222"}
Returns: 7
3)
{"1122","1221","1212","2112","2121","2211"}
Returns: 0
4)
{"1111111111111111111111","1111111111111111111111111111111"}
Returns: 0
Submissions are judged against all 68 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Elections with a public method int visit(vector<string> likelihoods) · 68 test cases · 2 s / 256 MB per case