Problem Statement
John and Brus place their knights on two different cells of an n by n chessboard. The pair of cells is chosen uniformly at random. A chessboard cell is attacked if it is either occupied by one of the knights, or if it can be reached by one of the knights in a single move. Return the expected number of attacked cells.
Definition
- Class:
- TheKnights
- Method:
- find
- Parameters:
- int, int, int
- Returns:
- double
- Method signature:
- double find(int n, int a, int b)
- (be sure your method is public)
Notes
- The returned value must be accurate to within a relative or absolute value of 1E-9.
- Informally, the expected number of attacked cells can be seen as the average number over very many rounds of the process. See http://en.wikipedia.org/wiki/Expected_value for a formal definition.
Constraints
- n will be between 2 and 1,000,000,000, inclusive.
- a will be between 1 and 1,000,000,000, inclusive.
- b will be between 1 and 1,000,000,000, inclusive.
Examples
2
1
1
Returns: 3.3333333333333335
If we fix one of the knights, there are three ways to place the other one. In two of those three cases all 4 cells on the board will be attacked. In the last case only the 2 cells occupied by the knights will be attacked. Thus the expected value is 4*(2/3) + 2*(1/3) = 10/3.
47
7
74
Returns: 2.0
For any placement of the knights only two cells will be attacked.
3
2
1
Returns: 4.888888888888889
9999
999
99
Returns: 16.25885103191273
10
1
6
Returns: 7.636363636363637
5
5
4
Returns: 2.0
4
4
5
Returns: 2.0
124823342
45386564
100951687
Returns: 3.9472984595887532
183856503
102695213
60284295
Returns: 6.7471367189191875
558782248
558463543
381881321
Returns: 2.002889041412912
925404249
438144414
800016186
Returns: 3.141494468813188
921115693
689349088
202813053
Returns: 5.139423765315677
633986483
186837751
425941920
Returns: 5.703124894165056
428649871
95595700
196624736
Returns: 8.729216464744985
330167461
327554576
20514242
Returns: 2.1187537513067953
899169639
472435499
680900359
Returns: 3.843260510931507
903943749
588260565
302934536
Returns: 5.71509350225846
551344169
182448637
414844903
Returns: 4.650379856570859
800051864
651969236
179379089
Returns: 4.297473491182333
807648924
432243241
379393432
Returns: 5.943469888141478
999999048
999999924
999999452
Returns: 2.0
999999234
999999550
999999873
Returns: 2.0
999999245
999999839
999999540
Returns: 2.0
999999750
999999818
999999760
Returns: 2.0
999999409
999999572
999999921
Returns: 2.0
703191760
145374404
145374404
Returns: 7.03415388011933
219470790
114967900
114967900
Returns: 3.813815609122127
129333615
60861281
60861281
Returns: 4.242319105047424
968295264
605815983
605815983
Returns: 3.1210906926463755
591907600
58565539
58565539
Returns: 8.49521937828574
1000000000
583526549
123155129
Returns: 7.842921750672317
999999999
304781299
330392701
Returns: 9.448376258513914
1000000000
12556648
541681559
Returns: 9.241015962631268
1000000000
630812393
15410460
Returns: 7.8159720983972925
999999999
817504650
227186913
Returns: 4.256556705974505
999999999
757598303
532893574
Returns: 3.8116382377432254
999999999
890695666
122069938
Returns: 3.535384958882839
999999999
281698010
168402490
Returns: 11.557410335309147
1000000000
266151066
348129641
Returns: 9.653989888933557
999999999
702171433
280562118
Returns: 5.428306445645552
2
1
1
Returns: 3.3333333333333335
3
1
1
Returns: 4.833333333333333
4
1
2
Returns: 7.166666666666667
3
2
2
Returns: 2.7777777777777777
1000000000
1000000000
1000000000
Returns: 2.0
1000000000
1
1
Returns: 9.999999984
1000000000
1
2
Returns: 17.999999952
1000000000
2
2
Returns: 9.999999968
100000
300
200
Returns: 17.9200959928535
999999999
523
11337
Returns: 17.99981024009468
238293583
2374
48569
Returns: 17.996579512348426
1000000000
2
3
Returns: 17.99999992
1000000000
268435456
268435456
Returns: 6.281493456303424
1000000000
1230
2131
Returns: 17.99994622404194
1000000000
3
2
Returns: 17.99999992
1000000000
500000000
400000000
Returns: 6.8