TopCoder SRM677(Div.1) Easy DoubleOrOneEasy

Posted on By 二价氢

题目大意

给定两个数,每次可以对两个数同时进行以下操作之一:

  1. 将两个数都加上1
  2. 将两个数都乘上2

问能否经过若干次操作,使两个数同时等于,求最小的操作次数,或不可能完成。

解法

考虑一个数的情形,可以算出,假如我们进行了次乘二操作完成,则有:

可以发现,如果题目的要求可以实现,那么,使得,同时,

枚举,通过二进制可以知道,,于是可以贪心的算出答案.

Code

class DoubleOrOneEasy {
public:
	int minimalSteps(int _a, int _b, int _newA, int _newB) {
		long long a(_a), b(_b), newA(_newA), newB(_newB);
		int ans = 0x7fffffff;
		int cnt = 0;
		while (a <= newA && b <= newB) {
			if (newA - a == newB - b) {
				int tmp = 0;
				long long rem = newA - a;
				for (int i = cnt; i >= 0; i--) {
					tmp += (rem >> i);
					rem &= ((1 << i) - 1);
				}
				ans = min(ans, tmp + cnt);
			}
			a *= 2;
			b *= 2;
			cnt++;
		}
		return ans == 0x7fffffff ? -1 : ans;
	}
};

Level Upper 2016 - TopCoder 250 : 4 / 5