SRM677 div1 easy DoubleOrOneEasy

考えたこと

• 2倍の回数はlogオーダーになるので大した回数にならない
• 3回2倍するとき a +x[0] *2 +x[1] *2 +x[2] *2 + x[3]
• 8a + 8x[0] + 4x[1] + 2x[2] + x[3] = newA になるようなxを見つける
• 最小回数なら2進法みたいな感じで貪欲にやれば求まる

適当な実装の結果long longでオーバーフローさせて落とした…

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class DoubleOrOneEasy {
   public:
   int minimalSteps(int a, int b, int newA, int newB)
  {
    if(newA < a || newB < b) return -1;

    ll ans = LLINF;
    REP(i, 31) {
      ll p = 1LL<<i;
      ll diff = newA - a*p;
      if(diff < 0 || newB-b*p < 0 || diff != newB - b*p) continue;
      ll ret = i;
      for(ll j = i; j>=0; --j) {
        ll tmp = diff / (1LL<<j);
        diff %= (1LL<<j);
        ret += tmp;
      }
      chmin(ans, ret);
    }

    if(ans == LLINF) return -1;
    return ans;
  }
};