Традиційно у відкритій шкільній олімпіаді з програмування, що я проводжу кожного року, беруть участь не лише учні, а також студенти та учні інших шкіл. І кожного року є свої сюрпризи, нові імена і дух змагання. Олімпіада традиційно проходить на платформі e-olymp.com на чистих акаунтах. Під час олімпіади можна користуватися help-системою мови програмування. Через те, що навчальний рік тільки розпочався і деякі учні позабували синтаксис, можна користуватися довідниками мови Python.
Приємно, що завантажені навчанням студенти-випускники школи кожного року мотивують молодь своїми гарними результатами по принципу «Навчайтеся, і ви також все це зможете зробити». Цього року у відкритій шкільній олімпіаді взяли участь студенти-айтішники КПІ, Львівської політехніки, НАУ. А студентка медичного факультету університету ім. Богомольця журилася, що «забула увесь Пайтон» але при цьому не забула математику і вивела формулу для однієї з задач.
В даній статті хочу звернути увагу на задачу «Байтик і шахи» (https://www.e-olymp.com/uk/problems/8659).
Нескладна задача, що має на e-olymp.com рейтинг складності лише 12%.
Ось умова:
Байтик та шахи
Якось, вкотре запізнившись на урок, Байтик, проходячи повз ігрову кімнату, помітив шахову дошку. Порахував усі клітинки на ній, і йому стало цікаво: скільки різних квадратів зі стороною k (1≤ k ≤ n) можна розмістити на дошці розміру n.
Вхідні дані:
Натуральне число n (n ≤ 10000) розмір шахової дошки.
Вихідні дані:
Єдине число – кількість різних квадратів, які можна розмістити на шаховій дошці.
Приклад вхідних даних: 3
Приклад вихідних даних: 14
Логічними міркуваннями, листочком і олівцем можна легко знайти кілька окремих випадків. Наприклад, при n=1 очевидно, що кількість різних квадратів – 1. При n=2, тобто дошці 2 на 2 клітинки, квадратів буде п’ять, чотири малих і один загальний, що вміщує в себе чотири малих.
При n =3 відповідь - 14. Це можна порахувати вручну або просто подивитися тестовий приклад в умові задачі.
Давайте складемо табличку:
|
n |
1 |
2 |
3 |
4 |
|
результат |
1 |
5 |
14 |
|
Тут можна побачити класичну задачу з розділу динамічного програмування. Кожне наступне число-відповідь, це n в квадраті плюс відповідь від попереднього n. Відповідно, для n=4, відповідь буде 4*4 + 14 = 30.
На Python це буде, наприклад, так:
n = int(input())
s = 0
for x in range(1, n+1):
s += x**2
print(s)
Я попросив у учнів дозволу переглянути код їх розв’язків. І здивовано побачив такий розв’язок цієї задачі:
n = int(input())
print('{:.0f}'.format((n*(n+1)*(2*n+1))/6))
Це студентський розв’язок. КПІ, 1 курс, прикладна математика. Питаю: «звідки формула»?
Почув відповідь: «Це квадратне пірамідальне число. Нам тиждень тому пояснював це викладач матану. Це не було темою, це він відповідав на запитання під час ZOOM-лекції».
Мабуть, якщо йти вчитися, то на правильну спеціальність правильного університету. Тому що в такому місці за допомогою самоосвіти і викладачів можна системно і послідовно навчитися серйозним речам.
Де замість циклу використовують формулу. Згадують її або виводять з голови. Там, де неоптимально – це погано, і внутрішня освіта за таке сварить. Де олімпіадний принцип «здати у відведений час» - це недостатньо. Тому що і на співбесідах і на роботі — інші критерії.
Можливо, гарна вища айтішна освіта – це коли в голові не розкидані сторінки різних класних книжок, а більш-менш серйозна бібліотека?
Як Ви вважаєте?