Пропоную розглянути чудову задачу «Булочки» з сайту eolymp.com. Безумовним плюсом задачі, як на мене, є простота умови і чудова родзинка, яку психологи називають «розрив шаблону».
Булочки
https://www.eolymp.com/uk/problems/11379
Умова:
Хусейн дуже любить булочки, які продаються в університеті. Відомо, що
- можна купити одну булочку за a гяпиків;
- можна купити три булочки за b гяпиків;
Хусейн хоче придбати точно n булочок. Яку найменшу кількість гяпиків йому слід витратити?
Вхідні дані:
Три натуральні числа a, b і n, кожне з яких не більше 10^9.
Вихідні дані:
Виведіть найменшу кількість гяпиків, яку слід витратити Хусейну для покупки точно n булочок.
Приклад
Вхідні дані :
2 5 10
Вихідні дані:
17
Автор: Михаил Медведев
Розглянемо тестовий приклад. Одна булочка коштує два гяпіка. Але три булочки коштують не шість, а п’ять гапіків. Ми бачимо зрозумілу оптову ціну. Якщо купити відразу три, то кожна булочка буде трохи дешевше, а саме 5 / 3 = 1,67 гяпіка. Очевидно, що при оптових знижках нам варто купити якомога більше «трійок булочок», а вже далі доповнити нашу купівлю одиночними, більш дорогими булочками.
В тестовому прикладі нам треба купити 10 булочок. Давайте порахуємо максимальну кількість трійок, що ми можемо купити. 10 // 3 = 3. Тобто ми можемо купити три рази по три булочки і таким чином заплатимо 5 + 5 + 5 = 15 гяпіків. Це так ми купимо дев’ять булочок. Ну а десяту вже купимо подорожче, за два гяпіка.
В булочках у нас буде така купівля: три + три + три + одна.
В грошах у нас буде така купівля: 5 + 5 + 5 + 2 = 17.
Ці 17 гяпіків – це і є відповідь, яку ми бачимо в тестовому прикладі.
І якщо ми напишемо код, то здамо задачу… лише на 80%. А чого?
А тому що автор гарно підказав нам типовий приклад. І тому що ми всі звикли, що оптом – дешевше. Це – шаблон. Але… А хто нам обіцяв, що так завжди? А давайте знайдемо розв’язок, коли будуть такі умови:
2 (ціна однієї одиночної булочки)
7 (ціни трьої булочок, от такий дивний опт, а хто сказав, що не буває?)
10 (скільки Хусейну треба купити булочок)
Звичайно, що тоді Хусейну і дарма не треба такі оптові ціни, бо поштучно булочки дешевше.
Гарна задача, так?
То здавайте! )