不参加でした。出てたら解けてたかなぁ…。
https://community.topcoder.com/stat?c=problem_statement&pm=15439
問題
コインの種類が標準で1,2,5,10,20,50,100,200,500,1000,2000,5000,10000,20000,50000があるとする。
ここに1種類追加でNの価値のコインが追加されたとしよう。
金額Aをちょうど支払うのに最小何枚のコインが必要か。
Aは2*10^9以下とする。
解法
元のコイン群だけを使う場合、貪欲に高いコインを優先的に使うのが良いので、必要コイン数は容易にわかる。
価値Nのコインを50000枚以上使うことはないので、Aのコインの使用量を0~50000で総当たりしよう。
Nが50000以下なら、このコインを50000枚使うなら価値50000のコインをN枚使った方がよい。
また、Nが50000以上ならA/Nは40000以下なので、やっぱり50000枚以上使うことはない。
class NewBanknote { public: int how(int a) { int ret=0; vector<int> V={50000,20000,10000,5000,2000,1000,500,200,100,50,20,10,5,2,1}; FORR(v,V) ret+=a/v, a%=v; return ret; } int hoge(int N,int A) { int mi=1<<30; int i; FOR(i,50000) if(1LL*N*i<=A) mi=min(mi,i+how(A-N*i)); return mi; } vector <int> fewestPieces(int newBanknote, vector <int> amountsToPay) { vector<int> R; FORR(a,amountsToPay) R.push_back(hoge(newBanknote,a)); return R; } }
まとめ
実際こんな最小から最高まで50000倍も異なるコイン・紙幣使う国ってあるのかね?