Generate 2024-like Number

2 secs 1024 MB
loop0919's icon loop0919
Tweet
Problem
Submissions
Test cases
Editorial

解説（全列挙をする解法）

実は、101510^{15} 以下の 2024-like Number は高々 817189817189 個しかないため、適切な方法で昇順に全列挙することで十分間に合います。

例えば、DFS などを用いて、各桁の数の和が 99 以下である 101410^{14} 以下の正整数を昇順に生成し、 最後に KK 番目に小さい各桁の数の和が 99 以下の数を 1010 倍し、各桁の数の和を足すことで求めることができます。

解説 (桁DPと二分探索を行う解法)

まず、以下の補題を考えます。

  • 11 以上 NN 以下の整数のうち、各桁の総和が 99 以下である整数は KK 個以上ある整数 NN の最小値 min⁡N\min N を求めよ。

そしてその補題は、11 以上 NN 以下の整数のうち、各桁の総和が 99 以下である整数の個数を桁DPで求めた後に、 それが KK 個以上かどうかで 11 以上 101410^{14} 以下の範囲で二分探索を行うことで求めることができます。

そして、求めたい KK 番目に小さい 2024-like Number は、min⁡N\min N を 1010 倍し、 min⁡N\min N の各桁の和を足すことで求めることができます。