SRM450 Div1 Medium

500

10^12 とか 10^6 程度でどうこうできるだろうと見切り発車して後悔。意外と難敵。

ある工場か従業員を雇うなら可能な限り多く一度に増やすべき。
増やせない場合は、増やせるターンまで飛ばす。
それとは別に、これ以上増やさずにいったとして何ターンかかるかも計算しておく。

オーバーフローとか怖い。
もっと綺麗に実装できそう。

class StrongEconomy {
public:
  long long earn(lli n, lli k, lli price, lli target)
  {
    lli ret = target;
    lli gold = 0;
    lli turn = 0;
    while (true) {
      ++turn;
      unless (n < k) swap(n, k);
      const lli income = n * k;
      if(k > target / n) {
        ret = min(ret, turn);
        break;
      }
      { // 
        lli rest = target - gold;
        ret = min(ret, (rest / income) + (bool)(rest % income) + turn - 1);
      }
      lli prev = gold;
      gold += income;
      if (gold < prev || target <= gold) {
        ret = min(ret, turn);
        break;
      }
      if (price <= gold) {
        lli diff = k - n;
        lli add = gold / price;
        gold %= price;
        if (add < diff) {
          n += add;
        } else {
          n += diff;
          add -= diff;
          lli a = add / 2;
          lli b = add - a;
          n += b;
          k += a;
        }
      } else {
        lli next = max(0LL, ((price - gold) / income) - 2);
        gold += next * income;
        turn += next;
      }
    }
    return ret;
  }
};