REVSEQ - Reverse the Sequence
This is a very ad-hoc problem. Consider a sequence (N, N-1, ..., 2, 1). You have to reverse it, that is, make it become (1, 2, ..., N-1, N). And how do you do this? By making operations of the following kind.
Writing three natural numbers A, B, C such that 1 ≤ A ≤ B < C ≤ N means that you are swapping the block (block = consecutive subsequence) of elements occupying positions A...B with the block of elements occupying positions B+1..C. Of course, the order of elements in a particular block does not change.
This means that you can pick any two adjacent blocks (each of an arbitrary length) and swap them. The problem can easily be solved in N-1 operations, but to make it more difficult, you must think of a faster way.
Input
A natural number 1 < N < 100.
Output
Output at most 50 operations, one per line. Each operation is represented by three numbers as described above.
Example
Input: 5 Output: 2 3 5 1 2 4 2 3 5
Explanation of the sample
(5 4 3 2 1) → (5 2 1 4 3) → (1 4 5 2 3) → (1 2 3 4 5)
hide comments
meiji:
2014-08-07 11:08:44
It looks that way. Thanks. |
|
Adrian Satja Kurdija:
2014-08-07 11:08:44
No, the answer is not unique. I think your solution uses more than 50 operations. Last edit: 2011-04-28 20:10:31 |
|
meiji:
2014-08-07 11:08:44
WA...
|
Added by: | Adrian Satja Kurdija |
Date: | 2011-03-18 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | originated from a mathematical problem |