| Submit | All submissions | Best solutions | Back to list |
PEGS - Triangle |
Description
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
| Input | Input | Input |
|---|---|---|
3 1 2 8 |
14 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
13 2 3 13 5 8 11 10 9 12 4 14 15 13 |
| Output | Output | Output |
yes |
yes |
yes |
| 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 |
hide comments
|
2014-05-16 02:48:26 candide
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. Last edit: 2014-05-23 17:30:31 |
|
|
2013-12-24 18:10:14 Ashwini
if n is 1 or 0 then what to print? |
|
|
2013-12-10 21:17:40 Sachin Railhan
Good Problem.Simple Recursion can get AC. Last edit: 2014-05-28 21:25:46 |
|
|
2013-12-08 20:29:53 Goldie
nice one... enjoyed solving .. :) Last edit: 2013-12-09 17:09:07 |
|
|
2013-10-26 16:21:00 Mitch Schwartz
@Arun Banala: No, only NE/SW, NW/SE, and E/W. |
|
|
2013-10-26 14:01:00 Arun Banala
Are the pegs considered to be adjacent if they are in the same vertical line? |
|
|
2013-10-25 00:00:53 Mitch Schwartz
Moved to classical. |
RSS