Link
That's a good question,
subject
solution
From "only one chess piece can be skipped at a time", an important property of this question is obtained:
There are at most three jumping methods for these three chess pieces at a certain time: the middle piece jumps left and right, or the piece closer to the middle piece jumps to the middle. like this
When AB=BC, there are only two jumping methods (A cannot jump to the position of A ')
When the outside point jumps in, the range of these three pieces will be smaller and smaller until there is a situation that they can't jump in.
We find that the state at this time is unique: the three pieces cannot reproduce the relative state at this time elsewhere.
We take this state as the root;
Judge the roots of two groups of pieces. If they are different, it means that they can never look like another group; Direct output No.
If they can be placed in the same root, then we need LCA.
The first group of pieces will eventually move to the state of LCA and then to the state of the second group of pieces.
be careful
- For LCA, we can't use multiplication, but we can use dichotomy to accelerate
- In case AB is close and BC is far away, it can be optimized here, like this:
When AB moves, just add (k-1)*AB directly. (translation method) since there is no special difference between chess pieces, you don't need to care about whether the AB position is exchanged.
Code
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int astep,bstep; struct asdf{ int a,b,c; } A,B,Fka,Fkb; void px(asdf &LL){ //Sort if(LL.a>LL.b) swap(LL.a,LL.b); if(LL.a>LL.c) swap(LL.a,LL.c); if(LL.b>LL.c) swap(LL.b,LL.c); } int getroot(int &aa,int &bb,int &cc){ //Find root int step = 0,l,jl1,jl2; while(aa+cc!=bb*2){ //If AB= AC jl1 = bb-aa;//AB jl2 = cc-bb;//BC if(jl1<jl2){ //Left inward l = jl2/jl1; //How many times can you jump if(jl2%jl1 == 0) --l; aa += jl1*l; //translation bb += jl1*l; step += l; //Statistical steps } else { //Right inward / / ditto l = jl1/jl2; if(jl1%jl2 == 0) --l; bb -= jl2*l; cc -= jl2*l; step += l; } } return step; } asdf jummp(asdf ll,int step){ //Skip step on ll status int l,jl1,jl2; while(step){ jl1 = ll.b-ll.a; //It's the same as finding the root. I don't want to comment jl2 = ll.c-ll.b; if(jl1<jl2){ l = jl2/jl1; if(jl2%jl1 == 0) --l; l = min(l,step); ll.a += jl1*l; ll.b += jl1*l; step -= l; } else { l = jl1/jl2; if(jl1%jl2 == 0) --l; l = min(l,step); ll.b -= jl2*l; ll.c -= jl2*l; step -= l; } } return ll; } bool db(asdf aa,asdf bb){ //Compare whether the two states are the same if(aa.a!=bb.a||aa.b!=bb.b||aa.c!=bb.c) return 0; return 1; } int main(){ scanf("%d%d%d%d%d%d",&A.a,&A.b,&A.c,&B.a,&B.b,&B.c); px(A); px(B); //sort Fka = A; //Temporary storage Fkb = B; astep = getroot(Fka.a,Fka.b,Fka.c); //Find root bstep = getroot(Fkb.a,Fkb.b,Fkb.c); if(db(Fka,Fkb)==0){ //Different roots printf("NO"); return 0; } if(astep > bstep) A = jummp(A,astep-bstep); //Jump to the same height first else B = jummp(B,bstep-astep); int l = 0,r = min(astep,bstep), mid; //Dichotomy while(l<r){ mid = (l+r)/2; Fka = jummp(A,mid); Fkb = jummp(B,mid); if(db(Fka,Fkb) == 1) r = mid; //Jump mid*2 steps to reach else l = mid+1; //no way } printf("YES\n%d",max(astep-bstep,bstep-astep)+r*2); }