#include<stdio.h>
#include<stdlib.h>
#include<string.h>
bool datascan();int solve(int,int);
int a[512],amax;
long int memo[513][21];
long int ans = 0;
int main(void){
int i,j;
for(i = 0; i < 513; i++){
for(j = 0; j < 21; j++){
memo[i][j] = 0;
}
}
if(datascan()){
exit(EXIT_FAILURE);
}
solve(1,a[0]);
printf("%d\n",ans);
return 0;
}
int solve(int i,int sum){
long int ret = 0;
long int patn;
if(i == amax - 1){
if(a[amax - 1] == sum){
ans++;
return 1;
}else{
return 0;
}
}else if(memo[i][sum] != 0){
ans = ans + memo[i][sum];
return memo[i][sum];
}else{
if(sum + a[i] <= 20){
patn = solve(i + 1,sum + a[i]);
if(patn != 0){
memo[i][sum] += patn;
ret += patn;
}
}
if(sum - a[i] >= 0){
patn = solve(i + 1,sum - a[i]);
if(patn != 0){
memo[i][sum] += patn;
ret += patn;
}
}
}
return (ret);
}
bool datascan(void){
int i = 0;
char fbuf[513],*p;
FILE *fp;
if((fp = fopen("2011-yo-t4-in5.txt","r")) == NULL){
printf("file open error\n");
return true;
}
fgets(fbuf,100,fp);
sscanf(fbuf,"%d",&amax);
fgets(fbuf,512,fp);
printf("%s\n",fbuf);
p = fbuf;
do{
sscanf(p,"%d",&a[i]);
i++;
p++;
}while((p = strchr(p,' ')) != NULL);
for(i = 0; i < amax; i++){
printf("%d ",a[i]);
}
printf("\n");
fclose(fp);
return false;
}
一体何がダメなのか…
まぁ一応ここで12点取れてれば大丈夫な気はするけど。
0 件のコメント:
コメントを投稿