Embercode: AI-powered software engineer course

1. What does this program print? ``

cpp
#include <iostream>
#include <vector>

std::vector<int> greedy_coins(const std::vector<int>& coins_desc, int amount) {
    std::vector<int> used;
    for (int coin : coins_desc) {
        while (amount >= coin) {
            used.push_back(coin);
            amount -= coin;
        }
    }
    return used;
}

int main() {
    for (int coin : greedy_coins({9, 6, 5, 1}, 12)) std::cout << coin << ' ';
    std::cout << '\n';
}

`` Choose the exact output, including the spaces between numbers.

6 69 1 1 19 6 15 5 1 1

2. What does this program print? ``

cpp
#include <iostream>
#include <limits>
#include <vector>

std::vector<int> best_counts(const std::vector<int>& coins, int max_amount) {
    const int inf = std::numeric_limits<int>::max() / 2;
    std::vector<int> best(max_amount + 1, inf);
    best[0] = 0;
    for (int x = 1; x <= max_amount; ++x) {
        for (int coin : coins) {
            if (coin <= x && best[x - coin] + 1 < best[x]) {
                best[x] = best[x - coin] + 1;
            }
        }
    }
    return best;
}

int main() {
    for (int b : best_counts({1, 3, 4}, 6)) std::cout << b << ' ';
    std::cout << '\n';
}

`` Choose the exact output, including the spaces between numbers.

0 1 2 1 1 2 30 1 1 1 1 2 20 1 2 3 4 5 60 1 2 1 1 2 2

3. For the coins 1, 20 and 21, what bound does find_counterexample use?

30214140

4. In best_counts, why is inf set to std::numeric_limits<int>::max() / 2 instead of the full maximum?

So the array takes less memorySo inf + 1 cannot overflow when the code adds 1 to an unreachable entrySo greedy can read the coins in orderSo the best counts stay even numbers

5. Statement: greedy is optimal for every amount with the coins 1, 2 and 5.

True, because the checker's report for [1, 2, 5] says greedy is optimal for every amount up to the boundFalse, because greedy fails at amount 4 with these coins

Coin systems