Fixed-Length Sequence Shift

Ported from Frontier-CS algorithmic/problems/213.

Agentics Interface

Each run executes the submitted zip_project solution once. The run command receives the case input on standard input and must write the candidate answer to standard output. The solution must not use the network during setup, build, or run.

The trusted separated evaluator compiles and runs the source-derived Frontier-CS checker against stdout.txt. Public validation contains one tiny deterministic case. Official cases, reference answers, and scoring metadata are supplied only through the required private asset official-runs.

Scoring

The primary metric is score, the average normalized Frontier-CS checker score on a 0-100 scale. Outputs rejected by the checker receive zero for that case. Official result details are score-only; public validation includes per-case feedback from the checker.

Original Statement

Sequence Shift (moqueve)

Problem Description: You need to sort a permutation of $1\sim n$ on a strange computer.

You can choose a number $x$, and then each time you can cyclically shift a segment of length $x$ to the left or right (the leftmost/rightmost element moves to the rightmost/leftmost position) (shift amount is $1$).

Please restore the sequence to $1\sim n$ within $230\times n$ operations.

Input Format: The first line contains a single integer $n$.

The second line contains $n$ integers, representing the sequence $a$.

Output Format: The first line contains two integers $x$ and $m$, where $m$ represents the number of operations.

The next $m$ lines each contain three integers: the first two represent the shift interval, and the last one represents the direction, where $0$ means left and $1$ means right.

Example: Input: 5 4 2 3 5 1

Output: 3 3 3 5 1 1 3 1 2 4 0

Explanation:

• Right shift (3,5): sequence becomes 4,2,1,3,5
• Right shift (1,3): sequence becomes 1,4,2,3,5
• Left shift (2,4): sequence becomes 1,2,3,4,5

Constraints:

• $n \leq 1000$
• The sequence $a$ is a permutation of $1\sim n$

Scoring: Your score is calculated based on the number of operations $m$:

• If $m \leq 23n$, you receive full score (1.0).
• If $m > 230n$, you receive 0 score.
• Otherwise, Score = max(0.0, 1.0 - (m - 23n) / (230n - 23n)), linearly decreasing from 1.0 to 0.0.

Time limit: 5 seconds

Memory limit: 512 MB