Решта

Решта

Складна

Вступ

У містичному селі Coinholt ми стоїмо за прилавком своєї пекарні й розкладаємо свіжу партію випічки. Двері зі скрипом відчиняються, і до пекарні заходить Denara, вправна торговка, яка добре знається на якісних товарах. Після швидкої трапези вона пересуває по прилавку сяйливу монету вартістю 100 одиниць.

Ми всміхаємося, беремо монету і дивимося на загальну вартість трапези: 88 одиниць. Отже, потрібно повернути решту на 12 одиниць.

Denara вичікувально простягає руку. «Дайте мені найменше монет», - каже вона з усмішкою. «Мій гаманець уже повний, і я не хочу ризикувати і загубити їх у дорозі.»

Ми знаємо, що варіантів є кілька. «На решту в нас є Lumis (вартістю 10 одиниць), Viras (вартістю 5 одиниць) і Zenth (вартістю 2 одиниці).»

Ми швидко подумки перебираємо можливі варіанти:

  • один Lumis (1 × 10 одиниць) + один Zenth (1 × 2 одиниці) = усього 2 монети
  • два Viras (2 × 5 одиниць) + один Zenth (1 × 2 одиниці) = усього 3 монети
  • шість Zenth (6 × 2 одиниці) = усього 6 монет

«Найкращий вибір - дві монети: один Lumis і один Zenth», - кажемо ми, віддаючи їй решту.

Denara всміхається, явно вражена. «Як завжди, усе правильно.»

Вказівки

Визначте найменшу кількість монет, яку потрібно видати покупцеві, щоб сума їхніх значень дорівнювала потрібній сумі решти.

Приклади

  • Для суми 15 і доступних значень монет [1, 5, 10, 25, 100] потрібно повернути одну монету значенням 5 і одну монету значенням 10, або [5, 10].
  • Для суми 40 і доступних значень монет [1, 5, 10, 25, 100] потрібно повернути одну монету значенням 5, одну монету значенням 10 і одну монету значенням 25, або [5, 10, 25].
Редагувати через GitHub Посилання відкривається в новому вікні або вкладці
CoffeeScript Exercism

Час розпочати Решта?

Зареєструйтеся на Exercism, щоб вивчати й опановувати CoffeeScript, а також 97 вправ та справжнє наставництво від людей, і все це безкоштовно.