题目

题目背景

原《奇怪的字符串》请前往 P2543

题目描述

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。

我们用跳跳棋来做一个简单的游戏：棋盘上有3颗棋子，分别在a，b，c这三个位置。我们要通过最少的跳动把他们的位置移动成x，y，z。（棋子是没有区别的）

跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过1颗棋子。

写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。

输入格式

第一行包含三个整数，表示当前棋子的位置a b c。（互不相同）

第二行包含三个整数，表示目标位置x y z。（互不相同）

输出格式

如果无解，输出一行NO。

如果可以到达，第一行输出YES，第二行输出最少步数。

输入输出样例

输入 #1 
1 2 3
0 3 5
输出 #1 
YES
2

说明/提示

20% 输入整数的绝对值均不超过10

40% 输入整数的绝对值均不超过10000

100% 绝对值不超过10^9 
#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;
}