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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
StoneGod
7 / 7 / 0
Регистрация: 23.10.2013
Сообщений: 52
#1

Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи - C++

11.07.2014, 06:31. Просмотров 854. Ответов 16
Метки нет (Все метки)

Здравствуйте, помогите с алгоритом, часов 15 думаю ни как придумать не могу. Можно просту идею с помощью которой решается.

Задача:
У Максима имеется A купюр по 10 рублей, B купюр по 50 рублей и C купюр по 100 рублей. В кафе Максиму и его девушке принесли счёт на сумму N рублей, а проезд в такси стоит M рублей. Помогите Максиму узнать, какую наименьшую сумму денег ему придётся потратить, если он будет отказываться от сдачи. Помните, что кафе и такси оплачиваются по отдельности.

Входные данные:
Первая строка содержит целые числа A, B, C (0 <= A, B, C <= 10) — количество имеющихся у Максима купюр по 10, 50 и 100 рублей соответственно. Вторая строка содержит целые числа N и M (1 <= N, M <= 600) — сумму в счёте кафе и цену такси соответственно.

Выходные данные:
Выведите единственное целое число — минимальное количество рублей, которое потребуется потратить Максиму.
Если Максим не сможет расплатиться предпочитаемым образом, выведите число -1.


Привер входных данных:
1 6 2
485 351

Пример выходных данных:
-1
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2014, 06:31     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи
Посмотрите здесь:

Найти сумму положительных элементов массива и узнать будет ли число простым, если округлить его до целого - C++
Только учусь писать программы, помогите найти ошибки в коде. Условие задачи: Найти сумму положительных элементов диагоналей массива...

Определить минимальную сумму которую придётся заплатить за трафик - C++
Здравствуйте! Объясните мне, пожалуйста, как надо решить данную задачу? Вот тз: В Москве начал работать новый оператор сотовой связи,...

Найти наименьшую четную цифру. Если ее нет, возвратить 0 - C++
1). Найти наименьшую четную цифру. Если ее нет, возвратить 0. помогите пожалуйста

Если первое число окажется кратным 5 или второе число будет нечетным, то вывести на экран сумму их модулей - C++
4. Даны два числа N и М. Если первое число окажется кратным 5 или второе число будет нечетным, то вывести на экран сумму модулей заданных...

Посчитать, сколько раз будет вызвана рекурсивная функция, если ей будет передан заданный аргумент - C++
int foo(int n) { if (n &lt;= 0) return 1; return foo((n * 2) / 3) + foo(n - 2); }Нужно посчитать, сколько всего раз...

Узнать, есть ли среди элементов массива элементы с нечетными номерами, которые кратны 17, и если есть, посчитать их сумму - C++
Проблема с заданием. Дан одномерный массив. Узнать, есть ли среди них элементы с нечетными номерами, которые кратны 17, и если есть,...

По заданному числу определить наименьшую сумму его делителей - C++
Есть у нас число. Допустим 12. Оно является НОК чисел 6 и 4, а также 6 4 1, 6 4 1 3 и т.д. Задача состоит в том, что нужно вывести...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nmcf
5276 / 4596 / 1541
Регистрация: 14.04.2014
Сообщений: 18,265
11.07.2014, 08:22     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #2
Делением суммы начиная с крупных номиналов и с учётом количества купюр.
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
11.07.2014, 08:26     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #3
Цитата Сообщение от nmcf Посмотреть сообщение
Делением суммы начиная с крупных номиналов и с учётом количества купюр.
Уверен что не упустишь оптимальный вариант?
nmcf
5276 / 4596 / 1541
Регистрация: 14.04.2014
Сообщений: 18,265
11.07.2014, 08:38     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #4
Сначала кафе, потом такси. Я так понял.
Trwsdf
Заблокирован
11.07.2014, 09:18     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int Calculate(int & a, int& b, int & c, const int & value) {
    for (int k = 0, s = 0; k <= c; k++)
        for (int j = 0; j <= b; j++)
            for (int i = 0; i <= a; i++)
                if ((s = i * 10 + j * 50 + k * 100) >= value) {
                    a -= i;
                    b -= j;
                    c -= k;
                    return s;
                };
    return -1;
}
 
int main(int argc, char** argv) {
 
    int A = (cin>>A, A), B = (cin>>B, B), C = (cin>>C, C), N = (cin>>N, N), M = (cin>>M, M);
    cout << "sum N " << Calculate(A, B, C, N) << endl;
    cout << "sum M " << Calculate(A, B, С, M) << endl;
    cout << "have " << A * 10 + B * 50 + C * 100;
    return 0;
}
Добавлено через 6 минут
p.s... теперь автор темы бесследно пропадет
StoneGod
7 / 7 / 0
Регистрация: 23.10.2013
Сообщений: 52
11.07.2014, 10:32  [ТС]     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #6
гениально, а я все время с 10 начанал думать, а оказалась надо было с 100.
Спасибо всем))
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
11.07.2014, 11:04     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #7
возможно это решение не оптимально. уверены что нету более оптимального расклада именно для 2х?
StoneGod
7 / 7 / 0
Регистрация: 23.10.2013
Сообщений: 52
11.07.2014, 11:08  [ТС]     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #8
решение не оптимально, так как программа не проходит тест

