>>526 これより早いのを書ける人カモン
#include <stdio.h>
#include <stdlib.h>
void hoge(long weight, int index, long worth, char *table){
static const int coin_weight[]={70, 48, 45, 40, 37, 10};
static const int coin_worth[]={500, 100, 10, 50, 5, 1};
static const int coin5[]={0, 3, 6, 9, 2, 5, 8, 1, 4, 7};
int a, b, x, w, i, coin_max;
if(index==4){
b=coin5[weight%10];
if((w=weight-b*37)<0) return;
x=w/370;
a=(w-x*370)/10;
worth+=a+b*5+x*37;
for(i=0;i<=x;i++) table[worth+i*13]=1;
return;
}
coin_max=weight/coin_weight[index];
for(i=0;i<=coin_max;i++) hoge(weight-i*coin_weight[index], index+1, worth+i*coin_worth[index], table);
}
int main(void){
double weight=8.0;
long i, table_size;
char *table;
scanf("%lf", &weight);
table_size=weight*500/7+1;
table=calloc(1, table_size);
hoge((weight*10+0.1), 0, 0, table);
for(i=0;i<table_size;i++) if(table[i]) printf("%ld\n", i);
free(table);
return 0;
}