﻿ Fuzhou University OnlineJudge ﻿
Problem 1518 Checkers

Problem Description

The rules of the checkers game is very simple: First, the number of participants in the game is even -- two, four or six peoples. Then you play with the diagonal player. Chesses can move one step in a straight line to the adjacent 6 directions. If adjacent location has a chess, and the next adjacent location is empty in the same line, then your chess can directly “jump” to the empty location. In the process of “jump”, as long as meeting the same conditions that is defined above, you can “jump” consecutively. The first player who occupies all the oppositive positions wins.

Figure 1:

Oaiei is tired of playing with others, he want to play himself. His game’s rules is showed as follows:

1. The chessboard is a straight line which has N lattices.
2. There are two sides divided by the middle empty lattice, each side has the same number of chesses.
3. In the initial state, only the middle lattice is empty.
4. There are two possible ways of moving:
• a chess can move directly to the adjacent empty lattice
• a chess can jump over one lattice into the next empty lattice
5. When both sides of the chesses exchange, namely the end state, the game is over.

When the size of chessboard N is 7，the initial state is showed as following:

The end state is showed as following:

Now,your task is coming. Give you the size of chessboard N, and you should compute the minimum move steps that can change the initial state into the end state.

Input

There are multiple test cases. Each test case contains a positive odd integer N (N<20) indicating the size of chessboard.

Output

For each test case, print the integer number which indicting the minimum move steps.

5

8

Hint

If the chessboard size is five, then one of solutions with least number of steps is showed as following:

Source

FZU 2007 ICPC Qualification Round I

Submit  Back  Status  Discuss
﻿