09/01/12 01:47:26
>>697 1問目 枝狩りしてないので n=100 (190569292 通り) くらいが限界。ついでにすぐに計算結果が long を超える
#include<stdio.h>
#include<stdlib.h>
int min(int a, int b){
if(a<b) return a;
return b;
}
long huga(int n, int maximum){
int i;
long ret=0;
for(i=min(n, maximum);i>0;i--){
if(n-i>0) ret+=huga(n-i, min(i, maximum));
else ret++;
}
return ret;
}
long hoge(int n){
return huga(n, n);
}
int main(int argc, char *argv[]){
int n=4;
if(argc==2) n=atoi(argv[1]);
printf("払い方は %ld 通り (n=%d)\n", hoge(n), n);
return 0;
}