gnaggnoyil
gnaggnoyil

我該說是sgu的評測機奇葩還是我本機的評測環境奇葩

本來指望把sgu502當作水題刷一下的,結果事實證明無論你在本機上測試多么沒問題,上sgu必須把數組開的足夠大,否則就等著RTE吧.

#include <cstdio>
#include <cstring>
#include <cstdlib>
#define maxn 19
#define maxs (1<<18)
int dp[maxs][19];
int dt[maxn];
char str[255];
int n,s;
bool search(int a,int b){
if(a==0)
return b==0;
if(dp[a][b]==0)
return false;
if(dp[a][b]==1)
return true;
for(int ta,tb,i=1;i<=n;i++){
if((a&(1<<(i-1)))==0)
continue;
ta=a^(1<<(i-1)),tb=(b-dt[i]+17)*12%17;
if((ta==0)&&(dt[i]==0))
continue;
if(search(ta,tb))
return dp[a][b]=1,true;
}
return dp[a][b]=0,false;
}
int print(int a,int b){
if(a==0)
return 0;
for(int ta,tb,i=1;i<=n;i++)
if((a&(1<<(i-1)))!=0){
ta=a^(1<<(i-1)),tb=(b-dt[i]+17)*12%17;
if((ta==0)&&(dt[i]==0))
continue;
if(search(ta,tb))
return print(ta,tb),printf("%d",dt[i]),0;
}
return 0;
}
int main(){
scanf("%s",str);
n=strlen(str);
if(n==18){
printf("-1\n");
return 0;
}
for(int i=1;i<=n;i++)
dt[i]=str[i-1]-'0';
s=(1<<n)-1;
for(int i=0;i<=s;i++)
for(int j=0;j<17;j++)
dp[i][j]=-1;
if(search(s,0))
print(s,0);
else
printf("-1");
printf("\n");
return 0;
}