Question

В магазине продается мастика в ящиках по a кг (тип 1), b кг (тип 2) и c кг (тип 3). Как купить ровно N кг мастики, не вскрывая ящики? Сколькими способами можно это сделать? Входные данные Входная строка содержит четыре числа, разделённые пробелами: a , b , c и N . Выходные данные В первой строке нужно вывести число K способов, которыми можно купить заданное количество мастики ( N кг), не вскрывая ящики. В каждой из последующих K строчек программа должна вывести (через пробелы) три числа, k a , k b и k c : количество ящиков 1, 2 и 3 типов для каждого из K вариантов закупки. Варианты должны выводиться в лексикографическом порядке: сначала варианты с наименьшим значением k a , для одинаковых k a – сначала варианты с наименьшим значением k b и т.д. На C++

Answer 1

Ответ:

#include <iostream>

using namespace std;

int main() {

   int n, a, b, c, s = 0;

   cin >> a >> b >> c >> n;

   

   for (int na = 0; na <= n / a; na++) {

       for (int nb = 0; nb <= (n - a * na) / b; nb++) {

           int kk = n - na * a - nb * b;

           if (kk >= 0 and kk % c == 0) s++;        

       }

   }

   cout << s << endl;

   for (int na = 0; na <= n / a; na++) {

       for (int nb = 0; nb <= (n - a * na) / b; nb++) {

           int ll = n - na * a - nb * b;

           if (ll >= 0 and ll % c == 0)

               cout << na << " " << nb << " " << ll / c << endl;

       }

   }

}

Объяснение:

Зашло на 100 баллов

Answer 2

Для решения этой задачи можно воспользоваться жадным алгоритмом. Мы будем увеличивать количество ящиков каждого типа, начиная с нуля, и проверять, можем ли мы собрать ровно N кг мастики. Если да, то добавляем этот вариант в ответ. Важно учитывать, что нам нужно вывести варианты в лексикографическом порядке.

Вот пример реализации на C++:

cppCopy code
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int a, b, c, N;
    cin >> a >> b >> c >> N;

    vector<vector<int>> solutions;

    for (int ka = 0; ka * a <= N; ka++) {
        for (int kb = 0; kb * b <= N; kb++) {
            int remaining = N - ka * a - kb * b;
            if (remaining >= 0 && remaining % c == 0) {
                int kc = remaining / c;
                vector<int> solution = {ka, kb, kc};
                solutions.push_back(solution);
            }
        }
    }

    sort(solutions.begin(), solutions.end());

    cout << solutions.size() << endl;

    for (const vector<int>& solution : solutions) {
        cout << solution[0] << " " << solution[1] << " " << solution[2] << endl;
    }

    return 0;
}

Этот код сначала считывает входные данные (a, b, c и N), затем перебирает все возможные комбинации (ka, kb, kc) ящиков типов 1, 2 и 3 и проверяет, можно ли собрать ровно N кг мастики. Если да, то добавляет вариант в вектор решений. После этого сортирует решения и выводит их на экран.

Пример работы программы:

Copy code
Входные данные:
2 3 5 10

Выходные данные:
3
0 0 2
0 2 0
1 1 1

Программа нашла 3 способа купить 10 кг мастики, не вскрывая ящики.