TheKnights | Topcoder Archive

Problem Statement

John and Brus have two (a, b) chess knights. When an (a, b) knight moves, it can move a squares horizontally and b squares vertically, or b squares horizontally and a squares vertically.

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
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.