AcWing 1173. 跳跳棋
原题链接
中等
作者:
ZTEG
,
2020-08-17 14:27:04
,
所有人可见
,
阅读 1139
#include<bits/stdc++.h>
using namespace std;
struct oppo{
long long a[5];
long long deep;
bool operator==(const oppo x)
{
if(a[1]==x.a[1]&&a[2]==x.a[2]&&a[3]==x.a[3])
return 1;
return 0;
}
}a,b;
long long ans;
oppo find(oppo a)
{
long long l1,l2,x;
while(1)
{
l1=a.a[2]-a.a[1];l2=a.a[3]-a.a[2];
if(l1>l2)
{
x=l1/l2;
if(!(l1%l2))
x--;
a.deep+=x;
a.a[2]-=x*l2;
a.a[3]-=x*l2;
}
else if(l2>l1)
{
x=l2/l1;
if(!(l2%l1))
x--;
a.deep+=x;
a.a[1]+=x*l1;
a.a[2]+=x*l1;
}
else
break;
}
return a;
}
oppo up(oppo a,long long f)
{
long long l1,l2,x;
a.deep=0;
while(f)
{
l1=a.a[2]-a.a[1];l2=a.a[3]-a.a[2];
if(l1>l2)
{
x=l1/l2;
if(!(l1%l2))
x--;
if(x>f)
x=f;
a.a[2]-=x*l2;
a.a[3]-=x*l2;
f-=x;
}
else if(l2>l1)
{
x=l2/l1;
if(!(l2%l1))
x--;
if(x>f)
x=f;
a.a[1]+=x*l1;
a.a[2]+=x*l1;
f-=x;
}
else
break;
}
if(f)
a.a[1]=a.a[2]=a.a[3]=-1;
return a;
}
void GG(oppo a,oppo b)
{
if(a.deep<b.deep)
swap(a,b);
ans+=a.deep-b.deep;
a=up(a,a.deep-b.deep);
if(a==b)
return;
for(long long i=1<<30;i>0;i>>=1)
{
oppo x=up(a,i);
oppo y=up(b,i);
if(!(x==y))
{
ans+=2*i;
a=x;
b=y;
}
}
ans+=2;
return;
}
int main()
{
cin>>a.a[1]>>a.a[2]>>a.a[3];
cin>>b.a[1]>>b.a[2]>>b.a[3];
a.deep=0;b.deep=0;
sort(a.a+1,a.a+4);
sort(b.a+1,b.a+4);
if(find(a)==find(b))
cout<<"YES"<<endl;
else
{
cout<<"NO"<<endl;
return 0;
}
a.deep=find(a).deep;
b.deep=find(b).deep;
GG(a,b);
cout<<ans<<endl;
return 0;
}