Intermediate.
Put your skills to the test.

Problem summary

Chute 1 starts with gifts 1…N. Operation 1 moves its rightmost gift to chute 2’s left; 2 moves chute 2’s leftmost gift to chute 3’s right; 3 moves chute 2’s leftmost gift back to chute 1’s right. Produce the requested final permutation using the fewest operations.

Constraints

1 ≤ N ≤ 30.

Worked example

Input and output for the worked example discussed below.

4
1 4 2 3

111123321122

Solution analysis

1. Concatenate chute 1 and chute 2, both left to right. Transfers only move the boundary between them; they never change the relative order of remaining gifts. Operation 2 removes the first gift immediately right of that boundary.
2. Maintain the remaining ordered list and boundary index. To output the next gift at index p, move the boundary to p: operation 1 moves it left, operation 3 moves it right. Then use operation 2 and erase the gift.
3. For target [1,4,2,3], move left four times and output 1: 11112. Move right twice and output 4: 332. Move left twice and output 2: 112. Finally output 3: 2. Concatenation gives the displayed optimal sequence.

Why it works

Before each output, relative order is fixed. The boundary must reach exactly the next gift’s index, and each transfer changes its index by only one. Thus every solution needs at least the absolute displacement plus one output operation. The construction meets this lower bound at every stage, proving total optimality.

Watch out. Chute 2 is not a FIFO queue. Output operation digits, not gift labels. Reversing individual blocks would violate the permitted moves.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
using namespace std;
int main(){
    int count;
    cin>>count;
    vector<int>remaining(count);
    iota(remaining.begin(),remaining.end(),1);
    int boundary=count;
    string operations;
    for(int index=0;index<count;index++){
        int wanted;
        cin>>wanted;
        int position=find(remaining.begin(),remaining.end(),wanted)-remaining.begin();
        // Transfers preserve order and only shift the boundary.
        while(boundary>position){
            operations+='1';
            boundary--;
        }
        while(boundary<position){
            operations+='3';
            boundary++;
        }
        operations+='2';
        remaining.erase(remaining.begin()+position);
    }
    cout<<operations<<'\n';
}