|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||0||0||0||0.000%|
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:
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.
The input consists of several test cases. The first line of a test case contains a single integer N (1 ≤ N ≤ 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 Nth 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.
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 ’#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 ‘push x’ or ‘pop x’ where ‘x’ is 1 or 2; ‘push x’ moves the topmost card from the stock pile to intermediate pile x, and ‘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 ‘impossible’.
4 4 1 3 2 4 1 4 3 2 4 2 2 2 1 0
#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 1 push 2 pop 2 pop 2 pop 1 pop 1