TopCoder SRM 677 Div1 Easy: DoubleOrOneEasy

解法

全探索

コード

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>

using namespace std;
typedef long long ll;

class DoubleOrOneEasy {
 public:
  int minimalSteps(int a, int b, int newA, int newB) {
    int ans = 1000000000;
    for (int i = 0; i < 30; ++i) {
      ll da = newA - (ll)a * (1LL << i);
      ll db = newB - (ll)b * (1LL << i);
      if (da != db) continue;
      if (da < 0) continue;
      int cnt = i;
      for (int j = i; j >= 0; --j) {
        int c = da / (1LL << j);
        cnt += c;
        da -= (1LL << j) * c;
      }
      ans = min(ans, cnt);
    }
    if (ans == 1000000000) return -1;
    return ans;
  }
};