SRM553Div2
Easy
全通り試す。TLEするかもしれないので一番内側にbreak仕込んどく。
class PlatypusDuckAndBeaver { public: int minimumAnimals(int WF, int DB, int BT) { REP(p,1001)REP(b,1001)REP(d,1001){ long long wf = 2*d + 4*b + 4*p; long long db = d + p; long long bt = b + p; if( wf > WF || bt > BT || db > DB )break; if( wf == WF && bt == BT && db == DB )return p+b+d; } }
Medium
二分探索しなくてもO(1)で求めれるらしい。オーバーフローに注意。
class Suminator { public: long long calc( vector<int> in , long long k ) { REP(i,in.size()) { if( in[i] == -1 ) { in[i] = k; } } stack< long long > stk; REP(i,60) { stk.push(0); } REP(i,in.size()) { if(in[i] == 0){ long long a = stk.top();stk.pop(); long long b = stk.top();stk.pop(); stk.push( a + b ); } else{ stk.push(in[i]); } } return stk.top(); } long long findMissing(vector <int> program, int r) { long long result=-1; long long ub = 9223372036854775807LL; long long lb = 0LL; if( calc(program,0) == r )return 0; while( ub-lb > 1 ) { long long md = ( ub - lb ) / 2LL + lb; long long res = calc(program,md); if( res == r )return md; if( res < r )lb = md; if( res > r )ub = md; } return result; }