Задача "Испытание автомата"
Компания Bookface, основанная в Ужляндии, где работает Степан, решила установить в своих офисах автоматы по продаже чая и кофе, чтобы программисты могли с пользой провести время во время перерывов. Стоимость стаканчика чая или кофе в автомате установлена равной пяти ужикам (местная валюта Ужляндии). Автоматы принимают монеты по 5 и 10 ужиков, а также купюры номиналом 10, 50 и 100 ужиков.
Если программисту необходимо дать сдачу (то есть он оплатил монетой 10 ужиков или купюрой 10, 50, 100 ужиков), автомат выдает сдачу монетами по 5 ужиков. Если программист заплатил монетой в 5 ужиков, автомат сохраняет её и может использовать для сдачи следующим покупателям.
Очевидно, что для обеспечения возможности выдачи сдачи всем программистам потребуется заранее загрузить в автомат некоторое количество монет номиналом 5 ужиков. Известен порядок, в котором программисты производили оплату. Ваша задача — определить минимальное количество монет номиналом 5 ужиков, которые нужно было загрузить в автомат перед началом рабочего дня, чтобы всем покупателям хватило сдачи.
Входные данные:
- В первой строке входного файла дано одно натуральное число N — количество покупок, совершенных в ходе испытания (1≤N≤50,000).
- Во второй строке записаны N натуральных чисел, каждое из которых соответствует номиналу монеты или купюры, которую использовал очередной программист для оплаты (5,10,50,100).
Выходные данные:
Выведите одно число — минимальное количество монет номиналом 5 ужиков, которые нужно загрузить в автомат перед началом рабочего дня.
Примеры ввода и вывода данных:
Код решения задача на С++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n; // Количество покупок
cin >> n;
vector<int> payments(n); // Массив для хранения номиналов оплат
for (int i = 0; i < n; ++i) {
cin >> payments[i];
}
int coins_in_machine = 0; // Текущее количество монет в автомате
int min_initial_coins = 0; // Минимальное начальное количество монет
for (int payment : payments) {
if (payment == 5) {
// Если программист платит монетой 5 ужиков
coins_in_machine += 1;
} else {
// Расчёт сдачи
int change_needed = (payment - 5) / 5;
if (coins_in_machine >= change_needed) {
// Если в автомате хватает монет на сдачу
coins_in_machine -= change_needed;
} else {
// Если не хватает монет, нужно добавить в автомат
min_initial_coins += change_needed - coins_in_machine;
coins_in_machine = 0; // Использовали все монеты
}
}
}
cout << min_initial_coins << endl; // Вывод минимального количества монет
return 0;
}