С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

11.07.2014, 06:31. Просмотров 921. Ответов 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
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2014, 06:31
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи (C++):

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

Какую сумму необходимо потратить на ремонт, если цена одного рулона обоев K руб? - Pascal ABC
Хозяин хочет оклеить обоями длинную стену в своем доме. Длина этой стены равна A и высота B. В рулоне 12 м обоев шириной 1 м. Какую сумму...

Способы потратить определенную сумму денег определенными монетами - Visual Basic .NET
У Вас А монет по Х рублей и В монет по Y рублей. Можно ли с их помощью заплатить Z рублей, если да - то как? Если можно то с...

Запишите минимальное количество монет, которое придется отдать продавцу, если у него не будет сдачи - C#
Когда Маша и Витя покупали подарок, возникла интересная ситуация. У них была в распоряжении только одна большая купюра, а у продавца –...

Как изменится предложение денег, если возможности банковской системы по созданию денег используются полностью. - Экономика
Вопрос (e13): Проводя политику дешевых денег, ЦБ выкупает ранее проданные облигации на сумму 100 млн. руб., в т.ч. у коммерческих банков на...

Создайте приложение, позволяющее вычислять сколько денег должен сдать для сдачи продавец - Visual Basic .NET
Я совсем новичок в программировании:-| Задача: Создайте приложение, позволяющее вычислять сколько денег должен сдать для сдачи продавец...

16
nmcf
5705 / 5016 / 1713
Регистрация: 14.04.2014
Сообщений: 20,492
11.07.2014, 08:22 #2
Делением суммы начиная с крупных номиналов и с учётом количества купюр.
1
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
11.07.2014, 08:26 #3
Цитата Сообщение от nmcf Посмотреть сообщение
Делением суммы начиная с крупных номиналов и с учётом количества купюр.
Уверен что не упустишь оптимальный вариант?
1
nmcf
5705 / 5016 / 1713
Регистрация: 14.04.2014
Сообщений: 20,492
11.07.2014, 08:38 #4
Сначала кафе, потом такси. Я так понял.
1
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... теперь автор темы бесследно пропадет
1
StoneGod
7 / 7 / 0
Регистрация: 23.10.2013
Сообщений: 52
11.07.2014, 10:32  [ТС] #6
гениально, а я все время с 10 начанал думать, а оказалась надо было с 100.
Спасибо всем))
0
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
11.07.2014, 11:04 #7
возможно это решение не оптимально. уверены что нету более оптимального расклада именно для 2х?
1
StoneGod
7 / 7 / 0
Регистрация: 23.10.2013
Сообщений: 52
11.07.2014, 11:08  [ТС] #8
решение не оптимально, так как программа не проходит тест

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

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

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

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


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

Если имелось ввиду, что у него уже два счета на руках и сумма денег, а ему нужно деньги сгруппировать так чтобы удачно расплотиться за оба счета - то это должно было указано быть в условии.
1
StoneGod
7 / 7 / 0
Регистрация: 23.10.2013
Сообщений: 52
11.07.2014, 15:16  [ТС] #12
Факт в том, что решение валится на кокомто из тестов (что это за тест я понятия не имею), но при этом есть люди решившие эту задачу.
P.S. щас напишу создателям задачи по этому поводу
0
SlavaSSU
216 / 161 / 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;
}
1
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;
0
Qwertiy
821 / 629 / 75
Регистрация: 20.08.2013
Сообщений: 2,524
11.07.2014, 16:32 #15
Цитата Сообщение от StoneGod Посмотреть сообщение
Можно просту идею с помощью которой решается.
Просто перебор. Числа мелкие там.
0
11.07.2014, 16:32
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.07.2014, 16:32
Привет! Вот еще темы с ответами:

.NET 4.x Какую БД использовать, если учесть, что записей будет свыше 4 500 000 - Visual Basic .NET
Пишу программу для архива организации. Конкретно нужно сделать выборку для пенсионного фонда по зарплате за определенный период. Вопрос:...

Определить, кто на какую оценку может написать контрольную, если будет писать самостоятельно - Turbo Pascal
На контрольной работе N учеников сидят в ряд. Для каждого ученика известно, какую оценку он получил бы, если бы писал эту контрольную...

Какая сумма будет подарена на каждый день рождения до совершеннолетия? Сколько всего денег будет подарено? - Turbo Pascal
мой богатый дядюшка подарил мне доллар на день рождения. в каждый следующий день рождения он удваивал свой подарок и прибавлял к нему...

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


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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