決め方の優先順位
- \(x\)の桁数の max
- 桁数を固定したとき，使う値を大きくする
- 各桁に使う値の multiset を固定したとき，大きい順に並べる
これらを優先順位の通りに求めればよい． 2つ目の条件，桁数を固定したときに使う値を大きくするのは， 9 から降順に貪欲に決めていけばよい．
9から貪欲に決めていく際，binary search でも実装可能． \(i \in [1..9]\) を固定すると，\(i\) を使える個数は 単調であるから．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n; cin >> n;
vll a(9); rep(i,9) { cin >> a[i]; }
ll mi = INFL;
rep(i,9) chmin(mi, a[i]);
ll k = n/mi; // ちょうどk桁
ll rem = n;
string str;
drep(j,k){
drep(i,9){
if(a[i] + mi*j <= rem){
rem -= a[i];
str.push_back(i+1+'0');
break;
}
}
}
cout << str << endl;
return 0;
}
