最終的な \(x\) の桁数を考えると、桁数が大きいほど \(x\) が大きいことから桁数を最大化する必要があることがわかります。

桁数の最大値は \(\lfloor \frac{N}{\mathrm{min}(C)}\rfloor\) で求まります。

桁数が定まると辞書順の比較となるため、後は先頭から貪欲に値を決めていけば良いです。適切な実装により \(\mathrm{Ο}(N)\) でこの問題を解くことができます。詳しくは実装例をご覧ください。

実装例(c++):

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<int> c(10);
    for(int i = 1; i <= 9; i++) cin >> c[i];

    int mn = *min_element(c.begin() + 1, c.end());
    int length = n / mn;

    string ans = "";

    for(int i = 0; i < length; i++) {
        for(int j = 9; j >= 1; j--) {
            if((ll)mn * (length - 1 - i) + c[j] <= n) {
                n -= c[j];
                ans.push_back((char)('0' + j));
                break;
            }
        }
    }

    cout << ans << endl;

    return 0;
}