Aはすんなり解けた。変数名間違えて1WAしたけど。
http://codeforces.com/contest/487/problem/A
問題
自分と相手それぞれヒットポイントH、攻撃力A、守備力Dが与えられる。
1ターンごとに、互いに(自分の攻撃力-相手の守備力)分のダメージを相手に与え、その分相手のHPを減少させることができる。
先にHPが0以下になったら負けである。
逆に勝利条件とは、あるターンで自分のHPが残っており、相手のHPが0以下であることである。
ここで、プレイヤーはそれぞれh,a,dのお金を払ってH,A,Dのパラメータを1上げることができる。
相手に勝利するために必要なパラメータを得るための最小費用を答えよ。
解法
H,A,Dは最大でも100以下である。
よってAを200上昇すれば1ターンで確実に相手に勝てるし、Dを100上昇すれば相手からのダメージが0になり負けることはなくなる。
一方、Hは数千上昇しないといけない場合もある。
よってA,Dの上昇量を総当たりし、そこからHの必要上昇量を求めてコストの最小値を求める。
まずAの上昇量が決まると、相手を倒せるターン数tが求まる。
ターン数tが求まれば、1ターンあたりの被ダメージをaとしてHPがt*a+1以上になるようにすればよい。
int H[2],A[2],D[2]; int h,a,d; void solve() { int i,j,k,l,r,x,y; string s; cin>>H[0]>>A[0]>>D[0]; cin>>H[1]>>A[1]>>D[1]; cin>>h>>a>>d; int mi=1<<29; FOR(x,201) FOR(y,201) { int at=A[0]+x-D[1]; int dm=A[1]-(D[0]+y); if(at<=0) continue; if(dm<=0) mi=min(mi,x*a+y*d); else { int mt=(H[1]+at-1)/at; int nh=mt*dm+1; mi=min(mi,x*a+y*d+h*max(0,nh-H[0])); } } cout<<mi<<endl; }
まとめ
Hの上限を見誤って計算範囲を間違えた人が続出していた。