27407번 - CPR (Cut-Paste-Reverse) 점수다국어

문제

Consider the list of integers 1, 2, ..., N. On this list you can perform a series of cut-paste operations. A cut-paste operation <x, y, z> consists of cutting the sequence between the values x and y and inserting the sequence immediately after the value z (z can also be 0 to designate an insertion at the beginning of the list). A triplet <x, y, z> constitutes a correct cut-paste operation if

• x appears before y in the list, or x = y;
• z appears outside the sequence from x to y, or z = 0.

Find a series of correct operations that reverses the list, so that after performing the operations the list becomes N, N - 1, ..., 2, 1. The fewer operations you require, the higher your score will be.

입력

The input contains a single integer number N, representing the length of the list.

출력

The outpu must contain a number M on the first line, representing the number of cut-paste operations. Each of the following M lines must contain three numbers x y z representing an operation.

제한

• 1 ≤ N ≤ 5,000

점수

Test cases will be scored individually. For every test, if your solution requires M operations, you will earn points as follows (slashes denote integer divisions):

• 100 points if M ≤ N / 2 + 1;
• 80 points if N / 2 + 1 < M ≤ 2 * N / 3;
• 60 points if 2 * N / 3 < M ≤ 3 * N / 4;
• 40 points if 3 * N / 4 < M ≤ 4 * N / 5;
• 20 points if 4 * N / 5 < M ≤ 5 * N / 6;
• 0 points if M > 5 * N / 6.

The score for the task will be the minimum of the scores for each test.

힌트

The initial list is 1 2 3 4 5 6

After the first operation, the list becomes 2 3 4 5 6 1 (The operation 1 1 6 would have had the same result.)

After the second operation, the list becomes 4 5 2 3 6 1

After the third operation, the list becomes 4 3 6 5 2 1

After the fourth operation, the list becomes 6 5 4 3 2 1

This solution earns full points as 4 = 6 / 2 + 1.