2011年11月29日火曜日

JOI予選、去年の問題

なぜか入力3が出来るのに入力4,5が出来ない。あと例題2も出来ない。

#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 件のコメント:

コメントを投稿