Задачи
November 12, 2021
Задача. Сдача от кваса
Задача: В киоске стакан кваса стоит 5 рублей. Дети стоят в очереди, чтобы купить у вас, и заказывают по одному по порядку. Каждый клиент купит только один стакан кваса и заплатит купюрой по 5, 10 или 20 рублей. Вы же должны дать сдачу каждому клиенту. Сначала у вас нет сдачи.
Необходимо определить сможете ли вы продать квас каждому клиенту!
Входные данные: bills - массив купюр, которые платит iй ребенок в очереди.
Вывод: true - если вы сможете расчитать каждого клиента, false - в противном случае.
Примеры:
1. [5, 5, 5, 10, 20]
Output: true
Поясниение:
- первым 3м клиентам вы продадите квас, не давая сдачи, у вас будет 3 купюры по 5 рублей.
- второму клиенту вы дадите сдачу 5 рублей и получите купюру в 10 рублей.
- 3му клиенту вы дадите сдачу купюрами в 5 и 10 рублей.
2. [5, 5, 10, 10, 20]
Output: false
Пояснение:
- первым 2м клиентам вы продадите квас, не давая сдачи, у вас будет 2 купюры по 5 рублей.
- следующим 2м клиентам вы дадите сдачу оставшимися купюрами в 5 рублей. У вас останется только 2 купюры по 10 рублей.
- последнему клиенту вы не сможете дать сдачу в 15 рублей.
Разбор
- Давайте просто смоделируем процесс выдачи сдачи:
- Сначала у нас нет ни одной купюры.
- Если клиент дает купюру в 5 рублей, берем ее и увеличиваем счетчик таких купюр.
- Если клиент дает купюру в 10 рублей, то мы должны дать сдачу в 5 рублей. Если у нас нет такой купюры, возвращаем false.
- Если клиент дает купюру в 20 рублей, то мы должны отдать 15 рублей сдачи:
- Всегда проверяем комбинацию в 10 и 5 рублей, если они у нас есть, то обновляем счетчики этих купюр.
- Если такой комбинации нет, то проверяем 3 купюры по 5 рублей. Если их нет, возвращаем false.
Детали реализации смотрите ниже.
Реализация
Запустить код можете тут:
https://dotnetfiddle.net/EWPBOd