ABC257E - Addition and Multiplication 2

考え方

優先順位は

1. 桁数を増やすこと
2. 大きい位に大きな数字を置くこと

である．

よって，

1. コスト最小の操作を使って桁数をなるべく増やしたものを求め，
2. 上の桁から（予算を超えない限り）なるべく大きな数字で置き換えていく

ことで答えが求まる．

回答例

N = int(input())
C = list(map(int, input().split()))

best_c, best_i = min((c, i + 1) for i, c in enumerate(C))
num = N // best_c
N -= best_c * num

if num > 0:
    x = [best_i] * num
else:
    exit(print(0))

cur = 0
for i in range(8, -1, -1):
    c = C[i]
    while N - (c - best_c) >= 0 and cur < num:
        x[cur] = i + 1
        N -= (c - best_c)
        cur += 1

x = list(map(str, x))
print(''.join(x))