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

@Prolamer · Регистрация: 24.01.2016

Студворк — интернет-сервис помощи студентам

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

Фирма 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;
}

проблема заключается в том, что этот код проходит не все тесты(скрин прилагется)
объясните , пожалуйста, в чём может быть проблема?
спасибо за внимание

@_Valera_ · 29.01.2016, 10:59

Сообщение от Prolamer

установить равной пяти ужикам

чего монет или бумажек?

Сообщение от Prolamer

монеты или купюры,

это при тем что у нас есть 10 - монетная и 10 - купюрная единица, как отличать?

Сообщение от Prolamer

В первом примере одна монета в пять ужиков потребуется для сдачи первом программисту

почему, если он кинул 5 при том что напиток стоит 5? А это не то, где вобще первый пример?

Сообщение от Prolamer

arr[i+1];

тут выход за массив

Сообщение от Prolamer

otv = five - (arr[i] / 5 -1);

может нужно посчитать сколько всего денег ввели, потом найти из этого сколько должно быть выдано сдачи, потом еще вычесть количество оплат 5-монетами. и останется сколько нужно положить в автомат, то есть ответ.

@Prolamer · 29.01.2016, 11:03 **[ТС]**

извините, тупанул
примеры

@Dimension · 29.01.2016, 11:06

вы я вижу хотите что бы за вас всю олимпиаду решили?

@Prolamer · 29.01.2016, 11:08 **[ТС]**

Сообщение от Dimension

вы я вижу хотите что бы за вас всю олимпиаду решили?

извините, но я спрашиваю, потому что у меня возникают проблемы
обратиться больше не к кому
к тому же я пишу свой код, чтобы кто-то проверил что не так...

@_Valera_ · 29.01.2016, 11:16

Сообщение от Dimension

вы я вижу хотите что бы за вас всю олимпиаду решили?

у него хоть код есть, свой. И скрин прикладывать не надо)

Сообщение от Prolamer

примеры

ну смысл тот же что и в первом ответе

@vndtta · 29.01.2016, 12:14

в программе нет счетчика купюр, если можно давать сдачу купюрами, то не нужно использовать монеты, так можно отсчитать монет больше чем требуется, например вариант
4
10 10 50 100

Добавлено через 30 минут
в общем прочитал условие внимательней,
в коде есть увеличение монет, когда автомат их принимает, но нет уменьшения, когда автомат их выдает
пример:
5
5 10 10 10 10

@_Scorpius_ · 29.01.2016, 14:14

Как вариант:

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;
}

Работу с файлами сам реализуешь

Новые блоги и статьи Все статьи Все блоги /
Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025

@Prolamer 0 / 0 / 0 Регистрация: 24.01.2016 Сообщений: 17
	29.01.2016, 11:03 [ТС]
	извините, тупанул примеры Миниатюры 0

@Dimension Dimension 595 / 463 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	29.01.2016, 11:06
	вы я вижу хотите что бы за вас всю олимпиаду решили? 0

@vndtta 93 / 69 / 22 Регистрация: 17.10.2011 Сообщений: 235
	29.01.2016, 12:14
	в программе нет счетчика купюр, если можно давать сдачу купюрами, то не нужно использовать монеты, так можно отсчитать монет больше чем требуется, например вариант 4 10 10 50 100 Добавлено через 30 минут в общем прочитал условие внимательней, в коде есть увеличение монет, когда автомат их принимает, но нет уменьшения, когда автомат их выдает пример: 5 5 10 10 10 10 1

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

Решение