| ||||||||||
| 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