177より難しかったし、しょうがないよね…。
http://yukicoder.me/problems/457
問題
A円の切手とB円の切手が無限枚ある。
これらの切手を用いて、合計T円以上を払う払い方のうち、最小金額を求めよ。
解法
まずは自分の解法を紹介。
B円切手をy枚使うとすると、T円以上払うにはA円切手は最低枚使うことになる。
よって払う金額はとなる。
あとはyを0から順に総当たりして上記式の最小値を求めていき、B*yがTに到達するか、もしくはyがAに到達した時点で探索を打ち切る。
B円切手A枚以上の探索が不要なのは、B円切手A枚はA円切手B枚で置き換えられるので、結局B円切手を(y-A)枚使う場合と同じ総額になるためである。
探索回数はなので、最大ケースでの時O(√T)の計算量となる。
Writer解は別方法のようだ。
非負整数x,yを用いて、の形での任意の数値を表現できる(らしい)。
よってなら、Tをの形になるよう、Tをの倍数まで繰り上げればよい。
ならyを0~A/GCD(A,B)もしくはB*yがTを超えるまで総当たりすればよい。
こちらのループ回数はとなる。
LCM(A,B)に対してTが大きい場合はこちらの解法が有効であるが、今回はそうでもないのでどちらでも良い。
void solve() { ll A,B,T; cin>>A>>B>>T; ll mi=1LL<<60; for(ll y=0; y*B <= T+B && y<=A; y++) mi=min(mi, y*B+ (T-y*B+A-1)/A*A); cout<<mi<<endl; }
解法
時々★2で侮れない問題が出てきて怖い。