#include #include using namespace std; const int coins[] = { 1, 3, 6, 12, 24, 30, 60 }; const int num_different_coins = sizeof(coins) / sizeof(coins[0]); int main(int argc, char * argv[]) { if (argc != 3) { cerr << "usage: " << argv[0] << " total_value max_number_of_coins\n"; exit(1); } int total_value = atol(argv[1]); int max_num_coins = atol(argv[2]); const int value_max = 240, numcoin_max = 10; bool cibd[value_max + 1][numcoin_max + 1][num_different_coins + 1]; bzero(cibd, sizeof(cibd)); for (int i = 0; i <= numcoin_max; i += 1) for (int j = 0; j <= num_different_coins; j += 1) cibd[0][i][j] = true; for (int last_usable_coin = 0; last_usable_coin <= num_different_coins; last_usable_coin += 1) for (int max_num_coins = 0; max_num_coins <= numcoin_max; max_num_coins += 1) for (int total_value = 1; total_value <= value_max; total_value += 1) { bool x = false, y = false; if (total_value >= coins[last_usable_coin] && max_num_coins > 0) x = cibd[total_value - coins[last_usable_coin]][max_num_coins - 1][last_usable_coin]; if (last_usable_coin > 0) y = cibd[total_value][max_num_coins][last_usable_coin - 1]; cibd[total_value][max_num_coins][last_usable_coin] = x || y; } bool answer = cibd[total_value][max_num_coins][num_different_coins]; if (answer) { cout << "yes\n"; int last_usable_coin = num_different_coins; while (total_value > 0) { if (last_usable_coin > 0 && cibd[total_value][max_num_coins][last_usable_coin - 1]) last_usable_coin -= 1; else { cout << coins[last_usable_coin] << "\n"; total_value -= coins[last_usable_coin]; max_num_coins -= 1; } } } else cout << "no\n"; }