TopFive
SRM 243 · 2005-05-17 · by Olexiy
SRM 243 · 2005-05-17 · by Olexiy · Advanced Math, Brute Force, Simulation
Problem Statement
Problem Statement
You regularly participate in problem solving contests. During a contest all contestants must solve 3 problems, submitting their solutions to the judges for some points. After the competition, the judges will check the correctness of the problems, and award 0 points for incorrect problems.
You want to know your result as soon as possible and you hate waiting for the judges to finish their work. You are ambitious and you are only interested in knowing if you will finish among the top 5 people. Thus you decide to write your own program to determine your probability of getting a top 5 spot. Notice that if someone gets the same score as you, they will go above you on the top scorers list.
You will be given twoString[] s - results, giving you the points all people have scored for their problems (prior to being judged), and accuracies, the submission accuracies for all people (the ith element of results corresponds to the ith element of accuracies). Each element of results and accuracies will contain three space-delimited integers without extra leading zeroes. For the ith contestant the corresponding element of results contains the points this contestant received for his three solutions, and the corresponding element of accuracies represents the probabilities in percents of these solutions to be correct.
Given the points you have (you think all your solutions are correct), return the probability you will make the top 5.
You want to know your result as soon as possible and you hate waiting for the judges to finish their work. You are ambitious and you are only interested in knowing if you will finish among the top 5 people. Thus you decide to write your own program to determine your probability of getting a top 5 spot. Notice that if someone gets the same score as you, they will go above you on the top scorers list.
You will be given two
Given the points you have (you think all your solutions are correct), return the probability you will make the top 5.
Notes
- Your return value must have an absolute or relative error less than 1e-9.
Constraints
- results and accuracies will have the same number of elements.
- results will have between 1 and 50 elements, inclusive.
- Each element of results and accuracies will contain between 5 and 50 characters, inclusive.
- Each element of results will be formatted as "A B C", where A, B and C are integers between 0 and 1000, inclusive.
- Each element of accuracies will be formatted as "A B C", where A, B and C are integers between 0 and 100, inclusive.
- All integers in both results and accuracies will NOT contain any leading zeroes.
- points will be between 0 and 2000, inclusive.
Examples
0)
{"200 200 200",
"200 200 200",
"200 200 200",
"200 200 200",
"200 200 200"}
{"100 100 100",
"100 100 100",
"100 100 100",
"100 100 100",
"0 0 50"
}
100
Returns: 0.5
The first four people always solve their problems correctly (getting 600 points each) and finish higher than you. Your success depends on the fifth person, who has a 50-50 chance of solving the 3rd problem, and beating you.
1)
{"200 200 200",
"200 200 200",
"200 200 200",
"200 200 200",
"200 200 200",
"200 200 200"}
{"100 100 100",
"100 100 100",
"100 100 100",
"100 100 100",
"0 0 50",
"0 0 0"}
100
Returns: 0.5
2)
{"200 200 200",
"200 200 200",
"200 200 200",
"200 200 200",
"200 200 200",
"200 200 200",
"200 200 200"}
{"100 100 100",
"100 100 100",
"100 100 100",
"100 100 100",
"0 0 50",
"0 0 0",
"0 0 50"}
100
Returns: 0.25
3)
{"1000 1000 1000"}
{"100 100 100"}
0
Returns: 1.0
4)
{"200 200 200",
"200 200 200",
"200 200 200",
"200 200 200",
"200 200 200"}
{"100 100 100",
"100 100 100",
"100 100 100",
"100 100 100",
"100 100 100"}
100
Returns: 0.0
Your performance isn't good enough for you to have any chance of making the top 5.
40)
{"200 200 200",
"200 200 200",
"200 200 200",
"200 200 200",
"600 600 600"}
{"100 100 100",
"100 100 100",
"100 100 100",
"100 100 100",
"75 75 75"
}
500
Returns: 0.015625
The fifth contestant must fail all his problems.
42)
{"200 200 200",
"200 200 200",
"200 200 200",
"200 200 200",
"33 33 33",
"33 200 200"}
{"100 0 0",
"0 0 100",
"0 100 0",
"100 100 100",
"100 100 100",
"33 80 50"
}
200
Returns: 0.10000000000000009
The last contestant must fail both the second and third problems to grant you a top 5 spot. The correctness of his first problem does not affect the result.
Submissions are judged against all 56 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TopFive with a public method double findProbability(vector<string> results, vector<string> accuracies, int points) · 56 test cases · 2 s / 256 MB per case