Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:暴力枚举题,放心不会超intIn Reply To:暴力枚举题,放心不会超int Posted by:KatrineYang at 2016-09-12 11:21:16 > #include <iostream> > #include <stdio.h> > using namespace std; > > int perm[24][4] = {{0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},{0,3,1,2},{0,3,2,1}, > {1,0,2,3},{1,0,3,2},{1,2,0,3},{1,2,3,0},{1,3,0,2},{1,3,2,0}, > {2,0,1,3},{2,0,3,1},{2,1,0,3},{2,1,3,0},{2,3,0,1},{2,3,1,0}, > {3,0,1,2},{3,0,2,1},{3,1,0,2},{3,1,2,0},{3,2,0,1},{3,2,1,0}}; > > struct rec{ > int x, y; > }; > > int gcd(int x, int y){ > if(x == 0) return y; > if(y == 0) return x; > if(x > y) return gcd(y, x%y); > return gcd(x, y%x); > } > > bool ky(rec *R, int gs, int X, int Y){ > if(gs == 1){ > return X*R[0].y == Y*R[0].x; > } > if(Y%R[0].y==0){ > int i1 = Y/R[0].y; > if(R[0].x*i1<X){ > bool f = ky(R+1, gs-1, X-R[0].x*i1, Y); > if(f) return 1; > } > } > if(X%R[0].x==0){ > int i1 = X/R[0].x; > if(R[0].y*i1<Y){ > bool f = ky(R+1, gs-1, X, Y-R[0].y*i1); > if(f) return 1; > } > } > return 0; > } > > int main() { > int X, Y; > int cnt = 0; > while(1){ > scanf("%d%d", &X, &Y); > if(X==0 && Y==0) return 0; > cnt ++; > rec r[4]; > for(int i = 0; i < 4; i++){ > scanf("%d%d", &r[i].x, &r[i].y); > int g = gcd(r[i].x, r[i].y); > r[i].x /= g, r[i].y /= g; > } > bool kx = 0; > for(int p = 0; p < 24; p++){ > rec R[4]; > for(int i = 0; i < 4; i++){ > R[i] = r[perm[p][i]]; > } > int x1 = R[0].x, y1 = R[0].y, x2 = R[1].x, y2 = R[1].y; > int x3 = R[2].x, y3 = R[2].y, x4 = R[3].x, y4 = R[3].y; > int fm14 = x1*y4+x4*y1, fm23 = x2*y3+x3*y2; > if((Y*x4)%fm14==0 && (Y*x1)%fm14==0 && (Y*x3)%fm23==0 && (Y*x2)%fm23==0){ > int i1 = Y*x4/fm14, i4 = Y*x1/fm14, i2 = Y*x3/fm14, i3 = Y*x2/fm14; > if(x1*i1+x2*i2==X && x3*i3+x4*i4==X){ > kx = 1; > goto done; > } > } > int fm12 = x1*y2+x2*y1, fm34 = x3*y4+x4*y3; > if((X*y2)%fm12==0 && (X*y1)%fm12==0 && (X*y4)%fm34==0 && (X*y3)%fm34==0){ > int i1 = X*y2/fm12, i2 = X*y1/fm12, i3 = X*y4/fm34, i4 = X*y3/fm34; > if(y2*i2+y3*i3==Y && y1*i1+y4*i4==Y){ > kx = 1; > goto done; > } > } > if(ky(R, 4, X, Y)){ > kx = 1; > goto done; > } > } > done: > if(kx) printf("Set %d: Yes\n", cnt); > else printf("Set %d: No\n", cnt); > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator