Цінність задачі, що ми розглянемо, в тому, що для її розв’язку не треба серйозних знань з системних дисциплін. Задачу можна розв’язати лише за допомогою звичайної логіки, підгледівши синтаксис в міні-довідниках.
Умова:
Мінімальна кількість купюр
(https://basecamp.eolymp.com/uk/problems/2033)
Дано натуральне число N (8 ≤ N ≤ 1000000), яке визначає будь-яку цілочислову грошову суму ≤ 1000000. Відомо, що цілочислову грошову суму, більшу чи рівну 7 грошовим одиницям, можна видати лише купюрами номіналом у 2 та 5 грошових одиниць. Визначте, якою кількістю купюр у 2 та 5 грошових одиниць можна видати суму в N грошових одиниць, щоб їхня загальна кількість була найменшою.
Вхідні дані
Єдине число - задана сума.
Вихідні дані
Єдине число - шукана мінімальна кількість купюр.
Приклади
Вхідні дані:
9
Відповідь:
3
Логічним буде припущення, що для мінімізації кількості купюр, варто брати купюри більшого номіналу. Тобто, якщо нам треба набрати 10 гривень, то логічним буде спробувати брати більші купюри — в 5 гривень. Беремо таких дві штуки і у нас чудово набирається 10 гривень.
Записуємо: 10 = 5 + 5.
Відповіддю буде два – кількість купюр. Логічно? Логічно.
Проводимо наступний віртуальний експеримент. Припустимо, нам треба набрати 11 гривень і у нас так само — купюри в 5 і купюри в 2 гривні.
Беремо максимальну кількість купюр максимального номіналу. Що виходить?
11 = 5 + 5 + (1 це залишок)
А купюри в одну гривню у нас нема. Так само ми не розв’яжемо задачу якщо у нас в залишку буде 3 гривні, тобто якщо у нас в залишку буде непарне число. Що в такому випадку робити?
Пропоную наступний алгоритм: якщо залишок виходить непарним, то повертаємо назад одну купюру в 5 гривень, відповідно, залишок збільшується на 5 гривень і ми будемо його набирати купюрами в 2 гривні. П’ять — число непарне, відповідно після операції повернення залишок з непарного стане парним.
11 = 5 + 5 + 1. Ні, бо залишок (1) непарний, тому 11 = 5 + (6 це залишок). Відповідно, 11 = 5 + 2 + 2 + 2 (всього — чотири купюри).
Проведемо ще кілька експериментів:
12 = 5 + 5 + 2 (три купюри)
13 = 5 + 5 + 3. Ні, бо залишок (3) непарний, тому 13 = 5 + 2 + 2 + 2 + 2 (п’ять купюр)
14 = 5 + 5 + 2 + 2 (чотири купюри)
15 = 5 + 5 + 5 (три купюри)
16 = 5 + 5 + 5 + 1. Ні, бо залишок (1) непарний, тому 16 = 5 + 5 + 2 + 2 + 2 (п’ять купюр)
17 = 5 + 5 + 5 + 2 (чотири купюри)
18 = 5 + 5 + 5 + 3. Ні, бо залишок (3) непарний, тому 18 = 5 + 5 + 2 + 2 + 2 + 2 (шість купюр)
Сподіваюсь, зрозуміло пояснив.
Успіхів!