Розглянемо олімпіадну задачу. Задача нескладна, детально описана автором як в тексті умови, так і в тестових прикладах. Але в задачі є один цікавий момент, який необхідно знайти самостійно.
Задача: Коробка
Автор: Anton Tsypko
Джерело: Ukrainian Olympiad in Informatics 2021-2022, II stage, 13-th November
Розміщена: https://groups.eolymp.com/uk/problems/10923
Умова:
У Козака Вуса є коробка, яка може вмістити до k кілограмів включно. Якщо у коробці будуть речі, вага яких перевищує k кілограмів, то вона порветься. У нього також є п'ять м'ячів вагою a1,a2,a3,a4,a5 кілограмів відповідно. Також відомо, що вага кожного наступного м'яча більша за попередню. Визначте максимальну кількість м'ячів, які можна положити у коробку так, що вона не порвалася.
Вхідні дані
Перший рядок містить одне ціле число k (1≤k≤100).
Другий рядок містить п'ять цілих чисел a1,a2,a3,a4,a5 (1≤ ai ≤25). Гарантується, що кожне наступне число більше за попереднє.
Вихідні дані
Виведіть максимальну кількість м'ячів, які можна вмістити у коробку.
Примітка
У першому прикладі перші три речі сумарно важать 10 кілограмів, саме стільки можна вмістити у коробку.
У другому прикладі перші дві речі важать три кілограми. А три речі важать уже шість кілограмів, проте шість більше, ніж чотири. Тому третю річ взяти неможливо.
У третьому прикладі перші три речі важать шість кілограмів, а чотири речі важать уже десять кілограмів, тобто більше, ніж дев'ять. Тому відповідь три.
Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MB
Вхідні дані #1
10
1 4 5 7 25
Вихідні дані #1
3
Вхідні дані #2
4
1 2 3 4 5
Вихідні дані #2
2
Вхідні дані #3
9
1 2 3 4 5
Вихідні дані #3
3
На перший погляд, не дуже зрозуміло, чому така проста задача була включена в олімпіаду. Але давайте не поспішати. Я пропоную розглянути один з варіантів розв’язку, пояснюючи алгоритм та ілюструючи його блок схемою. Саме використання блок-схеми, на мою думку, допоможе зрозуміти логіку роботи програми.
Припустимо, що всі п’ять м’ячів можуть розміститися в коробці. Тобто, вага п’яти м’ячів менша або дорівнює вазі, на яку розрахована коробка. В такому випадку нам потрібно вивести максимальну кількість м’ячів, тобто 5. І на тому завершити роботу програми.
Давайте представимо це блок-схемою. Введення і виведення даних представимо паралелограмами. Щоб не плутатися, при введенні даних будемо писати "input", а при виведенні — "print".
Розгалуження представимо ромбом, у якого один вхід (зверху) і два виходи. Якщо умова виконується, то програма переходить до виконання наступного блоку по стрілці «Yes», а коли умова не виконується, то програма переходить до наступного блоку по стрілці «No»:
Погодьтесь, з використанням блок-схеми логіка програми повністю зрозуміла. Якою би мовою ми потім не писали код. Єдина проблема — у нас є незакрита стрілка «No» – ми не вказали на блок-схемі, що робити, якщо умова не виконується. Тому стрілка червона. Але ми це скоро виправимо.
Варіант, коли в коробку влізуть всі п’ять м’ячів ми розглянули, можна більше до того не повертатися. А якщо п’ять м’ячів не можна розмістити (це якраз по червоній стрілці), давайте перевіримо, чи можна розмістити чотири:
if a1 + a2 + a3 + a4 <= k:
print(4)
Як це буде виглядати на блок-схемі? Так:
Погодьтесь, зрозуміла візуалізація.
Розбираємося далі.
Як казав один з моїх вчителів, Володимир Леонідович Дідковський, помилки дуже часто ховаються не перед очима, а саме на краях. Яка максимальна кількість м’ячів може поміститися в коробку? П’ять. Вірно, бо їх усього п’ять згідно умови. Один край умови ми розглянули – максимум. Розглянемо інший край – мінімум. А яка мінімальна кількість м’ячів може розміститися в коробці? Один? Ні, неправильно. Давайте абстрагуємся від тестових прикладів і представимо, що у нас є невелика коробка склеєна зі звичайного офісного паперу і п’ять цеглин. Скільки цеглин витримає така коробка? Нескільки. Нуль.
Ось варіант вхідних даних для такого випадку:
Вхідні дані
1
5 6 7 8 9
Вихідні дані
0
Звичайно, такого прикладу немає в умові задачі, треба самостійно розглянути умови «на краях». І якщо це зробити, то задача, по суті, нескладна. І за допомогою блок-схеми можна пояснити логіку її роботи без прив’язування до мови програмування.
Погодьтесь, все зрозуміло:
В коді на Python це буде так:
k = int(input())
a1, a2, a3, a4, a5 = map(int, input().split())
if a1 + a2 + a3 + a4 + a5 <= k:
print(5)
elif a1 + a2 + a3 + a4 <= k:
print(4)
elif a1 + a2 + a3 <= k:
print(3)
elif a1 + a2 <= k:
print(2)
elif a1 <= k:
print(1)
else:
print(0)