SRM450Div2

250

class StrangeComputer {
public:
  int setMemory(string s) {
    string t(s.size(), '0');
    int ret = 0;
    for(int i=0; i<t.size(); ++i){
      if( t[i] != s[i] ){
        ++ret;
        for(int j=i; j<t.size(); ++j){
          t[j] = '0' + (t[j] == '0');
        }
      }
    }
    return ret;
  }
};

500

int nim(vector<int> v)
{
  if( v.size() == 1 )return 0;
  int heap = v[0];
  v.erase( v.begin() );
  return heap == 1 ? nim(v) ^ 1 : 0;
}

class OrderedNim {
public:
  string winner(vector <int> v) {
    const string A = "Alice";
    const string B = "Bob";

    return nim(v) ? B : A;
  }
};

1000
悩んだ。

const int inf = 1 << 24;

pair<int, int> sim(int units, int hp, int att, int num)
{
  int sum = hp * num;
  int cnt = 0;
  while( 0 < units ){
    ++cnt;
    sum -= units;
    num = sum / hp + (0 < sum % hp);
    if( num <= 0 )return make_pair(cnt, 0);
    units -= att * num;
  }
  return make_pair(inf, num);
}

class EnemyTowers {
public:
  int attack(int myUnits, int hpT, int attackT, int numWodT, int numStoT) {

    int s = 0;
    int b = myUnits;

    int ret = inf;
    while( s + 1 < b ){
      int c = (s + b) / 2;
      pair<int, int> wood  = sim(c, hpT, attackT, numWodT);
      pair<int, int> stone = sim(myUnits - c, hpT, attackT, numStoT);

      ret = min( ret, max(wood.first, stone.first) );
      if( stone < wood )s = c;
      else b = c;
    }

    return ret == inf ? -1 : ret;
  }
};