略称の \(1\) 文字目に注目すると、これはカーソル \(1\) の位置によって決まり、更新ボタンによるカーソルの移動先は現在のカーソルの位置によってのみ決まります。カーソルの位置は有限通りしか存在しないので、略称の \(1\) 文字目はある年以降で周期的に変化します。（このことは functional graph 上の移動を考えるとわかりやすいです。）

他の文字に対しても同様に考えることで、十分大きな整数 \(Y\) に対して、今から \(Y\) 年後以降の略称は周期的に変化することがわかります。この周期を \(T\) とします。

略称が TTPC となる最後の年が存在するかは、周期の中に略称が TTPC となる年が存在するかと同値です。そこで次のような解法が考えられます。

• 今から \(Y\) 年後までのマシーンの動きをシミュレーションし、最後に略称が TTPC となった年 \(\text{Ans}\) を記録する。
• さらに \(T\) 年後までシミュレーションし、この際に TTPC となる年が存在したら NeverEnds と出力する。
• そうでなければ、 \(\text{Ans}\) を出力する。

\(Y,T\) を大きく見積もってもこの解法は正当です。そこで、 \(Y,T\) の値の大きさを見積りましょう。まず、 \(N\) 年後にはすべての文字が周期的になっているので \(Y\le N\) です。次に \(1\) 文字分の周期は高々 \(N\) なので　\(T\le N^4\) と評価できます。実装の際は単に \(Y=N, T=N^4\) とすればよいです。

したがって、以上の解法は \(O(N^4)\) 時間で動作します。

定数倍の改善ですが、 \(T\le (N/4)^4\) と評価することもできて、本問題を \(N\le 200\) などの制約で解くことも可能です。

この評価は、 functional graph に沿って移動する \(4\) 点の周期が、各点の周期の最小公倍数になることを考えると得られます。同じ連結成分内の \(2\) 点は同じ周期を持つので、最小公倍数を増やすことに寄与できません。したがって、 \(4\) 点は別々の連結成分に属しているとして良いです。それらの連結成分の大きさを \(S_1,S_2,S_3,S_4\) とすると、 \(S_1+S_2+S_3+S_4 \le N\) の制約下で \(\mathrm{lcm}(S_1,S_2,S_3,S_4)\) を上から評価すれば良く、最小公倍数を総積で、総積を相加相乗平均の不等式などで評価すると \(\mathrm{lcm}(S_1,S_2,S_3,S_4)\le S_1S_2S_3S_4\le (N/4)^4\) を得ることができます。

さらに、各文字について周期を検出することで、 TTPC2023 L - Next TTPC 3 に帰着することも可能です。この場合の時間計算量は \(O(N^2\log N)\) 程度です。