Codeforces 487A : Fight the Monster
問題リンク : Problem - A - Codeforces
問題概要 :
君はモンスターと戦っている
君の攻撃力はATKy,守備力はDEFy,体力はHPy
モンスターの攻撃力はATKm,守備力はDEFm,体力はHPm
1ターンに君の体力はmax(0,ATKm-DEFy)減り、モンスターの体力はmax(0,ATKy-DEFm)減る
戦闘が始まる前に魔法を使って体力、守備力、攻撃力を上げることができる
ただし、それぞれを1上げるためにはそれぞれh,d,aのコストがかかる
自分の体力が0より大きく、モンスターの体力が0以下になれば勝利である
君が勝利するために必要なコストの最小値をもとめよ
制約 :
入力はすべて1以上100以下
解法:
入力は全て1以上100以下なので
攻撃力は多くても200までしか上げなくてよい
200上げると君の攻撃力は少なくとも201になるのでモンスターの守備力が最大でも100なので1ターンで倒せる
守備力についても100上げれば君の守備力は101になりモンスターから一切ダメージを受けなくなる
体力については、攻撃力と守備力さえ決まれば後何ターン必要か分かる
つまり、攻撃力と守備力を全て試せば良い
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; int main(){ int HPy,ATKy,DEFy,HPm,ATKm,DEFm,h,a,d; cin >> HPy >> ATKy >> DEFy; cin >> HPm >> ATKm >> DEFm; cin >> h >> a >> d; int mini = INT_MAX; rep(da,201){ rep(dd,101){ int atk = ATKy + da; int def = DEFy + dd; if( atk <= DEFm ) continue; int time1 = ceil( (double)HPm / (double)( atk - DEFm ) ); int HP = HPy - ( ATKm - def ) * time1; if( HP > 0 ) { mini = min(mini,da*a+dd*d); } else { int need_time = ( ATKm - def ) * time1 - HPy + 1; mini = min(mini,da*a+dd*d+need_time*h); } } } cout << mini << endl; return 0; }