1135

解説

制約より1135数の個数は$10^6$以下であるため、1135数を全列挙することを考えます。簡単のため、1の位を排除して考えることにします。 1135数の10の位以降の数字は、各桁の数字を $d_i(1 \leq i \leq k , 1 \leq d_i)$ として、$\displaystyle \sum_{i=1}^{k} d_i \leq 9$ となり、このことから $k \leq 9$ つまり、1135数の10の位以降の数字は高々9桁であることが分かります。 では、具体的な $d_i$ の値の構築を考えてみましょう。ここで、$\displaystyle \sum_{i=1}^{k} d_i = c$ $(1 \leq c \leq 9)$と分解して考えてみます。 このときの$d_i$ の値は、「 $c$ 個のボールを$k-1$個の仕切りで $k$ 個の区別のある空間に(各空間に必ず1つ以上のボールがあるという条件の下で)区切ったときの各空間にあるボールの数」に等しいと考えることができます。 例えば$c=4$のとき、$d = (1,3)$は　o|ooo 、$d = (1,2,1)$は　o|oo|o 、といった具合に表すことができます。仕切りの入れ方はそれぞれのボールの間に仕切りを入れるか、入れないかを全探索することで求めることができ、$c=i$ のとき $(2^{i-1})$通りあります。これを全ての$c=i(1 \leq i \leq 9)$について調べることで1135数を全て列挙することができます。1135数を全列挙するのにかかる時間計算量は$O(\displaystyle \sum_{i=1}^{k} i \times 2^{i-1}) = O(k \times 2^k)$であり、$k \leq 9$ より1135数を全列挙しても余裕をもって実行時間制限に間に合います。あとは列挙した1135数を小さい順にソートした上で$N$番目の1135数を出力すればよいです。よって、この問題を解くことができました。

ex.

1135数の総数は $\displaystyle \sum_{i=1}^{9} 2^{i-1} = 511$ です。