Intermediate.
Put your skills to the test.

Problem summary

Transform each maximal run of digit d, of length c, into the two digits max(c,d), d. Starting with S as state 0, find state n. For example, 222999 becomes 3299.

Source clarification. The official Conway editorial reports early eventual periods 1 or 2 from observation; the implementation detects the cycle rather than assuming a fixed simulation limit. Editorial: https://infos.infosbg.com/files/Contests/ETI/2024/D/analyses/D2_conway_analysis.pdf

Constraints

1 ≤ |S| ≤ 1000000; each initial run has length at most 9; 0 ≤ n ≤ 10000000; memory limit 32 MB.

Worked example

Original statement sample.

21 9

333211

Solution analysis

1. Scan a string by maximal runs. For a run [left,right), its count is right−left; append the digit max(count, digit) and then the original digit. Process the whole old string before using the new one. This is a simultaneous transformation, not an in-place rewrite.
2. The official editorial reports that valid inputs soon reach a fixed point or a two-state cycle (observed by its ninth state). Instead of hardcoding a step bound, keep only the previous and current strings, calculate next, and detect next=current or next=previous. Once either equality holds, determinism guarantees that every future state repeats with the detected period.
3. For S=21, the states are 21 → 2211 → 2221 → 3211 → 332221 → 333211 → 332221. States 4 and 6 agree, so all remaining steps can be skipped by parity. State 9 is 333211. No table of millions of states is stored.

Why it works

The run scan implements exactly the stated rule. If next=current, applying the same deterministic function will keep the string unchanged. If next=previous, the two stored states alternate forever; the remaining step parity therefore selects the exact answer. Even before a repetition is found, each explicitly simulated state is correct by induction. The fast termination bound is the official editorial’s reported property, not a general property of arbitrary string-rewrite systems.

Watch out. Do not use the usual look-and-say count alone: the first digit is max(count,d). State numbering begins at zero. Do not retain every state. The initial run-length bound is important for the two-digit rule.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<string>
#include<utility>
using namespace std;
string transform(const string&text){
    string result;
    result.reserve(text.size()*2);
    for(size_t left=0;left<text.size();){
        size_t right=left+1;
        while(right<text.size()&&text[right]==text[left]){
            right++;
        }
        int digit=text[left]-'0';
        int count=static_cast<int>(right-left);
        result.push_back(static_cast<char>('0'+max(count,digit)));
        result.push_back(text[left]);
        left=right;
    }
    return result;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string current;
    int steps;
    cin>>current>>steps;
    string previous;
    int completed=0;
    while(completed<steps){
        string next=transform(current);
        if(next==current){
            break;
        }
        if(completed>0&&next==previous){
            // current is state completed; next is the other cycle state.
            if((steps-completed)%2==1){
                current=move(next);
            }
            break;
        }
        previous=move(current);
        current=move(next);
        completed++;
    }
    cout<<current<<'\n';
}