Connection Status:
Competition Arena > KnightCircuit2

KnightCircuit2

SRM 564 · 2012-06-05 · by vexorian

SRM 564 · 2012-06-05 · by vexorian · Simple Math
Class Name: KnightCircuit2
Return Type: int
Method Name: maxSize
Arg Types: (int, int)
Problem Statement

Problem Statement

The knight is a chess piece that moves by jumping: two cells in one direction, one in the other. Formally, a knight standing on the cell (x,y) can move to any of the following eight cells: (x+2,y+1), (x+2,y-1), (x-2,y+1), (x-2,y-1), (x+1,y+2), (x+1,y-2), (x-1,y+2), and (x-1,y-2). Of course, if the 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 chessboard 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 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. 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.

Constraints

  • w and h will each be between 1 and 45000, inclusive.
Examples
0)
1
1
Returns: 1

Note that a sequence that consists of a single cell is considered to be a valid knight circuit.

1)
15
2
Returns: 8

If you start at any corner of the board, it is possible to move the knight to visit 8 cells, and then do the same moves in reverse in order to return to the starting cell. One possibility for the first eight cells of an optimal knight circuit is shown below: 1...3...5...7.. ..2...4...6...8

2)
100
100
Returns: 10000

It is possible to make a Knight circuit that contains all the cells on the board.

3)
3
3
Returns: 8
4)
5
4
Returns: 20

Submissions are judged against all 122 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class KnightCircuit2 with a public method int maxSize(int w, int h) · 122 test cases · 2 s / 256 MB per case

Submitting as anonymous