PEGS - Triangle
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.
|
|
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 |