Задача тижня 12.11.12 – 18.11.12
Найшвидший розрахунок
У країні дурнів фінансові розрахунки здійснюються з використанням місцевої валюти – дургриків, при чому застосовуються купюри тільки двох номіналів: у 2 дургрики і в 5 дургриків. Під час проведення розрахунку кожну купюру, яку передають платник або касир один одному, піддають ретельній і тривалій експертизі, тому витрати часу на розрахунок залежать від сумарної кількості використовуваних у його процесі купюр.
1. Створіть програму, яка допомагає покупцю здійснити платіж N дургриків за мінімальний час.
Вхідні дані
Значення N (сума в дургриках, яку потрібно сплатити) – натуральне число, що не перевищує 1000000
Вихідні дані
Значення K2, K5 (кількості купюр номіналом 2 і 5 дургриків, відповідно, які передає (якщо значення від’ємне) або отримує (якщо значення додатне) платник, – цілі числа, виводяться на екран.
2. Заповніть тестову таблицю за результатами роботи програми:
Номер тесту | N | K2 | K5 |
| 1 | 3 | 1 | -1 |
| 2 | 1 | ||
| 3 | 4 | ||
| 4 | 5 | ||
| 5 | 6 | ||
| 6 | 17 | ||
| 7 | 48 | ||
| 8 | 109 | ||
| 9 | 1024 | ||
| 10 | 50002 |
Аналіз розв’язку задачі «Найшвидший розрахунок»
Відсутність купюри з номіналом 1 дургрик створює суттєві проблеми мешканцям країни дурнів.
На перший погляд здається, що простим перебором можна визначити оптимальний спосіб розрахунків для суми від 1 до 10 дургриків. Але здобуті висновки не можуть бути поширені на суми більше 10 дургриків без доведення. Деякі автори не врахували у своїх розв’язках, що оптимальні розрахунки для сум 11, 21, 31 тощо відрізняються від простого поєднання оптимальних розрахунків для сум в 1 та 10 дургриків (такі тести не були запропоновані в тестовій таблиці). Дивиться 11=(5+5)+(5-2-2) потребує більше перевірок купюр ніж 11=5+2+2+2.
На нашу думку, найбільш прозорим є наступний підхід до розв’язку задачі:
1. Визначимо, скільки купюр номіналом 5 є складовими потрібної суми:
K5=N div 5;
Залишається:
N1=N mod 5;
2. Визначимо, скільки купюр номіналом 2 можна додати:
K2 = N1 div 2;
Залишається:
N1=N1 mod 2;
3. Якщо залишилось сплатити ще 1 дургрик (N1=1), то потрібно сплатити 5 і отримати решту 2+2, розрахунок буде правильним, але не завжди оптимальним – доцільно замінити послідовність 5+5-2-2 (якщо така послідовність існує) на послідовність 2+2+2:
K5 = -N1 – K5;
K2 = N1 * 2 – K2;
якщо (K5 <= -2) and (K2 >= 2)
K2 = K2 – 5;
Тестова таблиця з результатами роботи програми:
Номер тесту | N | K2 | K5 |
| 1 | 3 | 1 | -1 |
| 2 | 1 | 2 | -1 |
| 3 | 4 | -2 | 0 |
| 4 | 5 | 0 | -1 |
| 5 | 6 | -3 | 0 |
| 6 | 17 | -1 | -3 |
| 7 | 48 | 1 | -10 |
| 8 | 109 | -2 | -21 |
| 9 | 1024 | -2 | -204 |
| 10 | 50002 | 1 | -10000 |
Журі оцінило надіслані розв’язки наступним чином:
| № | Учасник | Кількість балів |
| 1 | Sergey Shablenko | 3 |
| 2 | Антон Мишенин | 2 |
| 3 | Vitas Vitas | 3 (тестова таблиця учасника є правильною, але для N=2, 4, 6 програма виводить на екран два варіанти розрахунку й не вирішує, який з них потрібно обрати) |
| 4 | Юрий Дончик | 4 |
| 5 | Ивахненко Олег | 4 |
| 6 | RomaN | 3 |
| 7 | Сергій Сальніков | 4 |
