# PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

# DIFFICULTY:

CAKEWALK

# PROBLEM:

Given a chess board of size N\times N. A ‘disabled’ king is initially at cell (1,1). In one move, the king can move from cell (x,y) to any of the following cells (provided they are within the board):

- (x, y + 1)
- (x, y - 1)
- (x + 1, y + 1)
- (x + 1, y - 1)
- (x - 1, y + 1)
- (x - 1, y - 1)

Determine the minimum moves required to reach cell (N,1).

# EXPLANATION:

**Observation:** The minimum moves required is always \ge N-1.

## Proof

In one move, the king can travel atmost 1 step to the right. The destination cell is exactly N-1 steps to the right of the initial cell.

Thus, the minimum moves required is always \ge N-1.

There are now two cases:

- N is odd: The minimum number of moves required is N-1, which can be achieved as follows:

- N is even: Here, it isn’t hard to conclude that it is impossible to reach the destination cell using only N-1 moves. However, it can be done in N moves, in the following fashion:

Therefore, output

- N-1 when N is odd, and
- N otherwise.

# TIME COMPLEXITY:

per test case.

# SOLUTIONS:

Editorialist’s solution can be found here

**Experimental:** For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

- 1
- 2
- 3
- 4
- 5

0 voters