题目描述

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的

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

子是没有区别的）跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只

允许跳过1颗棋子。

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

输入

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

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

输出

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

样例输入

1 2 3

0 3 5

样例输出

YES

2

【范围】

100% 绝对值不超过10^9

 

思维神题。

考虑对于当前状态的a,b,c有哪些可移动方案，设d1=b-a,d2=c-b，如果d1!=d2，那么b可以向两边跳，d1,d2其中小的那个可以向中间跳；如果d1=d2那么只能由b向两边跳。

可移动方案最多只有三种，那么可以将每个状态看成一个点，往左右跳看作这个点的左右子节点，往中间跳看作是这个点的父节点，如果不能往中间跳，那这个点就是根节点。

那么所有状态就变成了一个二叉树森林，判断能否完成就变成了判断两个状态是否在同一棵树中，而最小步数自然就是两点间的距离了。

但如果将所有状态都枚举出来显然不行，例如下面这个样例：

1 2 1e9

1e9-1 1e9-2 1e9

要跳1e9级别这么多次，显然不能暴力跳。

那么再回到求答案的那一步，两点间的距离不就是lca分别和两点深度差的和吗！

而深度就是每个点跳到根节点的步数。

那么两点往上跳在原题中就是两边的点往中间跳。

因为跳的点和被跳的点之间的相对距离不变，那么就相当于将两个点都平移了两点间距离这么多。

假设d1>d2，那么c最多向左平移(d1-1)/d2次(因为不能跳到同一个点)。

对于d1和d2，我们可以像求gcd一样辗转相除来求得在二叉树上给出的这两点的深度，然后将深度深的点往上跳使两点深度相同。

接下来只要找到深度相同的这两个点的lca就好了，可以像求倍增lca一样往上跳验证，也可以用二分答案来往上跳验证。

我这里用了二分的写法。注意原题三个数不一定按顺序给出。

#include
      
       #include