1563: hzwer的跳跳棋(hop)

时间限制: 1 Sec 内存限制: 256 MB

题目描述

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

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

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

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

输入

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

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

输出

如果无解，输出一行NO。

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

样例输入

1 2 3
0 3 5

样例输出

YES
2

提示

【范围】

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

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

100% 绝对值不超过10^9

#include<cstdio>
#include<algorithm>
#define ll long long
#define inf 1e9
using namespace std;
//-----------------------------------------------------------------------
template<class T>inline void cin(T&x){
    static char c;static int y;
    for(c=getchar(),x=0,y=1;c<48||57<c;c=getchar())if(c=='-')y=-1;
    for(;48<=c&&c<=57;c=getchar())x=((x+(x<<2))<<1)+(c^'0');
    x*=y;}
void outint(int x){if(x>=10) outint(x/10);putchar(x%10+'0');}
//--------------------------optimization above---------------------------
int t1,t2,tmp,ans;
int a[4],b[4];
struct data{int a[4];};
data cal(int *a,int k){data ans;int t1=a[2]-a[1],t2=a[3]-a[2];//mark the distance between two chessman
    for(int i=1;i<=3;i++)ans.a[i]=a[i];//initialization ans
    if(t1==t2)return ans;//if has moved ,just return 
    if(t1<t2){int t=min(k,(t2-1)/t1);k-=t;tmp+=t;ans.a[2]+=t*t1;ans.a[1]+=t*t1;}
    else{int t=min(k,(t1-1)/t2);k-=t;tmp+=t;ans.a[2]-=t*t2;ans.a[3]-=t*t2;}
    if(k)return cal(ans.a,k);else return ans;}
bool operator!=(data a,data b){for(int i=1;i<=3;i++)if(a.a[i]!=b.a[i])return 1;return 0;}
int main()
{for(int i=1;i<=3;i++)cin(a[i]);for(int i=1;i<=3;i++)cin(b[i]);//read given a,b,c   and x,y,z 
    sort(a+1,a+4);sort(b+1,b+4);//set them in order
    data t1=cal(a,inf);int d1=tmp;tmp=0;
    data t2=cal(b,inf);int d2=tmp;tmp=0;//t1,t2 as their root ,and d1 d2 as their deep
    if(t1!=t2){puts("NO");return 0;}//has no root,just has no solution
    if(d1>d2){swap(d1,d2);for(int i=1;i<=3;i++)swap(a[i],b[i]);}//move from x,y,z_move from a,b,c has the same steps
    //so if the deep1 is deeper than deep2 ,just change the a,b,c and x,y,z
    //it's easier to deal with the data in the following steps
    ans=d2-d1;t1=cal(b,ans);//just set the answer as d1-d1(move steps,not the last solution),just let x,y,z move such steps
    for(int i=1;i<=3;i++)b[i]=t1.a[i];int l=0,r=d1;
    while(l<=r){int mid=(l+r)>>1;if(cal(a,mid)!=cal(b,mid))l=mid+1;else r=mid-1;}//dichotomy idiology
    puts("YES");outint(ans+2*l);return 0;
}

program is just above,the program is the best language.