Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 193187
06.05.2018, 08:13
0.00 руб.
0 0 0
Компьютеры Программирование
Добрый день.
Уважаемые эксперты, у меня возникли сложности со следующей задачей.
Прошу вашей помощи.

Задача не проходит один из тестов проверяющей системы. Помогите, пожалуйста, найти возможную ошибку.

Условие задачи:

Необходимо выложить бордюр длины N, использую до 2 кирпичей каждого вида M.

Формат ввода
Сначала вводится число N (1 ≤ N ≤ 10^9), затем — число M (1 ≤ M ≤ 15) и далее M попарно различных чисел A1, A2, …, AM (1 ≤ Ai ≤ 10^9).

Формат вывода
Выведите сначала K — количество кипричей, которое нужно использовать для выкладывания бордюра, если можно выложить бордюр длиной ровно N. Далее выведите K чисел, задающих длины использованных кирпичей. Если решений несколько, выведите вариант, в котором использует наименьшее количество кирпичей. Если таких вариантов несколько, выведите любой из них.
Если для выкладывания бордюра придется обязательно разломить какой-то кирпич, то выведите одно число 0. Если же не хватит кипричей, чтобы выложить бордюр, выведите одно число –1 (минус один).

Код:

    #include <iostream>
    #include <cmath>
    #include <algorithm>
    #include <math.h>
    #include <vector>
    #include <fstream>
 
    using namespace std;
    
    bool comp(int a, int b) {
        return -(a-b);
    }
    
    void write(vector<long long> a) {
        for (int i = 0; i < a.size(); i++) {
            cout << a[i] << " ";
        }
    }
    
    int main()
    {
        long long n, m;
        long long L = 0;
        long long sum = 0;
        long long k = 0;
        vector<long long> used;
        vector<long long> br;
    
        cin >> n >> m;
        for (long long i = 0; i < m; i++) {
            long long t;
            cin >> t;
            br.push_back(t);
            br.push_back(t);
            sum += t*2;
        }
    
        sort(br.begin(), br.end(), greater<int>());
    
        if (n < sum) {
            for (int j = 0; j < br.size(); j++) {
                for (int i = j; i < br.size(); i++) {
    
                    if ( br[i] <= (n-L) ) {
                        used.push_back(br[i]);
                        L += br[i];
                        k++;
                    }
                    if (L == n) break;
                }
                if (L == n) {
                    break;
                } else {
                    k = 0;
                    L = 0;
                    used.clear();
                }
            }
    
    
            if (L == n) {
                cout << k << endl;
                write(used);
            } else {
                cout << 0;
            }
        } else if (n == sum) {
            cout << m*2 << endl;
            write(br);
        } else {
            cout << -1;
        }
    
    
    
        return 0;
    }

Обсуждение

Форма ответа