#include <stdio.h>

#define MAX 1024

main()
{
	int coins[] = { 1, 5, 10};
	int times[MAX] = { 0 }, from[MAX] = { 0 };
	int size = sizeof(coins) / sizeof(int);
	int i, j, c;

	for( i = 1; i < MAX; i++) {
		times[i] = MAX;
		from[i] = -1;
	}

	for( i = 0; i < MAX; i++ ) {
		for( j = 0; j < size; j++ ) {
			if( from[i] != -1 && i + coins[j] < MAX && times[i] + 1 < times[i + coins[j]] ) {
				times[i + coins[j]] = times[i] + 1;
				from[i + coins[j]] = i;
			}
		}
	}

	printf("最多可換 %d 元，請輸入您想換的金額：", MAX - 1);
	scanf("%d", &c);

	if ( c >= MAX || from[c] == -1 ) {
		printf("對不起，無解！\n");
		return -1;
	}

	while( times[c] != 0 ) {
		printf("%d ", c - from[c] );
		c = from[c];
	}
	printf("\n");
}