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

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

Войти
Регистрация
Восстановить пароль
 
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
#1

Определить минимальное количество монет, которое должно находиться в автомате, чтобы всем хватило сдачи - C++

29.01.2016, 10:29. Просмотров 539. Ответов 7
Метки нет (Все метки)

Здравствуйте.
Не первый раз создаю тему об олимпиадных задачах , думаю, и не последнюю))
Возникла проблема со следующей задачей:

Фирма bookface, созданная в Ужляндии, в которой работает Степан, решила установить в своих офисах автоматы по продаже чая и кофе, чтобы программисты во время перерыва могли с толком провести время.
Стоимость стакана чая и кофе в автомате предполагается установить равной пяти ужикам (такая в Ужляндии валюта). Автоматы будут принимать монеты по 5 и 10 ужиков, а также купюры в 10, 50 и 100 ужиков. Когда программисту нужно выдавать сдачу (т.е. когда программист бросил в автомат монету в 10 ужиков, или купюру в 10, 50 или 100 ужиков), автомат выдает сдачу монетами в пять ужиков; если же пассажир бросил в автомат монету в пять ужиков, то автомат ее сохраняет и может использовать для сдачи следующим программистам.
Очевидно, что, чтобы обеспечить возможность выдачи сдачи всем программистам, может потребоваться сначала загрузить в автомат некоторое количество монет в пять ужиков. Сейчас в офисах фирмы проходят испытания с целью определить минимальное количество монет, которые надо загрузить в автомат перед рабочим днем.
Вам дано протокол одного из таких испытаний: известный порядок, в котором программисты оплачивали свои покупки различными монетами и купюрами. Определите, какое минимальное количество монет в пять ужиков, должно было сначала находиться в автомате, чтобы всем пассажирам хватило сдачи.

Входные данные:
В первой строке входного файла находится одно натуральное число N - количество покупок в автомате, которые были осуществлены в ходе испытания (1 ≤ N ≤ 50000). Во второй строке находятся N натуральных чисел, каждое из которых равно номинала монеты или купюры, которую использовал очередной программист для оплаты; каждый номинал может принимать одно из четырех значений: 5, 10, 50 или 100.

Исходные данные:
В выходной файл выведите одно число - минимальное количество монет в пять Ужик, которые надо было загрузить в автомат сначала, чтобы всем программистам хватило сдачи.

Примечание:
В первом примере одна монета в пять ужиков потребуется для сдачи первом программисту и 19 монет - третьему, но при сдаче третьей можно использовать ту монету, которую бросит второй программист, поэтому сначала в автомате достаточно 19 монет.
Во втором примере сдачу третьему программисту можно выдать, используя монету первого или второго покупателя, и поэтому не нужно загружать монеты в автомат сначала.
В третьем примере первому программисту нужны девять монет сдачи, и все они должны сначала находится в автомате.


мой код:
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
#include <iostream>
#include <fstream>
using namespace std;
int main(){
    int five = 0;
    int k0 = 0;
    int otv;
    int n;
    ifstream fin("testing.in");
    fin >> n;
    int arr[n];
    for(int i = 0; i < n; i++){
        fin >> arr[i+1];
    }
    for(int i = 1; i <= n; i++){
        if(arr[i]==5){
            five++;
        }
 
        otv = five - (arr[i] / 5 -1);
        if(otv < 0){
            k0 += -otv;
        }
 
    }
    ofstream fout("testing.out");
    fout << k0;
    return 0;
}
проблема заключается в том, что этот код проходит не все тесты(скрин прилагется)
объясните , пожалуйста, в чём может быть проблема?
спасибо за внимание
0
Миниатюры
Определить минимальное количество монет, которое должно находиться в автомате, чтобы всем хватило сдачи  
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.01.2016, 10:29
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Определить минимальное количество монет, которое должно находиться в автомате, чтобы всем хватило сдачи (C++):

Минимальное количество долек апельсина, чтобы всем досталось поровну - C++
Катя решила пригласить к себе в гости n друзей. Так как ее друзья очень любят фрукты, то в качестве угощения для них она купила m...

Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в n гривен - C++
В банкомате имеются в достаточном количестве купюры номиналом 10, 20, 50, 100, 200 и 500 гривен. Найти минимальное количество купюр,...

Найти минимальное количество шариков, которое необходимо перекрасить, чтобы все шарики были одного цвета - C++
Написал код для одной задачи. Ответ выдает он вроде правильный. Но на сайте при тестировании моего алгоритма, он проходит тест на 31%...

Какое минимальное число монет нужно перевернуть, чтобы все монеты лежали одинаковой стороной вверх? - C++
Всем привет прошу помощи или же направления в решение задачи! 1) На столе лежат n монеток. Некоторые из них лежат вверх решкой, а...

Определить минимальное число и номиналы банкнот и монет, необходимые для набора заданной суммы - C++
Имеется сумма в некоторой денежной системе. Определить минимальное число и номиналы банкнот и монет, необходимые для набора этой суммы. ...

