TheKnights
TCO13 Round 1C · 2013-02-19 · by Vasyl[alphacom]
TCO13 Round 1C · 2013-02-19 · by Vasyl[alphacom] · Simple Math
Problem Statement
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.
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.
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
0)
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.
1)
47 7 74 Returns: 2.0
For any placement of the knights only two cells will be attacked.
2)
3 2 1 Returns: 4.888888888888889
3)
9999 999 99 Returns: 16.25885103191273
4)
10 1 6 Returns: 7.636363636363637
Submissions are judged against all 56 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TheKnights with a public method double find(int n, int a, int b) · 56 test cases · 2 s / 256 MB per case