KnightCircuit
SRM 564 · 2012-06-05 · by vexorian
SRM 564 · 2012-06-05 · by vexorian · Simple Math
Problem Statement
Problem Statement
The (a,b)-knight is a chess piece that moves by jumping, just as a regular knight, but the jump is a cells in one direction, b in the other. Formally, an (a,b)-knight standing on the cell (x,y) can move to any of the following eight cells:
(x+a,y+b), (x+a,y-b), (x-a,y+b), (x-a,y-b), (x+b,y+a), (x+b,y-a), (x-b,y+a), and (x-b,y-a).
Of course, if the (a,b)-knight is close to the edge of the board, some of these cells might not be on the board.
It is not allowed to jump to a cell that is not on the board.
A knight circuit is a sequence of cells on a chess board that starts and ends with the same cell. Each consecutive pair of cells in the knight circuit must correspond to a single jump of the (a,b)-knight. The knight circuit may visit each cell arbitrarily many times. The size of a knight circuit is the number of different cells visited by the circuit.
You are given theint s w and h: the width (in columns) and the height (in rows) of a rectangular chessboard. You are also given the int s a and b: the parameters of your knight. Return the maximum knight circuit size that can be obtained on the given board. You are free to choose any cell as the start of your circuit.
A knight circuit is a sequence of cells on a chess board that starts and ends with the same cell. Each consecutive pair of cells in the knight circuit must correspond to a single jump of the (a,b)-knight. The knight circuit may visit each cell arbitrarily many times. The size of a knight circuit is the number of different cells visited by the circuit.
You are given the
Constraints
- w, h will each be between 1 and 100000, inclusive.
- a and b will each be between 1 and 10, inclusive.
- a and b will not be equal.
Examples
0)
1 1 2 1 Returns: 1
This is a 1x1 board. Note that a sequence that consists of a single cell is considered to be a valid knight circuit.
1)
3 20 1 3 Returns: 11
2)
100000 100000 1 2 Returns: 10000000000
It is possible to make a circuit that contains every cell on the board.
3)
100000 20 1 2 Returns: 2000000
4)
3 3 1 2 Returns: 8
Submissions are judged against all 173 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class KnightCircuit with a public method long long maxSize(int w, int h, int a, int b) · 173 test cases · 2 s / 256 MB per case