题意
跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏：棋盘上有三颗棋子，分别在 $a,b,c$ 这三个位置。我们要通过最少的跳动把他们的位置移动成 $x,y,z$（注意：棋子是没有区别的）。跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过一颗棋子。
写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。
思路
可以将状态视为一个三元组$(x,y,z)$。- 中间往左跳：$(x,y,z) –> (2x-y,x,z)$
- 中间往右跳：$(x,y,z) –> (x,z,2z-y)$
- 左边往右跳：$if (y-x)<(z-y) then (x,y,z) –> (y,2y-x,z) Because ‘Only one chess piece is allowed to be skipped at a time.’$
- 右边往左跳：$if (y-x)>(z-y) then (x,y,z) –> (x,2y-z,y) Because ‘Only one chess piece is allowed to be skipped at a time.’$
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
#include<bits/stdc++.h> #define int long long #define MAXN 500010 using namespace std; inline int read(){ int res=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); return res*f; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x<10) putchar(x+'0'); else{ write(x/10); putchar(x%10+'0'); } } struct node{ int x,y,z; }endsss,tmps; node make(int x,int y,int z){ node pp;pp.x=x;pp.y=y;pp.z=z;return pp; } int GetFa(node p){ int x=p.x,y=p.y,z=p.z,res=0; if(y-x<z-y){ int pt=y-x; int zr=z-y; int kkk=zr%pt;res=zr/pt; if(kkk==0) --res,kkk+=pt; res+=GetFa(make(z-kkk-(y-x),z-kkk,z)); return res; //-----X--Y-Z---------- }else if(y-x>z-y){ int pt=z-y; int zr=y-x; int kkk=zr%pt;res=zr/pt; if(kkk==0) --res,kkk+=pt; res+=GetFa(make(x,x+kkk,x+kkk+(z-y))); return res; //------X-Y---Z---------- }else{ endsss=p; return 0; } } void move(node p,int stp){ int x=p.x,y=p.y,z=p.z; int pt=y-x,zr=z-y,cz,res=0; if(stp==0||pt==zr){endsss=p;return ;} if(pt<zr){ res=zr/pt; cz=zr%pt; if(cz==0) cz=pt,--res; if(stp<res) move(make(z-cz-(res-stp+1)*pt,z-cz-(res-stp)*pt,z),0); else move(make(z-cz-pt,z-cz,z),stp-res); //X,Y,Z }else{ res=pt/zr; cz=pt%zr; if(cz==0) cz=zr,--res; if(stp<res) move(make(x,x+cz+zr*(res-stp),x+cz+zr*(res-stp+1)),0); else move(make(x,x+cz,x+cz+zr),stp-res); //X,Y,Z } } int tmp[5]; void Sort(int &x,int &y,int &z){ tmp[1]=x;tmp[2]=y;tmp[3]=z; sort(tmp+1,tmp+3+1); x=tmp[1];y=tmp[2];z=tmp[3]; } int a,b,c; int x,y,z; bool judge(node q,node p){ if(q.x==p.x&&q.y==p.y&&q.z==p.z) return 0; return 1; } bool check(int mid){ move(make(x,y,z),mid);tmps=endsss; move(make(a,b,c),mid); if(judge(tmps,endsss)==1) return 0; return 1; } signed main(){ a=read();b=read();c=read(); x=read();y=read();z=read(); Sort(x,y,z); Sort(a,b,c); int stp1=GetFa(make(a,b,c));tmps=endsss; int stp2=GetFa(make(x,y,z)); if(judge(tmps,endsss)==1){ puts("NO"); return 0; } if(stp1<stp2) move(make(x,y,z),stp2-stp1),x=endsss.x,y=endsss.y,z=endsss.z; else if(stp1>stp2) move(make(a,b,c),stp1-stp2),a=endsss.x,b=endsss.y,c=endsss.z; int l=0,r=min(stp1,stp2),mid,ans; while(l<=r){ mid=l+r>>1; if(check(mid)) r=mid-1,ans=mid; else l=mid+1; } puts("YES"); write(ans*2+abs(stp1-stp2));putchar('\n'); return 0; } //(x,y,z) --> (2x-y,x,z) //(x,y,z) --> (x,z,2z-y) //if (y-x)<(z-y) then (x,y,z) --> (y,2y-x,z) Because 'Only one chess piece is allowed to be skipped at a time.' //if (y-x)>(z-y) then (x,y,z) --> (x,2y-z,y) Because 'Only one chess piece is allowed to be skipped at a time.' |
