CCC '12 S4 - A Coin Game
View as PDFCanadian Computing Competition: 2012 Stage 1, Junior #5, Senior #4
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:
- The initial coin line-up defines all positions where coins can be placed. That is, no additional positions can be added later, and even if one of the positions does not have a coin on it at some point, the position still exists.
- The game consists of a sequence of moves and in each move Jo moves a coin from one position to an adjacent position.
- The coins can be stacked, and in a move Jo always takes the top coin from one stack and moves it to the top of another stack.
- In a stack of coins, Jo never places a higher-value coin on top of a lower-value coin.
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 moves (where
denotes that coin
is on top of coin
):
| 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 |
| Move | Position 1 | Position 2 | Position 3 |
|---|---|---|---|
| 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.
Input Specification
The input will contain some number of test cases. A test case consists of two lines. The first line will contain a positive integer (
), which is the number of coins. We assume that the coins are labeled
. The second line will contain a list of numbers
to
in an arbitrary order, which represents the initial coin configuration. For the above example, the input test case would be:
3
3 2 1The end of test cases is indicated by on a line by itself.
Output Specification
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.
Sample Input
3
3 2 1
2
2 1
0Output for Sample Input
20
IMPOSSIBLE
Comments
Why dmoj is so fast?? I made some test cases and they take forever to run on my pc. lol (‾◡◝)
The time limit in CCC online grader is 60s, so some TLE migits be correct solution.
Wut? I don't get your point...
Edit: I see but TLE means Time Limit Exceed, in other words the code was too slow. By 60s on the website u probably mean the time in total. Right?
Would it be possible to find a trend and code accordingly?
What should the output be when there is only one coin? I keep getting an index error for the first batch and I'm pretty sure it's cuz there's only one coin in the test case. I tried impossible, 0, 1, 2, and they all didn't work.
it should be 0, because it's already in the goal line-up.
Can anyone gives me an idea?
though i thinks it's quite like hanoi tower queston...
try not to overthink and go with your first instinct
I don't think my solution should pass
I TLE on:
...gg problem...