Форум программистов, компьютерный форум CyberForum.ru

Ребята немогу понять задачу на С++ - C++

Восстановить пароль Регистрация
 
k700a
0 / 0 / 0
Регистрация: 09.11.2013
Сообщений: 6
09.11.2013, 16:29     Ребята немогу понять задачу на С++ #1
В волшебной стране используются монетки достоинством A1, A2,..., AM. волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Входные данные

Во входном файле INPUT.TXT записано сначала число N (1 <= N <= 109), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A1, A2,..., AM (1 <= Ai <= 109).

Выходные данные

В выходной файл OUTPUT.TXT выведите количество монет, которое придется отдать волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Если решений несколько, выведите вариант, в котором волшебный человек отдаст наименьшее возможное количество монет. Если без сдачи не обойтись, то выведите одно число 0. Если же у волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).

Примеры

№ INPUT.TXT OUTPUT.TXT
1 5 2
1 2 3
2 7 2
1 2 -1
3 5 2
3 4 0




http://********/index.asp?main=task&id_task=153









Буду очень благодарен если разъясните или поможете с задачей.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.11.2013, 16:29     Ребята немогу понять задачу на С++
Посмотрите здесь:

C++ Немогу понять почему в программе выкидует ошибка
C++ Немогу понять как реализовать
Немогу понять в чем ошибка. C++
C++ Немогу понять в чем ошибка (
C++ Немогу понять в чем ошибка.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
09.11.2013, 18:24     Ребята немогу понять задачу на С++ #2
k700a, Вам не понятна суть задачи или решение?
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
09.11.2013, 18:44     Ребята немогу понять задачу на С++ #3
Задача на динамическое программирование (google it).
Однако, вопрос в другом! Зачем решать задачи асмр, если за тебя их решает форум? Это ж дело добровольное!
k700a
0 / 0 / 0
Регистрация: 09.11.2013
Сообщений: 6
09.11.2013, 20:36  [ТС]     Ребята немогу понять задачу на С++ #4
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Задача на динамическое программирование (google it).
Однако, вопрос в другом! Зачем решать задачи асмр, если за тебя их решает форум? Это ж дело добровольное!
ну чтоб объяснили я хотел

Добавлено через 19 секунд
Цитата Сообщение от jambas92 Посмотреть сообщение
k700a, Вам не понятна суть задачи или решение?
суть)
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
10.11.2013, 19:00     Ребята немогу понять задачу на С++ #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
 
using namespace std;
 
int main() {
 
    int n, m;
    int *mas, *mas2;
    int count = 0;
    bool flag = false;
 
    cin >> n >> m;
    mas = new int[m];
    mas2 = new int[m];
 
    for (int i=0; i<m; i++) {
        cin >> mas[i];
        mas2[i] = mas[i] * 2;
    }
 
    for (int i=0; i<m-1; i++) {
        for (int j=i+1; j<m; j++) {
            if (mas[i] > mas[j]) {
                swap(mas[i], mas[j]);
                swap(mas2[i], mas2[j]);
            }
        }
    }
 
    for (int i=0; i<m; i++) {
        if (mas[i] == n) {
            cout << 1;
            exit(0);
        }
        if (mas2[i] == n) {
            cout << 2;
            exit(0);
        }
    }
    
    for (int i=0; i<m-1; i++) {
        if (mas[i] + mas[i+1] == n) {
            cout << 2;
            exit(0);
        }
        if (mas2[i] + mas2[i+1] == n) {
            cout << 4;
            exit(0);
        }
        if (mas[i] + mas[i+1] > n) {
            flag = true;
        }
        if (mas2[i] + mas2[i+1] > n) {
            flag = true;
        }
    }
 
    for (int i=0; i<m; i++) {
        for (int j=0; j<m; j++) {
            if (i == j) {
                continue;
            }
            if (mas[i] + mas2[j] == n) {
                cout << 3;
                exit(0);
            }
        }
    }
 
    if (flag) {
        cout << 0;
    } else {
        cout << -1;
    }
    
    
    system("pause");
}
Yandex
Объявления
10.11.2013, 19:00     Ребята немогу понять задачу на С++
Ответ Создать тему
Опции темы

Текущее время: 06:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru