题目描述

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

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

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

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

输入输出格式

输入格式：

 

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

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

 

输出格式：

 

如果无解，输出一行NO。

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

 

输入输出样例

输入样例#1： 

1 2 30 3 5

输出样例#1： 

YES2

说明

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

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

100% 绝对值不超过10^9

 

 

    非常有趣的一道题目。

    可以发现只有唯一的一种方案向里跳，并且一直这样跳最后总会达到一种再也不能向里跳的状态。

    于是我们就可以把向里跳看成在树上向父亲走，而最后b-a = c-b 的状态就是根节点。

 

    首先如果两个状态的树根不一样，无解；否则就是一个求LCA的问题了，直接倍增即可。

 

/*    向前跳:  a[1] -= a[2]  (须满足 a[1] > a[2])	向后跳： a[2] -= a[1] , a[0] += a[1] (须满足 a[1] < a[2])	a[1] == a[2] 就不能跳了 */#include
     
      #define ll long longusing namespace std;struct node{    int x,y,z;    bool operator !=(const node &u)const{    	return x!=u.x||y!=u.y||z!=u.z;	}}A,B;	int a[3],b[3];unsigned int ans;node getroot(node x){	if(x.y==x.z) return x;		if(x.y>x.z) return getroot((node){x.x,(x.y-1)%x.z+1,x.z});		else{		int o=(x.z-1)/x.y;		x.x+=o*x.y,x.z-=o*x.y;		return getroot(x);	}}int getdeep(node x){	if(x.y==x.z) return 0;		if(x.y>x.z){		int o=(x.y-1)/x.z;		x.y-=o*x.z;		return getdeep(x)+o;	}		else{		int o=(x.z-1)/x.y;		x.x+=o*x.y,x.z-=o*x.y;		return getdeep(x)+o;	}	}node getnode(node x,int lef){	if(x.y==x.z) return x;		if(x.y>x.z){		int o=(x.y-1)/x.z;				if(o>=lef) return (node){x.x,x.y-lef*x.z,x.z};				x.y-=o*x.z;		return getnode(x,lef-o);	}		else{		int o=(x.z-1)/x.y;				if(o>=lef) return (node){x.x+lef*x.y,x.y,x.z-lef*x.y};				x.x+=o*x.y,x.z-=o*x.y;		return getnode(x,lef-o);	}		}inline void solve(){	int da=getdeep(A),db=getdeep(B);	if(da
      
       db) A=getnode(A,da-db);		ans=da-db;		if(!(A!=B)) return;		for(int i=log(db)/log(2)+1;i>=0;i--) if((1<
       
        <=db){		node AA=getnode(A,1<