Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 06.05.2018, 08:03   #1
IIISergeyIII
Новичок
Джуниор
 
Регистрация: 06.05.2018
Сообщений: 1
По умолчанию Задача C++ Необходимо выложить бордюр длины N, использую до 2 кирпичей каждого вида M.

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

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

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

Необходимо выложить бордюр длины 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;

int comp (const void * a, const void * b)
{
  return ( *(long long*)b - *(long long*)a );
}

int main()
{
    long long n, m;
    cin >> n >> m;

    long long br[m*2];
    vector<long long> used;
    long long k = 0, L = 0;
    long long sum = 0, t = 0;


    for (int i = 0; i < m*2; i+=2) {
        t = 0;
        cin >> t;
        br[i] = t;
        br[i+1] = t;
        sum += t*2;
    }

    //sort(br.begin(), br.end(), greater<int> ());
    qsort (br, m*2, sizeof(long long), comp);

    if (n < sum) {
        for (long long i = 0; i < m*2; i++) {
            for (long long j = i; j < m*2; j++) {
                if (br[j] <= (n-L) ) {
                    used.push_back(br[j]);
                    k++;
                    L += br[j];
                    //cout << "L " << L << endl;
                    //cout << k << " " << br[j] << " L " << L << endl;
                    //cout << "i " << i << " j " << j << endl;
                }
                if (L == n) {
                    break;
                }
            }
            if (L == n) {
                break;

            } else {
                k = 0;
                L = 0;
                used.clear();
            }
        }
        if (L == n) {
            cout << k << endl;
            for (long long d = 0; d < k; d++) {
                cout << used[d] << " ";
            }
        } else {
            cout << "0";
        }
    } else if (n == sum) {
        cout << m*2 << endl;
        for (long long d = 0; d < m*2; d++) {
            cout << br[d] << " ";
        }
    } else {
        cout << "-1";
    }


    return 0;
}
IIISergeyIII вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
По последовательности длины n вида.. Rosana C++ Builder 1 08.03.2017 13:42
Помогите решить задачу через цикл For. загрузить грузовик грузоподъемностью Р тонн контейнерами трех видов: по А, В и С кг. Определить, какое количество контейнеров каждого вида Belzan Паскаль, Turbo Pascal, PascalABC.NET 1 02.12.2016 09:31
Каждый из двух земельных участков в форме равнобедренных треугольников задан , если для каждого заданы длины основания и боковой с Vadim228 Паскаль, Turbo Pascal, PascalABC.NET 0 22.12.2015 22:38
Дана база данных некоторого акционерного предприятия. Поля : ФИО Акционера, список акций(кол-во, стоимость каждого вида акций)Сост ANTON1994 Паскаль, Turbo Pascal, PascalABC.NET 6 04.03.2013 15:55
Дескрипторы потоков - Для каждого элемента списка необходимо создать поток, выполняющий требуемые функции kdv0403 Общие вопросы Delphi 2 09.06.2007 11:12