有没有一组Hack数据可以让这两份代码输出结果不同?(不考虑时间复杂度和空间复杂度)
代码1:
#include<bits/stdc++.h>
using namespace std;
int n,side,m,sticks[25];
bool visit[25];
bool DFS(int sum,int number,int position){
if(number==3){
return true;
}
int sample=0;
for(int i=position;i<m;++i){
if(visit[i]||sum+sticks[i]>side||sticks[i]==sample) continue;
visit[i]=true;
if(sum+sticks[i]==side){
if(DFS(0,number+1,0)) return true;
else sample=sticks[i];
}else{
if(DFS(sum+sticks[i],number,i+1)) return true;
else sample=sticks[i];
}
visit[i]=false;
}
return false;
}
bool cmp(int x,int y){ return x>y; }
int main(){
scanf("%d",&n);
while(n--){
int length=0;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d",&sticks[i]);
length+=sticks[i];
}
memset(visit,false,sizeof(visit));
if(length%4!=0){
printf("no\n");
continue;
}
side=length/4;
sort(sticks,sticks+m,cmp);
if(sticks[0]>side){
printf("no\n");
continue;
}
if(DFS(0,0,0)) printf("yes\n");
else printf("no\n");
}
return 0;
}
代码2:
#include<bits/stdc++.h>
using namespace std;
int n,side,m,sticks[25];
bool visit[25];
bool DFS(int sum,int number,int position){
if(number==4){
return true;
}
int sample=0;
for(int i=position;i<m;++i){
if(visit[i]||sum+sticks[i]>side||sticks[i]==sample) continue;
visit[i]=true;
if(sum+sticks[i]==side){
if(DFS(0,number+1,0)) return true;
else sample=sticks[i];
}else{
if(DFS(sum+sticks[i],number,i+1)) return true;
else sample=sticks[i];
}
visit[i]=false;
}
return false;
}
bool cmp(int x,int y){ return x>y; }
int main(){
scanf("%d",&n);
while(n--){
int length=0;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d",&sticks[i]);
length+=sticks[i];
}
memset(visit,false,sizeof(visit));
if(length%4!=0){
printf("no\n");
continue;
}
side=length/4;
sort(sticks,sticks+m,cmp);
if(sticks[0]>side){
printf("no\n");
continue;
}
if(DFS(0,0,0)) printf("yes\n");
else printf("no\n");
}
return 0;
}