Размен. Алгоритмическая задача с хендбука Яндекс

Question

Помогите пожалуйста решить задачу. Размен: все варианты

МОЕ РЕШЕНИЕ. оно не проходит некоторые тесты и я не понимаю почему. Мое решение корректно отрабатывает даже варианты при money=25 и подобных. В телеграм чат хендбука писал два дня назад, мне никто не смог помочь.

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

struct VectorComparator {
    bool operator()(const std::vector<int>& a, const std::vector<int>& b) const {
        return a.size() < b.size();
    }
};

using Store = std::set<std::vector<int>, VectorComparator>;

std::vector<int> optimalChange(int money) {
    std::vector<int> coins;
    while (money > 0) {
        if (money >= 10) {
            coins.push_back(10);
            money -= 10;
        }
        else if (money >= 5) {
            coins.push_back(5);
            money -= 5;
        }
        else {
            coins.push_back(1);
            --money;
        }
    }
    return coins;
}
std::vector<int> change10(std::vector<int> coins) {
    auto it = std::find(coins.begin(), coins.end(), 10);
    if (it != coins.end()) {
        *it = 5;
        coins.push_back(5);
    }
    return coins;
}
std::vector<int> change5(std::vector<int> coins) {
    auto it = std::find(coins.begin(), coins.end(), 5);
    if (it != coins.end()) {
        *it = 1;
        coins.push_back(1);
        coins.push_back(1);
        coins.push_back(1);
        coins.push_back(1);
    }
    return coins;
}

size_t allChanges(int money, Store& store) {
    store.clear();
    store.insert(optimalChange(money));
    while (true) {
        Store copyStore(store);
        for (const auto& coins : copyStore) {
            store.insert(change10(coins));
            store.insert(change5(coins));
        }
        if (copyStore.size() == store.size())
            break;
    }
    return store.size();
}

int main() {
    int money;
    std::cin >> money;
    Store allSets;
    std::cout << allChanges(money, allSets);

    
    for (auto coins : allSets) {
        std::cout << '\n';
        std::sort(coins.begin(), coins.end());
        std::cout << coins.size();
        for (const auto& coin : coins) {
            std::cout << ' ' << coin;
        }
    }
}

Answer 1

Как вам правильно подчказали, ваша первая проблема в том, что вы сравниваете наборы просто по количеству монет. В таком случае, если есть 2 набора монет с разным номиналом, но одинаковой суммой и одинаковым количеством монет, то ваш вариант это не учтет.

Вторая ваша проблема, как мне кажется, в том, что вы сильно перемудрили с алгоритмом. По сути, у вас конечное количество номиналов монет, потому вы можете просто перебрать варианты сразу так, чтобы среди них не было повторений. Ну просто вложенными циклами сделать тупо и всё. Пример на C#

private List<(int one, int five, int ten)> GetAllOptions(int amount)
{
    var ret = new List<(int one, int five, int ten)>();
    
    for(int tens = 0; tens*10 <= amount; tens ++)
    {       
        var reminder1 = amount - tens * 10;
        
        for(int fives = 0; fives * 5 <= reminder1; fives ++)
        {
            var ones = reminder1 - 5 * fives;       
            ret.Add((ones, fives, tens));                               
        }
    }
    return ret;
}

Каждая итерация здесь генерирует уникальную комбинацию монет, потому повторов тут не будет, а значит нет необходимости убирать дубликаты путей. Ну и как бы ясно, что я просто раскладываю amount = ones + fives * 5 + tens * 10 и просто перебираю эти коэффициенты.

Проверка

var options = GetAllOptions(10);
foreach(var option in options)
{
    var ret = Enumerable.Repeat(1, option.one)
        .Concat(Enumerable.Repeat(5, option.five))
        .Concat(Enumerable.Repeat(10, option.ten));
    Console.WriteLine(string.Join(" ", ret));
}

Вывод

1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 5
5 5
10

На С++ сами перепишите =)

БЛОГ НА HUSL

Размен. Алгоритмическая задача с хендбука Яндекс

Ответы (1 шт):