P1467 [USACO2.2] Runaround Numbers

Runaround numbers are positive integers that contain no $0$ and have no repeated digits (for example, $81362$). They must also have the following property: Starting from the leftmost digit (in $\color{red}{8}\color{black}1362$, that digit is $8$), move to the right a number of positions equal to the value of the current digit (wrapping around to the leftmost digit after the rightmost one; in $\color{red}{8}\color{black}1362$, you move $8$ steps). You will land on another new digit (in $\color{red}{8}\color{black}1362$, this is $\color{red}8\color{black}\to 1\to 3\to 6\to 2\to 8\to 1\to 3\to \color{red}6$; if you land on a digit that has already been visited, then the number is not a runaround number). Repeat this process. If you return to the leftmost digit after visiting every digit exactly once, then the integer is a runaround number. Using $81362$ as an example, the following simulation shows that $81362$ is a runaround number: $$\color{red}8\color{black}\to 1\to 3\to 6\to 2\to 8\to 1\to 3\to \color{red}6$$ $$\color{red}6\color{black}\to 2\to 8\to 1\to 3\to 6\to \color{red}2$$ $$\color{red}2\color{black}\to 8\to \color{red}1$$ $$\color{red}1\color{black}\to \color{red}3$$ $$\color{red}3\color{black}\to 6\to 2\to \color{red}8$$ Task: Given a positive integer $m$, find the smallest runaround number $m'$ that is greater than $m$. It is guaranteed that $m' \le 2^{32} - 1$.

A single line containing $m$.

A single line containing the smallest runaround number $m'$ such that $m' > m$.

Constraints: For $100\%$ of the testdata, $1 \le m \le 10^9$. Source: USACO 2.2. Translated by ChatGPT 5