Problem Statement
This problem has a non-standard time limit: 4 seconds.
Elly participates in two programming competitions: TopForces and CodeCoder. Each week she takes part in exactly two matches â on Tuesdays she competes on TopForces and on Saturdays on CodeCoder.
Both TopForces and CodeCoder keep a rating of their users â an integer between 1 and 1000, inclusive. After each match a contestant's rating can change by at most 100 points in either direction â increase, if the contestant performed well, or decrease, if he or she did not.
Elly's performance is very inconsistent. It is so inconsistent that we can assume that after each match her rating becomes any possible new rating with equal probability. Of course, the rating never goes below 1 or over 1000.
Thus, for example, if her current rating is 42, it can become any integer in the range [1, 142] with chance 1/142 for each value. If, instead, her rating is 930 it can go down to 830 or up to 1000 with chance 1/171 for each value in the range. Finally, if it is 666, her new rating will be in [566, 766] with chance 1/201 for each value.
One Sunday Elly thought what a lucky coincidence it would be if both her ratings became equal at some point in time in the next N weeks. We assume ratings are updated immediately after the contest's end, thus TopForces's rating is updated on Tuesday, and CodeCoder's on Saturday. Her current rating in TopForces is A and her current rating in CodeCoder is B. What is the expected chance of this happening?
Definition
- Class:
- EllysTwoRatings
- Method:
- getChance
- Parameters:
- int, int, int
- Returns:
- double
- Method signature:
- double getChance(int N, int A, int B)
- (be sure your method is public)
Notes
- Your return value must have an absolute error at most 1e-9.
Constraints
- N will be an integer between 1 and 52, inclusive.
- A and B will be integers between 1 and 1000, inclusive.
- A and B will be distinct.
Examples
13
42
666
Returns: 0.001968164704
It turns out that even after 13 weeks the chance of her ratings becoming equal at any point are very slim.
3
1
1000
Returns: 0.0
The closest ratings she can get after 3 weeks is 301 in TopForces and 700 in CodeCoder. Thus the chance of them ever being equal is zero.
20
216
219
Returns: 0.083322288706
42
973
123
Returns: 0.019345240789
1
333
666
Returns: 0.0
1
420
620
Returns: 2.4751863E-5
1
500
501
Returns: 0.009900745031
2
200
600
Returns: 6.13E-10
2
500
501
Returns: 0.016838018008
2
1
2
Returns: 0.03223395855
2
999
1000
Returns: 0.032119109503
4
100
900
Returns: 0.0
4
111
888
Returns: 1.0E-12
4
100
836
Returns: 5.02E-10
4
100
837
Returns: 4.52E-10
5
1
1000
Returns: 0.0
5
111
1000
Returns: 2.05E-10
5
123
987
Returns: 1.022E-9
6
4
1000
Returns: 9.39E-10
6
5
1000
Returns: 9.77E-10
6
6
1000
Returns: 1.017E-9
7
1
1000
Returns: 5.2181E-8
10
1
1000
Returns: 8.396738E-6
13
123
321
Returns: 0.032825749602
17
17
177
Returns: 0.075356331762
29
290
920
Returns: 0.014301115955
33
874
295
Returns: 0.020654041763
36
666
777
Returns: 0.098234264948
42
42
420
Returns: 0.076057364855
49
911
666
Returns: 0.112905513053
50
819
870
Returns: 0.163586255585
52
1
2
Returns: 0.209379547649
52
1
1000
Returns: 0.029398176698
52
500
501
Returns: 0.128874637847
52
756
988
Returns: 0.142836984823
19
230
421
Returns: 0.042375505851
31
271
962
Returns: 0.014683985241
1
373
951
Returns: 0.0
34
379
15
Returns: 0.068206187478
19
955
66
Returns: 0.001141897198
49
982
296
Returns: 0.040339186364
34
591
750
Returns: 0.079638729532
41
224
186
Returns: 0.135139550303
22
84
542
Returns: 0.019413377942
26
288
78
Returns: 0.073429813078
41
417
476
Returns: 0.106836253824
48
564
565
Returns: 0.123396211588
40
377
633
Returns: 0.064969867498
15
111
823
Returns: 0.001028933732
42
520
708
Returns: 0.084446820942
22
144
295
Returns: 0.066587822684
52
222
777
Returns: 0.046681608403
52
334
339
Returns: 0.137770878254