Тест:
Кликните здесь для просмотра всего текста

Входные данные:
5 5 5
500 222

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

а должно быть 750;


P.S. сейчас пытаюсь придумать как это исправить
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
11.07.2014, 11:14     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #9
Цитата Сообщение от StoneGod Посмотреть сообщение
P.S. сейчас пытаюсь придумать как это исправить
внутри ифа запускать такую же процедуру для такси, только в ней проверять все возможные варианты и запомнить наиболее оптимальный. и так для всех вариантов с кафе. но это не оптимальной решение в плане времени выполнения. но 100% дает наиболее оптимальный вариант
StoneGod
7 / 7 / 0
Регистрация: 23.10.2013
Сообщений: 52
11.07.2014, 11:20  [ТС]     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #10
Спасибо, сейчас опробуем)
Trwsdf
Заблокирован
11.07.2014, 14:37     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #11
Цитата Сообщение от Kukurudza Посмотреть сообщение
возможно это решение не оптимально. уверены что нету более оптимального расклада именно для 2х?
это решение оптимально. Именно потому, что Максим (или как там его) не знает какой у него будет счет за такси , при оплате счета в кафе.
А потому берет наименьшую сумму денег без сдачи, которая у него сейчас есть отдает в кафе. После получает счет за такси и делает тоже самое.

Если имелось ввиду, что у него уже два счета на руках и сумма денег, а ему нужно деньги сгруппировать так чтобы удачно расплотиться за оба счета - то это должно было указано быть в условии.
StoneGod
7 / 7 / 0
Регистрация: 23.10.2013
Сообщений: 52
11.07.2014, 15:16  [ТС]     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #12
Факт в том, что решение валится на кокомто из тестов (что это за тест я понятия не имею), но при этом есть люди решившие эту задачу.
P.S. щас напишу создателям задачи по этому поводу
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
11.07.2014, 15:28     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #13
Сообщение было отмечено автором темы, экспертом или модератором как ответ
StoneGod, я не понял, а че такое не проходит???

C++ (Qt)
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
 
#include <iostream>
#include <algorithm>
#include <string>
 
using namespace std;
 
int main()
{
    int a, b, c;
    int n, m;
    cin >> a >> b >> c;
    cin >> n >> m;
    int ans = int(1e9);
 
    for(int i1 = 0; i1 <= 10; i1++)
        for(int j1 = 0; j1 <= 10; j1++)
            for(int k1 = 0; k1 <= 10; k1++)
                for(int i2 = 0; i2 <= 10; i2++)
                    for(int j2 = 0; j2 <= 10; j2++)
                        for(int k2 = 0; k2 <= 10; k2++)
                        {
                            if(i1 + i2 > a || j1 + j2 > b || k1 + k2 > c)
                                continue;
                            int s1 = i1 * 10 + j1 * 50 + k1 * 100;
                            int s2 = i2 * 10 + j2 * 50 + k2 * 100;
                            if(s1 >= n && s2 >= m)
                                ans = min(ans, s1 + s2);
                        }
 
    if(ans == int(1e9))
        ans = -1;
    cout << ans << endl;
    return 0;
}
StoneGod
7 / 7 / 0
Регистрация: 23.10.2013
Сообщений: 52
11.07.2014, 15:44  [ТС]     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #14
Спасибо, данное решение прошло все тесты. Но можете пояснить почему циклы до 10. И вот эту строчку:
C++ (Qt)
1
2
if(i1 + i2 > a || j1 + j2 > b || k1 + k2 > c)
                                continue;
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.07.2014, 16:32     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи
Еще ссылки по теме:

Заменить строку матрицы, имеющую наименьшую сумму, на элементы главной диагонали - C++
Дана прямоугольная матрица. Заменить строку, имеющую наименьшую сумму, на элементы главной диагонали.

Найти наименьшую сумму квадратов двух результатов измерений с интервалом в 5 элементов - C++
На вход программы подаются результаты измерений, выполняемых прибором с интервалом 1 минуту. Все данные – натуральные числа, не...

Заменить строку матрицы, имеющую наименьшую сумму, на элементы главной диагонали - C++
Дана прямоугольная матрица. Заменить строку, имеющую наименьшую сумму, на элементы главной диагонали.

Заменить строку матрицы, имеющую наименьшую сумму, на элементы главной диагонали - C++
Дана прямоугольная матрица. Заменить строку, имеющую наименьшую сумму, на элементы главной диагонали.

Отправить несколько бандеролей за минимальную сумму денег - C++
Нужно скомпилировать в C++!!! Кто-нибудь может помочь с моей практикой? Для подготовки заключительного этапа Russian Code Cup...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Qwertiy
818 / 626 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
11.07.2014, 16:32     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #15
Цитата Сообщение от StoneGod Посмотреть сообщение
Можно просту идею с помощью которой решается.
Просто перебор. Числа мелкие там.
Yandex
Объявления
11.07.2014, 16:32     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru