чемпионаты Спб: Чемпионат СПБ 2008

В математике часто встречаются так называемые рекуррентные соотношения. Обычно они применяются для задания числовых последовательностей - очередное число в последовательности некоторым образом выражается через предыдущие. Примером такой последовательности являются числа Фибоначчи (в них очередное число равно сумме двух предыдущих).

С помощью соотношений такого типа можно задавать не только последовательности чисел, но и последовательности строк. В этой задаче рассматривается последовательность строк \(s_0, \ s_1, \ldots\) , задаваемая следующим образом.

Строка \(s_0\) пуста, а каждая строка \(s_i\) (\(i \ge 1\)) получается из \(s_{i-1}\) по следующему правилу: если десятичная запись числа \(i\) входит как подстрока в \(s_{i-1}\), то \(s_i = s_{i-1}\), иначе \(s_i\) получается приписыванием к \(s_{i-1}\) в конец десятичной записи числа \(i\).

Задано число \(n\). Необходимо найти строку \(s_n\).