日鉄ソリューションズプログラミングコンテスト2022(AtCoder Beginner Contest 257) E - Addition and Multiplication 2 (500)
操作回数を増やして桁数を増やすのが最も重要なので最小のコストの操作を行った場合に何桁になるかを求める
同じコストのが複数ある場合は一番大きい数のを選ぶことにする
$ nから全て最小コストで操作を行ったときの残りコストを余りとする
上の桁から次のように繰り返す
余りがある場合、$ 9,8,...,1の順により大きい数でその桁を置換できるか試し、できるなら置換
余りがその数字のコスト以上なら可能
上の桁からやるのは上の桁が大きい方が当然大きい数になるため
余りがないか、より大きい数で置換するのが不可能なら元の選んだ数を使う
最大で$ 10^6桁になるので少なくてもC++の整数型では表せない