Connection Status:
Competition Arena > LateProfessor

LateProfessor

SRM 467 · 2009-11-12 · by vexorian

SRM 467 · 2009-11-12 · by vexorian · Brute Force, Math, Simulation
Class Name: LateProfessor
Return Type: double
Method Name: getProbability
Arg Types: (int, int, int, int, int)
Problem Statement

Problem Statement

Punctuality is not exactly one of Dr. Wesley's strengths. His student John always shows up for class at the scheduled starting time, but he never knows when Dr. Wesley will arrive. This is a problem for John because he cannot stay in the same place doing nothing for a long period of time. Therefore, he has come up with the following method to reduce the amount of time he spends waiting by the classroom door.
  • John arrives at time 0.
  • John waits for Dr. Wesley to arrive.
  • If after waitTime seconds Dr. Wesley has not arrived yet, John goes to take a walk for walkTime seconds.
  • John therefore arrives back to the classroom exactly at time waitTime + walkTime.
  • If Dr. Wesley has not arrived yet, John waits another waitTime seconds and then proceeds to take a new walk. The process is repeated until John becomes aware that Dr. Wesley has arrived.
Overall, John stands in front of the class door from time 0 to time waitTime, inclusive, then from time walkTime + waitTime to time walkTime + 2*waitTime, inclusive, and so on. At all other time moments he walks outside.

This has solved John's patience issues, but it has caused a new problem. When John returns from a walk, if Dr. Wesley is already in the classroom, it will appear that John has arrived late to class. Dr. Wesley does not like that, and he will deny John access to the class if he arrives lateTime or more seconds after the time at which Dr. Wesley arrived.

There are multiple variables that affect Dr. Wesley's arrival time, but for the purpose of the problem, assume that the arrival time will be a real number chosen uniformly from bestArrival to worstArrival, inclusive. Return the probability that John will be denied access to Dr. Wesley's class.

Notes

  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • waitTime, walkTime, lateTime and worstArrival will each be between 1 and 10000000, inclusive.
  • bestArrival will be between 0 and worstArrival, inclusive.
Examples
0)
20
30
10
0
50
Returns: 0.4

The professor will arrive at some random moment between 0 and 50 seconds, inclusive. During this interval, these are John's activities: He waits from time 0 to time 20, inclusive. He takes a walk between times 20 and 50, non-inclusive. He arrives back at time 50. John will only be too late if the professor arrives while he is away, and more than 10 seconds before he returns. This only happens if the professor arrives strictly between times 20 and 40. The probability that this will happen is (40-20)/(50-0) = 0.4.

1)
20
30
10
30
100
Returns: 0.42857142857142855

If the professor arrives between 30 and 40 seconds or between 70 and 90 seconds, John will be late to the class.

2)
20
40
50
0
300
Returns: 0.0

John's walking time is 40 seconds. Hence, even if the professor arrives while John is taking a walk, John will always be less than 50 seconds late.

3)
10
100
50
59
60
Returns: 1.0
4)
300
50
25
9000
10000
Returns: 0.075
11)
20
30
10
90
90
Returns: 1.0

Dr. Wesley will always arrive at time 90 seconds. John will arrive at time 100 seconds after taking two different walks. Since the time difference is equal to 10 seconds, John will be too late.

Submissions are judged against all 309 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LateProfessor with a public method double getProbability(int waitTime, int walkTime, int lateTime, int bestArrival, int worstArrival) · 309 test cases · 2 s / 256 MB per case

Submitting as anonymous