Consider a system with only two colors. To consolidate all balls of the first color onto the first peg, let k represent the quantity of the first color currently on the first peg. Shift the top k elements from the second peg to the third (auxiliary) peg. Sequentially move elements from the first peg: elements matching the first color go to the second peg, while others go to the third peg. Relocate the k elements from the second peg to the first, followed by the remaining elements from the third peg to the first. At this stage, the first peg is perfectly partitioned (non-target on top, target on bottom). Move the non-target elements from the first peg to the third. Finally, distribute the elements from the second peg—target color to the first peg, remainign to the third.

cpp int match_cnt = 0; for (int v : pegs[1]) if (v == 1) match_cnt++; for (int i = 0; i < match_cnt; i++) transfer(2, 3); while (heights[1] > 0) { if (pegs[1].back() == 1) transfer(1, 2); else transfer(1, 3); } for (int i = 0; i < match_cnt; i++) transfer(2, 1); for (int i = 0; i < cap - match_cnt; i++) transfer(3, 1); while (heights[3] > 0) transfer(3, 2); while (heights[1] > 0 && pegs[1].back() == 2) transfer(1, 3); while (heights[2] > 0) { if (pegs[2].back() == 1) transfer(2, 1); else transfer(2, 3); }

Expand the logic to handle n colors by iteratively isolating one color at a time. Designate the target color as 1 and all others as 0. The objective is to gather all 1s into a specific column. This requires two specialized columns: one entirely composed of 0s and one that is complete empty. By logically swapping column indices, we can assign the n-th column as the uniform 0 column and the (n+1)-th as the empty column.

To bring all target elements of a column i to the top, let k be the count of target elements in column i. Move k elements from the uniform column to the empty column. Distribute elements from column i: target elements to the uniform column, non-target to the empty column. Swap column i with the empty column, then swap column i with the uniform column. This operation effectively filters the target elements to the top of column i.

After establishing the uniform and empty columns, apply the elevation procedure to columns x through n-1. Once all target elements in these columns are at the top, move them to the empty column. Swap the empty column with column x. The remaining space in columns x+1 through n can then be filled with the leftover non-target elements from column x.

cpp void isolateColor(int col, int target) { establishUniformColumn(col, target); for (int i = col; i <= num_cols - 1; i++) { int match_cnt = 0; for (int v : pegs[i]) if (v == target) match_cnt++; for (int j = 0; j < match_cnt; j++) transfer(num_cols, num_cols + 1); while (heights[i] > 0) { if (pegs[i].back() == target) transfer(i, num_cols); else transfer(i, num_cols + 1); } swap_logical(i, num_cols + 1); swap_logical(i, num_cols); } for (int i = col; i <= num_cols - 1; i++) { while (heights[i] > 0 && pegs[i].back() == target) transfer(i, num_cols + 1); } swap_logical(num_cols + 1, col); swap_logical(num_cols, num_cols + 1); for (int i = col + 1; i <= num_cols; i++) { while (heights[i] < cap) transfer(num_cols + 1, i); } }

Assume we are building the uniform 0 column on column x. Let k be the number of target elements in column x. Move k elements from the n-th column to the (n+1)-th column. Distribute elements from column x: target to the n-th column, non-target to the (n+1)-th. Move the non-target elements from the (n+1)-th column back to column x. Process column x+1: move non-target elements to column x until it is full, directing any overflow or target elements to the (n+1)-th column. Finally, swap column x with the n-th column, and column x+1 with the (n+1)-th column.

cpp void establishUniformColumn(int col, int target) { int match_cnt = 0; for (int v : pegs[col]) if (v == target) match_cnt++; for (int i = 0; i < match_cnt; i++) transfer(num_cols, num_cols + 1); while (heights[col] > 0) { if (pegs[col].back() == target) transfer(col, num_cols); else transfer(col, num_cols + 1); } for (int i = 0; i < cap - match_cnt; i++) transfer(num_cols + 1, col); while (heights[col + 1] > 0) { if (pegs[col + 1].back() == target || heights[col] == cap) transfer(col + 1, num_cols + 1); else trasnfer(col + 1, col); } swap_logical(col, num_cols); swap_logical(col + 1, num_cols + 1); }

Repeat the consolidation for the first n-2 colors. The remaining two columns are resolved using the base case logic.

cpp #include #include #include

using namespace std;

const int MAX_COLS = 55; const int MAX_CAP = 405;

