## DMOPC '21 Contest 1 P2 - Folding Clothes

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

One of the daunting chores you must face, whether you're 18 or 28, is the task of doing laundry. On one occasion, you find yourself with a massive stack of laundry consisting of pieces of clothing, the -th piece of clothing from the top having width . You would like to arrange these clothes in non-decreasing order of width from top to bottom.

To do this, you may temporarily form a second stack of clothes next to the first one. In one move, you may choose a positive number of clothes off the top of one stack and move it to the other stack, maintaining the same relative order of clothes in the pile you moved (you may not flip or rearrange the pile of clothes in any other way).

Since you would like to get back to filmmaking as soon as possible, please find a sequence of moves that arranges the clothes in non-decreasing order of width back in the original stack. Your solution will be scored based on the number of moves used.

#### Input Specification

The first line contains an integer , the number of clothes in the stack.

The next line contains integers , the width of the -th piece of clothing from the top.

#### Output Specification

On the first line, output an integer , the number of moves in your solution.

Then, on the -th of the next lines, output an integer , describing your -th move. If , it represents moving clothes off the top of the first (and original) stack to the second stack. If , it represents moving clothes off the top of the second stack back to the first.

All must represent valid moves. That is, must be non-zero, and you should not try to move more clothes than there currently are in the stack. In the end, the clothes should be arranged in non-decreasing order of width from top to bottom in the first stack.

#### Scoring

For each test case:

If any of your are invalid, the final condition is not met, or , your score will be for that case and you will receive a Wrong Answer verdict.

Otherwise, your score for the case will be determined by the following formula:

In particular, a full score will be given if your solution uses no more than moves.

Your final score will be the minimum score over all test cases.

4
2 1 1 3

3
1
2
-3

#### Explanation

Initially, the stacks look like this:

2
1
1
3

After the first move, the stacks look like this:

1
1
3   2

After the second move, the stacks look like this:

1
1
3   2

Finally, after the third move, the stacks look like this:

1
1
2
3

All moves were valid and the clothes are arranged in non-decreasing order of width from top to bottom in the first stack, so this is a valid output.

Since , the score for this output is calculated as .