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

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

Восстановить пароль Регистрация
 
StoneGod
6 / 6 / 0
Регистрация: 23.10.2013
Сообщений: 48
11.07.2014, 06:31     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #1
Здравствуйте, помогите с алгоритом, часов 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++ Какую площадь и периметр будет квадрат, описанный вокруг круга заданной площади S
МАСИИВЫ, найти сумму каждого рядка матрицы та наименьшую из них! не могу другую часть программы сделать.. C++
По заданному числу определить наименьшую сумму его делителей C++
Заданную сумму денег выразить минимальным количеством банкнот по 500, 100, 10, 5, 2 и 1 рублю C++
C++ Узнать, есть ли среди элементов массива элементы с нечетными номерами, которые кратны 17, и если есть, посчитать их сумму
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nmcf
4259 / 3690 / 1243
Регистрация: 14.04.2014
Сообщений: 14,458
11.07.2014, 08:22     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #2
Делением суммы начиная с крупных номиналов и с учётом количества купюр.
Kukurudza
104 / 85 / 6
Регистрация: 29.08.2012
Сообщений: 539
11.07.2014, 08:26     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #3
Цитата Сообщение от nmcf Посмотреть сообщение
Делением суммы начиная с крупных номиналов и с учётом количества купюр.
Уверен что не упустишь оптимальный вариант?
nmcf
4259 / 3690 / 1243
Регистрация: 14.04.2014
Сообщений: 14,458
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
6 / 6 / 0
Регистрация: 23.10.2013
Сообщений: 48
11.07.2014, 10:32  [ТС]     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #6
гениально, а я все время с 10 начанал думать, а оказалась надо было с 100.
Спасибо всем))
Kukurudza
104 / 85 / 6
Регистрация: 29.08.2012
Сообщений: 539
11.07.2014, 11:04     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #7
возможно это решение не оптимально. уверены что нету более оптимального расклада именно для 2х?
StoneGod
6 / 6 / 0
Регистрация: 23.10.2013
Сообщений: 48
11.07.2014, 11:08  [ТС]     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #8
решение не оптимально, так как программа не проходит тест

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

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

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

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


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

Если имелось ввиду, что у него уже два счета на руках и сумма денег, а ему нужно деньги сгруппировать так чтобы удачно расплотиться за оба счета - то это должно было указано быть в условии.
StoneGod
6 / 6 / 0
Регистрация: 23.10.2013
Сообщений: 48
11.07.2014, 15:16  [ТС]     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #12
Факт в том, что решение валится на кокомто из тестов (что это за тест я понятия не имею), но при этом есть люди решившие эту задачу.
P.S. щас напишу создателям задачи по этому поводу
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
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
6 / 6 / 0
Регистрация: 23.10.2013
Сообщений: 48
11.07.2014, 15:44  [ТС]     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #14
Спасибо, данное решение прошло все тесты. Но можете пояснить почему циклы до 10. И вот эту строчку:
C++ (Qt)
1
2
if(i1 + i2 > a || j1 + j2 > b || k1 + k2 > c)
                                continue;
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
11.07.2014, 16:32     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #15
Цитата Сообщение от StoneGod Посмотреть сообщение
Можно просту идею с помощью которой решается.
Просто перебор. Числа мелкие там.
Trwsdf
Заблокирован
11.07.2014, 17:22     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #16
Цитата Сообщение от StoneGod Посмотреть сообщение
Факт в том, что решение валится на кокомто из тестов (что это за тест я понятия не имею), но при этом есть люди решившие эту задачу.
P.S. щас напишу создателям задачи по этому поводу
Понимаю, не ваша вина в идиотских условиях задач.
могу переделать, так, чтобы Ваня знал обе цены заранее, которые ему надо будет заплатить и распределял по очереди свои деньги наиболее оптимально для обоих плат.
Но теперь не бесплатно.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.07.2014, 22:25     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи
Еще ссылки по теме:

Найти наименьшую четную цифру. Если ее нет, возвратить 0 C++
Найти наименьшую сумму квадратов двух результатов измерений с интервалом в 5 элементов C++
Отправить несколько бандеролей за минимальную сумму денег C++

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

Или воспользуйтесь поиском по форуму:
Kukurudza
104 / 85 / 6
Регистрация: 29.08.2012
Сообщений: 539
11.07.2014, 22:25     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи #17
Цитата Сообщение от Trwsdf Посмотреть сообщение
это решение оптимально. Именно потому, что Максим (или как там его) не знает какой у него будет счет за такси , при оплате счета в кафе.
плевать что знает Максим, по условию задачи вам сразу же даны оба счета. отсюда и считайте.
Yandex
Объявления
11.07.2014, 22:25     Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи
Ответ Создать тему
Опции темы

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