DMOPC '21 Contest 1 P2 - Folding Clothes

View as PDF

Submit solution


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 N pieces of clothing, the i-th piece of clothing from the top having width w_i. 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.

Constraints

1 \le N \le 2 \times 10^3

1 \le w_i \le 10^9

Input Specification

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

The next line contains N integers w_i (1 \le i \le N), the width of the i-th piece of clothing from the top.

Output Specification

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

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

All x_j must represent valid moves. That is, x_j must be non-zero, and you should not try to move more clothes than there currently are in the stack. In the end, the N 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 x_j are invalid, the final condition is not met, or M > 7N, your score will be 0 for that case and you will receive a Wrong Answer verdict.

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

\displaystyle S = \left\lfloor \min(100, \frac{20}{N}(7N - M)) \right\rfloor

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

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

Sample Input

4
2 1 1 3

Sample Output

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 M \le 7N, the score for this output is calculated as S = \left\lfloor \min(100, \frac{20}{4}(7 \times 4 - 3)) \right\rfloor = \left\lfloor \min(100, 125) \right\rfloor = 100.


Comments

There are no comments at the moment.