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:这个程序确实WA, 但是您可以找一个让这个程序WA的数据吗?

Posted by liuche_90 at 2008-05-22 11:02:35 on Problem 1011
In Reply To:这个程序确实WA, 但是您可以找一个让这个程序WA的数据吗? Posted by:gzw_02 at 2008-05-22 00:31:41
> 答案是,我找不到. 我的朋友找不到,一些AC了这题的学友也找不到, 
> 
> 您能找到吗?期待您的参与.
> 
> 
> # include <iostream>
> using namespace std;
> 
> const short maxsize = 65;
> short sticks[maxsize];
> bool  isused[maxsize]; 
> short gl;  //当前应找合并的木棍数
> short n; //当前木棍总数
> short partlen; //当前每段应该合成的长度
> int comp(const void * a,const void *b){
> 	short *ca = (short*)a;
> 	short *cb = (short*)b;
> 	return *cb - *ca;
> }
> bool findstick(short index, short step, short clen){
> 	// clen --- 累加长度 <= partlen
> 	// step --- 找到的木棍数  step为gl-1时结束
> 	// index --- 当前要取的木棍
> 	int k;
> 	if( step==gl-1) return true; 
> 	isused[index]=1;
>     if(clen==partlen){
> 		if(step>0&&!isused[step-1]){
> 			isused[index]=0;
> 			return false;
> 		}
> 		clen=0;
> 		step++;
> 	}
> 	
> 	for(short i=step;i<n;i++){
> 		
> 		
> 		if(!isused[i]){
> 			if(partlen-clen>sticks[i]){
> 				if(!findstick(i,step,clen+sticks[i])){
> 					k=i;
> 					while(sticks[++i]==sticks[k]);
> 					i--;
> 				}   else{
> 					return true;
> 				}
> 			}
> 			else if(partlen-clen==sticks[i]){    
> 				return findstick(i,step,clen+sticks[i]);
> 			}
> 		}//isused
> 		
> 	}//for
> 	isused[index]=0;
> 	return false;
> }
> int main(){
> 	while(cin>>n){
> 		
> 		if(!n) break;
> 		int i=0;
> 		int sum=0;
> 		int maxlen = 0;
> 		while(i<n){
> 			cin>>sticks[i];
> 			sum+=sticks[i];
> 			if(maxlen<sticks[i]) maxlen=sticks[i];
> 			i++;
> 		}
> 		//对sticks[0..n-1]降序排序
> 		qsort(sticks,n,sizeof(short),comp);
> 		// maxlen到sum的长度k,使得sum%k=0的最小的k值
> 		for(int k=maxlen;k<=sum;k++){
> 			if(sum%k==0) {
> 				for(i=0;i<n;i++){
> 					isused[i]=0;
> 				}
> 				gl = sum/k;
> 				partlen = k;
> 				if(findstick(0, 0,sticks[0])){
> 					cout<<k<<endl;
> 					break;
> 				}
> 			}
> 		}
> 	}
> 	return 1;
> } 
> 
> 

的确是WA,我找到了.

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