[bzoj 2144]:ジャンプ

2144:ジャンプ
Time Limit: 10 Sec  
Memory Limit: 259 MB
Submit: 689  
Solved: 326
[ Submit][ Status][ Discuss]
Description
ジャンプは1本の数軸で行われる.駒は整点にしか並べられない.ポイントごとに1つ以上の駒を並べてはいけません.私たちはジャンプ将棋で簡単なゲームをします.碁盤には3つの駒があり、それぞれa,b,cの3つの位置にあります.私たちは最小限のジャンプで彼らの位置をx,y,zに移動しなければならない.(駒は区別がない)ジャンプのルールは簡単で、任意に1つの駒を選んで、1つの中軸駒に対してジャンプする.ジャンプ後の2つの駒の距離は変わらない.1回に1つの駒をスキップすることしか許されない.1つのプログラムを書いて、まず任務を完成できるかどうかを判断する.できれば、最低限必要なジャンプ回数を出力する.
Input
第1行は、現在の駒の位置a b cを表す3つの整数を含む.(互いに異なる)2行目は、ターゲット位置x y zを表す3つの整数を含む.(互いに異なる)
Output
解がなければ,1行NOを出力する.到着可能であれば、1行目はYES、2行目は最低ステップ数を出力します.
Sample Input
1 2 3 0 3 5
Sample Output
YES 2【範囲】100%絶対値10^9を超えない
構想
bzoj 2144跳跳棋2017.6.2 by xlj难题一道とても考えにくい题目の条件の中から6种类の状态が见えますしかし1つの驹が2つの驹をスキップすることができないためもし1 4 10この时の右侧の跳ぶことができないならば2つの驹を越えたためただ3种类(中间の跳ぶことができる両侧&中间の驹の距离に近い跳ぶことができます)y-x=t 1 z-y=t 2とするとt 1=t 2のときにジャンプできない状態が木の根であるt 1 t 1が同じでgcdのような方法で木の根を求める(t 1,t 2)->(t 1-t 2,t 2)与えられたa 1,b 1,c 1から数本のa 2,b 2を上に押し出し、c 2も同様に木の根が違うと出力NOが完成しないと同じように2つの状態の深さを同じにしてから上を探す(LCA)ここでは二分法で探す

#include
#include
#include
#include
#include
#include
#define inf 1000000000
using namespace std;
int a[5],b[5];
struct node{
	int a[5];
};
int tmp,ans;
node cal(int *a,int k)//           k             
{
	node ans;
	int t1=a[2]-a[1];int t2=a[3]-a[2];
	for(int i=1;i<=3;i++) ans.a[i]=a[i];
	if(t1==t2) return ans;
	if(t1d2)
    {
		swap(d1,d2);
		for(int i=1;i<=3;i++)swap(a[i],b[i]);
    }
    ans=d2-d1;//         
    t1=cal(b,ans);
    for(int i=1;i<=3;i++) b[i]=t1.a[i];
    int l=0,r=d1;
    while(l<=r)//    LCA 
    {
		int mid=(l+r)>>1;
		if(cal(a,mid)!=cal(b,mid))l=mid+1;//       
		else r=mid-1;//                    
    }
    puts("YES");
    printf("%d",ans+2*l);
    return 0;
}