前の問題の影響で、最初タイトルをMonkeyと読み間違えた。
https://code.google.com/codejam/contest/4244486/dashboard#s=p2
問題
この国にはD種類のコインがあり、それぞれの金額がA[i]とする。
この国では、金銭の支払いに際し1種類のコインは最大C枚までしか使えない。
これらのコインで、1~Vのすべての金額を1刻みで支払えるようにしたいが、これらのコインでは不足するかもしれない。
Cは増やすことができないので、コインの種類を増やして対応することにした。
増やさなければならない最小のコインの種類の数を答えよ。
解法
現在のコインで支払えない最小の額が存在する場合、その額のコインを増やせばよい。
A[1]~A[D]のうちA[1]~A[x]で払える金額の最大値はC*(A[1]+...+A[x])である。
この最大値がA[x+1]-1未満である場合、C*(A[1]+...+A[x])とA[x+1]の間に払えない金額が存在するので、C*(A[1]+...+A[x])+1の金額のコインを足していけば良い。
以下のコードでは、以下の工夫をしている。
- 金額1のコインは無条件に追加
- 金額(V+1)のコインを番兵代わりに追加
ll C,D,V; vector<int> P; void solve(int _loop) { int f,i,j,k,l,x,y; cin>>C>>D>>V; P.clear(); FOR(i,D) cin>>x, P.push_back(x); if(P[0]!=1) P.push_back(1); P.push_back(V+1); while(1) { sort(ALL(P)); ll tot=0; FOR(x,P.size()-1) { tot += P[x]*C; if(tot+1<P[x+1]) break; } if(tot+1>V) break; P.push_back(tot+1); } _P("Case #%d: %d\n",_loop,P.size()-D-1); }
まとめ
面白い問題でした。