PEGS - Triangle

no tags 

Consider the following common single-player game.

A board has fifteen holes, arranged in a triangular pattern. Pegs fit in these holes.

A valid move is to take a peg and jump in a straight line over an adjacent peg to the an empty hole two positions away from the starting position. The peg that was jumped is removed from the board. The player wins the game when there is only one peg remaining.

For example, in the game below, the player wins in two moves.

    x             .            .
   x .           . .          . .
  . . .   =>    x . .   =>   . . .
 . x . .       . x . .      . . . .
. . . . .     . . . . .    . . x . .

In the game below, the player has no possible moves and loses.

    x
   . .
  x . .
 . . . .
. . . . .

Given a starting position, determine if it is possible to win.

Input

The first line is N, the number of starting pegs (0 < N < 15).

The next N lines are the pegs' positions. The positions on the board are numbered as following:

         1
       2   3
     4   5   6
   7   8   9  10
11  12  13  14  15

Examples

Input:
3
1
2
8

Output:
yes
Input:
14
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Output:
yes
Input:
13
2
3
13
5
8
11
10
9
12
4
14
15
6

Output:
no

hide comments
candide: 2014-05-16 02:48:26

Funny and innovatory question. Problem statement is quite clear. But, please, update the last example.
--ans(Francky)--> Updated, thanks.

@Francky : are you sure the 3rd example has been fixed ? we expect the pegs to be distinct but peg numbered 13 appears twice. Moreover, the three examples return "yes", for clarity, not all-the-same answer is better.

[Simes]: finally fixed

Last edit: 2024-09-18 14:21:43
Ashwini: 2013-12-24 18:10:14

if n is 1 or 0 then what to print?

Sachin Railhan: 2013-12-10 21:17:40

Good Problem.Simple Recursion can get AC.

Last edit: 2014-05-28 21:25:46
Goldie: 2013-12-08 20:29:53

nice one... enjoyed solving .. :)

Last edit: 2013-12-09 17:09:07
Mitch Schwartz: 2013-10-26 16:21:00

@Arun Banala: No, only NE/SW, NW/SE, and E/W.

Arun Banala: 2013-10-26 14:01:00

Are the pegs considered to be adjacent if they are in the same vertical line?

Mitch Schwartz: 2013-10-25 00:00:53

Moved to classical.


Added by:BYU Admin
Date:2013-10-18
Time limit:25s-50s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64