KnightCircuit | Topcoder Archive

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 the ints w and h: the width (in columns) and the height (in rows) of a rectangular chessboard. You are also given the ints 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.

Definition

Class:: KnightCircuit
Method:: maxSize
Parameters:: int, int, int, int
Returns:: long
Method signature:: long maxSize(int w, int h, int a, int b)
(be sure your method is public)

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

```
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.
```
3
```
```
20
```
```
1
```
```
3
```
```
Returns: 11
```
```
100000
```
```
100000
```
```
1
```
```
2
```
```
Returns: 10000000000
```
It is possible to make a circuit that contains every cell on the board.
```
3
```
```
3
```
```
1
```
```
2
```
```
Returns: 8
```
```
30
```
```
30
```
```
8
```
```
4
```
```
Returns: 64
```
```
32
```
```
34
```
```
6
```
```
2
```
```
Returns: 136
```

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.