Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:暴力枚举题,放心不会超int

Posted by 20051106 at 2016-12-17 10:32:25 on Problem 1311
In 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator