Problem C
Shuffles
The most common technique for shuffling a deck of cards is called the Riffle or Dovetail shuffle. The deck is split into two stacks, which are then interleaved with each other. The deck can be split anywhere, and the two stacks can be interleaved in any way.
For example, consider a deck with 10 unique cards:
1 2 3 4 5 6 7 8 9 10
Split them somewhere
1 2 3 4 5 6 7 8 9 10
And interleave them in some way:
1 2 7 3 8 9 4 5 10 6
Do it again. Split them somewhere:
1 2 7 3 8 9 4 5 10 6
And interleave them in some way:
3 8 1 9 4 5 2 7 10 6
This is one possible ordering after
Input
Each input will consist of a single test case. Note that
your program may be run multiple times on different inputs.
Each test case will begin with a single integer
Output
Output a single line with a single integer indicating the minimum number of shuffles that could possibly put the deck in the given order.
Sample Input 1 | Sample Output 1 |
---|---|
10 1 2 7 3 8 9 4 5 10 6 |
1 |
Sample Input 2 | Sample Output 2 |
---|---|
10 3 8 1 9 4 5 2 7 10 6 |
2 |
Sample Input 3 | Sample Output 3 |
---|---|
8 2 1 4 3 6 5 8 7 |
3 |