구글링해도 풀이가 없다.
코포 D번 같은 문제다.. 언제 한번 나와라!
우리는 뒤에서 부터 보는게 무조건 좋다.
즉, $(a,b)$ -> $(c,d)$ 보다는 $(c,d)$ -> $(a,b)$로 접근하자.
왜 그렇게 하냐면, $*2$라는 연산은 아무 제약이 없이 할 수 있지만, $/2$라는 연산은 짝수일때만 가능하기 때문이다.
그러면 이제 다음과 같은 특이한 사실이 성립한다.
현재 c와 d의 홀짝성이 다르다면, -1만 사용해야 한다.
(나누기 2를 사용하려면 둘다 짝수 즉, 둘다 2로 나눈 나머지가 같아야 하고, 빼기 1 연산은 두 개의 홀짝성이 동시에 반전된다.)
둘다 홀수라면, 나눌수 없으므로 항상 -1 해줘 야한다.
짝수라면 2로 나눌수 있으면 나누는게 이득이다.
그 이유는 둘다 -1을 해버리면, 홀수가 되는데, 여기서는 -1하는거 밖에 수가 없다.
즉 -1 -1 을 하는 방법밖에 없는데, 이렇게 되면, -1 -1 /2 를 하는 거보단, /2 -1 을하는게 이득이기 떄문에 항상 나눌 수 있다면 나누는게 이득이다.
그럼 나눌수 있다는건 어떻게 판정할까?
2가지로 판정한다.
결국 우리가 말하고 싶은거는 짝수만 존재할때 /2를 한번이라도 해야 한다면 무조건 앞에서 해야한다는 것인데,
둘의 차이를 보면 쉽게 해결이 가능하다. -1을 하면 차이는 감소하지 않으므로, abs(a-b)와 abs(c-d)가 다르다면 지금 나누는게 이득이다.
a <= c/2 && b<= d/2가 성립하고 abs(a-c)<=abs(b/2-d/2)가 성립해야 한다. (차이는 감소만 하므로)
나눌수 없으면 계속 -1을 해준다.
끝!
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<stack>
#include<map>
#include<set>
#include<deque>
#include<functional>
#include<unordered_map>
#include<list>
#include<cstdlib>
#include<ctime>
//#define double long double
//T.erase(unique(T.begin(),T.end()),T.end());
//written by djs100201
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 3e5 + 100, inf = 1e18, mod = 998244353, sqrtN = 333, p = 27, m_ = 55;
ll dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
ll n, m, k, tc = 1, a, b, c, d, sum, x, y, z, w, base, ans;
ll gcd(ll x, ll y) {
if (!y)return x;
return gcd(y, x % y);
}
void solve() {
cin >> a >> b >> c >> d;
if (a > c || b > d) {
cout << "-1";
return;
}
while (1) {
if (a == c && b == d) {
cout << ans;
return;
}
if (c % 2 != d % 2) {
x = c - a, y = d - b;
if (x != y) cout << "-1";
else cout << ans + x;
return;
}
if (c % 2) {
c--, d--;
ans++;
}
else {
x = abs(a - b), y = abs(c / 2 - d / 2);
if (a <= c / 2 && b <= d / 2 && x <= y) {
c /= 2, d /= 2;
ans++;
}
else {
x = c - a, y = d - b;
if (x != y) cout << "-1";
else cout << ans + x;
return;
}
}
if (a > c || b > d) {
cout << "-1";
return;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
//cin >> tc;
while (tc--)solve();
}