Card Magic
Time limit2sMemory limit128 MB
Find an initial card order so that repeatedly cycling and dealing cards produces the sequence 1 to N on the table.
- Level
Medium4 of 10
- Topics
- Simulation, Queue, Implementation
- Solved
- No attempts yet
Problem
There are N cards arranged in a line, numbered from 1 to N. You need to choose their initial order so that the following magic trick places the cards on the table in the order 1, 2, ..., N.
On step i (1 <= i <= N), repeat the following operation i times on the remaining deck: move the front card to the back. Then place the front card on the table. The card placed on step i must be i.
Given N, print an initial card order that satisfies this process.
Input
The first line contains the number of cards N.
- 1 <= N <= 1,000
Output
Print the initial card order from front to back on one line, separated by spaces.
Hint
If the initial order is 2 1 4 3, the process works as follows.
- Move the front card 2 to the back, making 1 4 3 2, then place 1 on the table.
- From the remaining deck 4 3 2, move the front card to the back twice, making 2 4 3, then place 2 on the table.
- From the remaining deck 4 3, move the front card to the back three times, making 3 4, then place 3 on the table.
- Place the last card, 4, on the table.