vector pegs[MAX_COLS]; int heights[MAX_COLS]; int peg_id[MAX_COLS]; int num_cols, cap; vector<pair<int, int>> moves;

void transfer(int src, int dest) { pegs[dest].push_back(pegs[src].back()); pegs[src].pop_back(); heights[dest]++; heights[src]--; moves.push_back({peg_id[src], peg_id[dest]}); }

void swap_logical(int a, int b) { swap(pegs[a], pegs[b]); swap(heights[a], heights[b]); swap(peg_id[a], peg_id[b]); }

void establishUniformColumn(int col, int target) { int match_cnt = 0; for (int v : pegs[col]) if (v == target) match_cnt++; for (int i = 0; i < match_cnt; i++) transfer(num_cols, num_cols + 1); while (heights[col] > 0) { if (pegs[col].back() == target) transfer(col, num_cols); else transfer(col, num_cols + 1); } for (int i = 0; i < cap - match_cnt; i++) transfer(num_cols + 1, col); while (heights[col + 1] > 0) { if (pegs[col + 1].back() == target || heights[col] == cap) transfer(col + 1, num_cols + 1); else transfer(col + 1, col); } swap_logical(col, num_cols); swap_logical(col + 1, num_cols + 1); }

void isolateColor(int col, int target) { establishUniformColumn(col, target); for (int i = col; i <= num_cols - 1; i++) { int match_cnt = 0; for (int v : pegs[i]) if (v == target) match_cnt++; for (int j = 0; j < match_cnt; j++) transfer(num_cols, num_cols + 1); while (heights[i] > 0) { if (pegs[i].back() == target) transfer(i, num_cols); else transfer(i, num_cols + 1); } swap_logical(i, num_cols + 1); swap_logical(i, num_cols); } for (int i = col; i <= num_cols - 1; i++) { while (heights[i] > 0 && pegs[i].back() == target) transfer(i, num_cols + 1); } swap_logical(num_cols + 1, col); swap_logical(num_cols, num_cols + 1); for (int i = col + 1; i <= num_cols; i++) { while (heights[i] < cap) transfer(num_cols + 1, i); } }

int main() { if (!(cin >> num_cols >> cap)) return 0; for (int i = 1; i <= num_cols; i++) { pegs[i].resize(cap); for (int j = 0; j < cap; j++) cin >> pegs[i][j]; heights[i] = cap; peg_id[i] = i; } peg_id[num_cols + 1] = num_cols + 1;

if (num_cols == 2) {
    int match_cnt = 0;
    for (int v : pegs[1]) if (v == 1) match_cnt++;
    for (int i = 0; i < match_cnt; i++) transfer(2, 3);
    while (heights[1] > 0) {
        if (pegs[1].back() == 1) transfer(1, 2);
        else transfer(1, 3);
    }
    for (int i = 0; i < match_cnt; i++) transfer(2, 1);
    for (int i = 0; i < cap - match_cnt; i++) transfer(3, 1);
    while (heights[3] > 0) transfer(3, 2);
    while (heights[1] > 0 && pegs[1].back() == 2) transfer(1, 3);
    while (heights[2] > 0) {
        if (pegs[2].back() == 1) transfer(2, 1);
        else transfer(2, 3);
    }
} else {
    for (int i = 1; i < num_cols - 1; i++) isolateColor(i, i);
    int match_cnt = 0;
    for (int v : pegs[num_cols - 1]) if (v == num_cols - 1) match_cnt++;
    for (int i = 0; i < match_cnt; i++) transfer(num_cols, num_cols + 1);
    while (heights[num_cols - 1] > 0) {
        if (pegs[num_cols - 1].back() == num_cols - 1) transfer(num_cols - 1, num_cols);
        else transfer(num_cols - 1, num_cols + 1);
    }
    for (int i = 0; i < match_cnt; i++) transfer(num_cols, num_cols - 1);
    for (int i = 0; i < cap - match_cnt; i++) transfer(num_cols + 1, num_cols - 1);
    while (heights[num_cols + 1] > 0) transfer(num_cols + 1, num_cols);
    while (heights[num_cols - 1] > 0 && pegs[num_cols - 1].back() == num_cols) transfer(num_cols - 1, num_cols + 1);
    while (heights[num_cols] > 0) {
        if (pegs[num_cols].back() == num_cols - 1) transfer(num_cols, num_cols - 1);
        else transfer(num_cols, num_cols + 1);
    }
}
cout << moves.size() << "\n";
for (auto [src, dest] : moves) cout << src << " " << dest << "\n";
return 0;

}