1 条题解
-
0
#include <bits/stdc++.h> using namespace std; int d1, d2, d3, x, y, z, X, Y, Z, a[5]; struct node{int x,y,z,tot;}A,B; inline void findroot(int x, int y, int z) { int tot=0; while (1) { d1=y-x; d2=z-y; if (d1==d2) break; if (d1>d2) d3=(d1-1)/d2, tot += d3, y -= d3*d2, z -= d3*d2; else d3=(d2-1)/d1, tot += d3, x += d3*d1, y += d3*d1; } if (A.x||A.y) B=node{x,y,z,tot}; else A=node{x,y,z,tot}; } inline void Swap() { swap(x,X), swap(y,Y), swap(z,Z); swap(A.x,B.x), swap(A.y,B.y), swap(A.z,B.z), swap(A.tot,B.tot); } inline bool check(int T, int x, int y, int z, int X, int Y, int Z) { int tot=T; while (tot) { d1=y-x; d2=z-y; if (d1==d2) break; if (d1>d2) d3=min((d1-1)/d2, tot), tot -= d3, y -= d3*d2, z -= d3*d2; else d3=min((d2-1)/d1, tot), tot -= d3, x += d3*d1, y += d3*d1; } tot=T; while (tot) { d1=Y-X; d2=Z-Y; if (d1==d2) break; if (d1>d2) d3=min((d1-1)/d2, tot), tot -= d3, Y -= d3*d2, Z -= d3*d2; else d3=min((d2-1)/d1, tot), tot -= d3, X += d3*d1, Y += d3*d1; } return X==x&&Y==y&&Z==z; } int main() { scanf("%d%d%d", &a[1], &a[2], &a[3]); sort(a+1,a+4);x=a[1];y=a[2];z=a[3]; scanf("%d%d%d", &a[1], &a[2], &a[3]); sort(a+1,a+4);X=a[1];Y=a[2];Z=a[3]; findroot(x,y,z);findroot(X,Y,Z); if(A.x!=B.x||A.y!=B.y||A.z!=B.z){printf("NO");return 0;} if(A.tot<B.tot) Swap(); int ans, tot; ans=tot=A.tot-B.tot; while (tot) { d1=y-x; d2=z-y; if (d1==d2) break; if (d1>d2) d3=min((d1-1)/d2, tot), tot -= d3, y -= d3*d2, z -= d3*d2; else d3=min((d2-1)/d1, tot), tot -= d3, x += d3*d1, y += d3*d1; } int L=0, R=B.tot, c; while (L<=R) { int mid=L+R>>1; if (check(mid, x, y, z, X, Y, Z)) c=mid, R=mid-1;//中间变量c记录最小的mid else L=mid+1; } printf("YES\n%d", ans+c*2); return 0; }
- 1
信息
- ID
- 3809
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 3
- 上传者