TestProctoring
2018 TCO Fun 3B · 2018-04-20 · by lg5293
Problem Statement
This problem has a non-standard time limit: 4 seconds.
Bob is a teacher proctoring a test for his students. All students are taking the test simultaneously.
Every second, student i has probability p[i]/q[i] of finishing the test and leaving the classroom. (The process is discrete, i.e., for each student the time spent taking the test is always an integer.)
Bob must stay in the room until all students have completed the test. Bob would like to know the expected amount of time he needs to stay.
Notes
- Your answer will be accepted if it has absolute or relative error at most 1e-6.
Constraints
- p will contain between 1 and 20 elements, inclusive.
- q will have the same length as p.
- Each element of q will be between 1 and 10^9, inclusive.
- The i-th element of p will be between 1 and q[i], inclusive.
{2}
{4}
Returns: 2.0
There is a single student. The student has probability 1/2 of finishing the test each second. The expected time Bob waits is 2.
{1,2}
{2,4}
Returns: 2.6666666666666665
There are two students, each with probability 1/2 of finishing. In this case, Bob must wait a bit longer - it is quite likely that at least one of the two students will take more than 2 seconds.
{3,1,2,4,2,5}
{3,1,2,4,2,5}
Returns: 1.0
Every student will finish the test in the first second.
{1,1,1,1,1,1,1,1}
{1,2,3,4,5,6,7,8}
Returns: 13.604834665120991
{2,3,5,7,11,13,17}
{3,5,7,11,13,17,19}
Returns: 2.6299445065924276
Submissions are judged against all 70 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TestProctoring with a public method double expectedTime(vector<int> p, vector<int> q) · 70 test cases · 2 s / 256 MB per case