Определить минимальное количество символов, которые нужно добавить в строку, чтобы получить палиндром - C++
Определить минимальное количество символов, которые нужно добавить в строку, чтобы получить палиндром например: ввод aziz ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
_Valera_
487 / 369 / 94
Регистрация: 27.01.2015
Сообщений: 1,588
29.01.2016, 10:59 #2
Цитата Сообщение от Prolamer Посмотреть сообщение
установить равной пяти ужикам
чего монет или бумажек?

Цитата Сообщение от Prolamer Посмотреть сообщение
монеты или купюры,
это при тем что у нас есть 10 - монетная и 10 - купюрная единица, как отличать?

Цитата Сообщение от Prolamer Посмотреть сообщение
В первом примере одна монета в пять ужиков потребуется для сдачи первом программисту
почему, если он кинул 5 при том что напиток стоит 5? А это не то, где вобще первый пример?

Цитата Сообщение от Prolamer Посмотреть сообщение
arr[i+1];
тут выход за массив

Цитата Сообщение от Prolamer Посмотреть сообщение
otv = five - (arr[i] / 5 -1);
может нужно посчитать сколько всего денег ввели, потом найти из этого сколько должно быть выдано сдачи, потом еще вычесть количество оплат 5-монетами. и останется сколько нужно положить в автомат, то есть ответ.
1
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
29.01.2016, 11:03  [ТС] #3
извините, тупанул
примеры
0
Миниатюры
Определить минимальное количество монет, которое должно находиться в автомате, чтобы всем хватило сдачи  
Dimension
Dimension
556 / 437 / 135
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
29.01.2016, 11:06 #4
вы я вижу хотите что бы за вас всю олимпиаду решили?
0
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
29.01.2016, 11:08  [ТС] #5
Цитата Сообщение от Dimension Посмотреть сообщение
вы я вижу хотите что бы за вас всю олимпиаду решили?
извините, но я спрашиваю, потому что у меня возникают проблемы
обратиться больше не к кому
к тому же я пишу свой код, чтобы кто-то проверил что не так...
0
_Valera_
487 / 369 / 94
Регистрация: 27.01.2015
Сообщений: 1,588
29.01.2016, 11:16 #6
Цитата Сообщение от Dimension Посмотреть сообщение
вы я вижу хотите что бы за вас всю олимпиаду решили?
у него хоть код есть, свой. И скрин прикладывать не надо)

Цитата Сообщение от Prolamer Посмотреть сообщение
примеры
ну смысл тот же что и в первом ответе
1
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 1
29.01.2016, 12:14 #7
в программе нет счетчика купюр, если можно давать сдачу купюрами, то не нужно использовать монеты, так можно отсчитать монет больше чем требуется, например вариант
4
10 10 50 100

Добавлено через 30 минут
в общем прочитал условие внимательней,
в коде есть увеличение монет, когда автомат их принимает, но нет уменьшения, когда автомат их выдает
пример:
5
5 10 10 10 10
1
_Scorpius_
49 / 49 / 24
Регистрация: 01.04.2015
Сообщений: 104
29.01.2016, 14:14 #8
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Как вариант:
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
#include <iostream>
#include <fstream>
 
using namespace std;
 
int main()
{
    int five = 0, k0 = 0;
    const int n = 3;
    int arr[n] = {10, 5, 100};
//    int arr[n] = {5, 5, 10};
//    int arr[n] = {50, 5, 5};
 
    for(int i = 0; i < n; ++i)
    {
        if(arr[i] != 5)
            five += arr[i] / 5 - 1;
        else
            --five;
 
        if (five > k0)
            k0 = five;
    }
 
    if (k0 <= 0)
        k0 = 0;
    cout << k0 << endl;
 
    return 0;
}
Работу с файлами сам реализуешь
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.01.2016, 14:14
Привет! Вот еще темы с ответами:

Определить минимальное количество символов, которые нужно добавить в строку, чтобы получить палиндром - C++
Здравствуйте, помогите пожалуйсто, был бы очень признателен хотя бы за идею решения(поидеи методом ветвей и границ она решается) ...

Минимальное количество байт, которое займёт отрицательное число - C++
Нужно узнать минимальное количество байт, которое займёт число. То есть в int у нас может быть число и 256 (00000001 00000000), которое...

Определить минимальное число пирамид которое требуется сложить - C++
Капитан Вася всегда держит на своем корабле запас пушечных ядер для борьбы с пира- тами. Так как он привык во всем поддерживать порядок,...

Определить наименьшее время, которое должно пройти до того момента, когда часовая и минутная стрелки совпадут - C++
1) Даны целые числа M и N (0&lt;M&lt;=12, 0&lt;=N&lt;=60), указывающие момент времени: «M часов, N минут». Определить наименьшее время (число полных...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
29.01.2016, 14:14
Ответ Создать тему
Опции темы

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