시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 12 | 10 | 10 | 83.333% |
When she is bored, Jo Coder likes to play the following game with coins on a table. She takes a set of distinct coins and lines them up in a row. For example, let us say that she has a penny (P, worth \$0.01), a nickel (N, worth \$0.05), and a dime (D, worth \$0.10). She lines them up in an arbitrary order, (for example, D N P), and then moves them around with the goal of placing them in strictly increasing order by value, that is P N D (i.e., \$0.01, \$0.05, \$0.10). She has particular rules that she follows:
For simplicity, let the coins have consecutive integer values (e.g., denote the penny as 1, nickel as 2, and dime as 3). Then, in the above example, Jo could play the game in the following way in 20 moves (where XY denotes that coin X is on top of coin Y):
Move | Position 1 | Position 2 | Position 3 |
initial | 3 | 2 | 1 |
1 | 3 | 12 | |
2 | 13 | 2 | |
3 | 13 | 2 | |
4 | 3 | 1 | 2 |
5 | 3 | 12 | |
6 | 3 | 12 | |
7 | 13 | 2 | |
8 | 1 | 3 | 2 |
9 | 1 | 23 | |
10 | 123 | ||
11 | 23 | 1 | |
12 | 2 | 3 | 1 |
13 | 2 | 13 | |
14 | 12 | 3 | |
15 | 12 | 3 | |
16 | 2 | 1 | 3 |
17 | 2 | 13 | |
18 | 2 | 13 | |
19 | 12 | 3 | |
20 | 1 | 2 | 3 |
For some starting configurations, it is not always possible to obtain the goal of strictly increasing order.
The input will contain some number of test cases. A test case consists of two lines. The first line contains a positive integer n (n < 5), which is the number of coins. We assume that the coins are labeled 1, 2, 3, . . . n. The second line contains a list of numbers 1 to n in an arbitrary order, which represents the initial coin configuration.
The end of test cases is indicated by 0 on a line by itself.
For each test case, output one line, which will either contain the minimal number of moves in which Jo can achieve the goal coin line-up, or, if it is not possible to achieve the goal coin line-up, IMPOSSIBLE.
3 3 2 1 2 2 1 0
20 IMPOSSIBLE