|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
E - Two-Stacks Solitaire
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Card games for one player are called Patience in Britain and Solitaire in the United States. One very difficult (some say maddening) solitaire game is called Two-Stacks and has the following rules:
Tableau
The tableau consists of a stock pile, two intermediate piles and one foundation pile.
Cards
A game may use up to four complete decks, or parts of those four decks. A complete deck contains $52$ cards; since all cards in a deck can be ordered, in this description we will forget about faces and suits and we will use the numbers from $1$ to $52$ to represent the cards in a deck.
Dealing
Once the cards to be used in the game have been chosen, they are dealt face up in the tableau, one on top of the other, forming the stock pile.
Moving cards
Cards may be moved one at a time. A card can be moved from the stock pile to one of the intermediate piles, or from one intermediate pile to the foundation pile. In a pile (stock or intermediate) only the topmost card can be moved, although all the others are visible.
Object
The goal is to have all cards used in the game in non-decreasing order, from bottom to top, constituting the foundation pile.
As you may have noticed by now, even when a solution exists, chances of winning a Two-Stacks solitaire game are very low. But your grandmother has just learned the game and loved it. She has asked you to help her to learn playing the game, by writing a program that would coach her through her first tries, showing which movements to make.
Input
The input consists of several test cases. The first line of a test case contains a single integer $N$ $(1 \leq N \leq 208)$, representing the number of cards in the game. The second line of a test case contains a sequence of $N$ integers (between $1$ and $52$), separated by single blank spaces, representing the cards. The cards will be dealt in the order they appear in the input, so that the topmost card in the stock pile is the $N$-th card in the line. Notice that each number from $1$ to $52$ will appear at most $4$ times in each test case. The end of input is indicated by a test case with $N = 0$.
Output
For each test case in the input your program must produce an answer. The first line of an answer must contain a test case identifier, in the form $\texttt{’#i’}$ where $i$ starts from $1$ and is incremented for every test case. Then, if it is possible to win the game, print a sequence of movements to win the game. Each movement must be described in a separate line, in the form $\texttt{‘push x’}$ or $\texttt{‘pop x’}$ where $\texttt{‘x’}$ is $1$ or $2$; $\texttt{‘push x’}$ moves the topmost card from the stock pile to intermediate pile $x$, and $\texttt{‘pop x’}$ moves the topmost card from intermediate pile $x$ to the foundation pile. If more than one solution exists, print any one. If it is not possible to win the game, print a line with the word $\texttt{‘impossible’}$.
Sample test(s)
Input
4
4 1 3 2
4
1 4 3 2
4
2 2 2 1
0
Output
#1
push 1
push 2
push 1
pop 1
pop 1
push 1
pop 2
pop 1
#2
impossible
#3
push 1
push 2
push 2
push 2
pop 1
pop 2
pop 2
pop 2