Розглянемо олімпіадну задачу. Задача нескладна, детально описана автором як в тексті умови, так і в тестових прикладах. Але в задачі є один цікавий момент, який необхідно знайти самостійно.

Задача: Коробка
Автор: 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)

Розглянемо складну задачу. На сайті eolymp.com її складність — 55%, тобто більше половини програмістів, що за неї бралися, її не подолали, а кількість спроб розв’язку перевищує 14 тисяч. При цьому, якщо прочитати умову уважно — задача проста.  Давайте розбиратися.

Задача «Слово чемпіон».
https://www.eolymp.com/uk/problems/330

Умова:

Дано деяке речення на невідомій мові. Назвемо слово у ньому чемпіоном, якщо воно є паліндромом і кількість літер у ньому максимальна. Літерами алфавіту у невідомій мові є літери латинського алфавіту та арабські цифри. Гарантується, що у реченні відсутні інші символи, крім літер, пропусків, розділових знаків та нелітерних дефіс (мінус) і апостроф.

Вхідні дані

Речення на невідомій мові.

Вихідні дані

Номер слова чемпіона.

Ліміт часу 0.5 секунди

Ліміт використання пам'яті 64 Mб

Перший приклад вхідних даних: Oo, it aaa is not bb.

Вихідні дані: 3

Другий приклад вхідних даних: Oo, it aaa issi not bbbbb.          

Вихідні дані: 6

Звичайно, для початку необхідно розібратися з означеннями. Вікіпедія пише, що паліндром — це слово, число, набір символів, словосполучення або віршований рядок, що однаково читається в обох напрямках (зліва направо та справа наліво). У статті на вікі є купа прикладів паліндромів, в тому числі достатньо драматичних як то «Три психи пили Пилипихи спирт», але немає чіткої відповіді чи є паліндромом слово з однієї букви. ChatGPT каже, що однобуквене слово можна вважати паліндромом і тут з ним можна погодитися. Не питайте його про трьох випиваючих психів, в цьому питанні воно до смішного дурне.

З паліндромом визначились. Мовою Python визначити чи слово є паліндромом можна, наприклад, так:

word = 'abba'

print(word == word[::-1]) 

Тестові приклади підказують нам, що треба привести всі букви до єдиного регістру. Бо без цього слово 'abba'  буде зараховане як паліндром, а слово 'Abba' — ні. Тому приводим весь текст до одного регістру, наприклад, зробимо всі букви маленькими. Треба враховувати, що об’єкт текстового типу в мові Python є іммутабельним, тобто його не можна змінити.

Відповідно, так робити не можна:

txt = 'Василь'
txt.lower()

А так — можна:

txt = 'Василь'
txt = txt.lower()

Наступний етап дослідження — розділові знаки. В реченні, згідно умови, є розділові знаки, і нам потрібно їх з речення вилучити. До розділових знаків належать: крапка, кома, крапка з комою, двокрапка, тире, три крапки, знак оклику, знак питання, лапки, дужки, скісна риска, абзац, проміжок.

Як багато! Звичайно, можна вилучати їх по черзі:

txt = txt.replace('.','')
txt = txt.replace(',','')

Але так довго. Тому варто пошукати алгоритм колективного вилучення розділових знаків. Нам допоможуть регулярні вирази. Ось як можна в один рядок вилучити з речення цілу купу розділових знаків:

txt = re.sub(r'[.,;:!?{}\[\]()"]', '', txt)

Ну і вишенька на нашому торті. В умові написано, що в реченні можуть бути нелітерний дефіс (мінус) і апостроф.

Тут важливо не полінуватися і дізнатися, що це таке — нелітерні знаки.

Вікіпедія не така вже і наукова, але простою людською мовою пише, що нелітерні орфографічні знаки — категорія знаків писемності, які не є літерами, але використовуються в написанні слів (тобто належать орфографії), а не розділяють слова (на відміну від знаків пунктуації, що належать до пунктуації).

Дефіс і апостроф ми повинні в нашій задачі рахувати як літери! Ми не можемо викинути з тексту дефіси, тому що вони можуть бути важливими для визначення паліндромності. Ось, наприклад два слова:

abba-abba
abbaab-ba

Перше — паліндром, друге — ні.  Різниця — в місці дефісу.

Але якщо  дефіс стоїть окремо, наприклад, обрамлений пропусками, то це вже не буква, а окрема частина речення. Приклад:

abba - abak bebebeb

Формально це вже тире, тобто знак пунктуації, а ми такі знаки з речення вилучаемо. Тому будемо вилучати дефіс лише в тому випадку, коли він буде в оточенні пропусків:

txt = re.sub(r' - ', ' ', txt)

Так само з апострофом. Він, згідно умови, може бути частиною слова, наприклад

abba'abba або  abbaab'ba

або може бути окремим символом в реченні, тоді буде оточеним пропусками. Зідно умови наше речення на невідомій мові, може в цій мові існують такі конструкції:

abba ' abak bebebeb 

Отже, для розв’язування даної задачі нам потрібно розібрати поняття нелітерних орфографічних знаків, або ілетрограм. Інакше ми не зможемо повністю зрозуміти умову. 

В узагальненому вигляді, порада програмістам може бути традиційною: «Читайте умову уважно і цілком» :)

Варіант коду:

import re

txt = input()
txt = txt.lower()
txt = re.sub(r'[.,;:!?{}\[\]()"]', '', txt)
txt = re.sub(r' - | \' ', ' ', txt)

index_max = 0
len_max = 0

words = [x for x in txt.split()]

for index, word in enumerate(words):
    if word == word[::-1] and len(word) > len_max:
        len_max = len(word)
        index_max = index + 1

print(index_max)

Обмін думками про значність зв’язку програмування з математикою — річ відома. Сьогодні на розгляд пропонується задача, для розв’язання якої математика таки згодиться.

Задача «Контрольна робота»
https://www.eolymp.com/uk/problems/1690

Умова:

Паралель восьмих класів написала контрольну роботу. В результаті рівно A% учнів отримали 5, рівно B% - 4, рівно C% - 3, а інші D% написали її на 2. Яка мінімальна кількість школярів повинна бути у паралелі восьмих класів для того, щоб могли бути отримані такі результати?

Вхідні дані

Вводяться 4 цілих числа від 0 до 100 - A, B, C, D (A + B + C + D = 100).

Вихідні дані

Виведіть єдине ціле додатнє число - мінімальну можливу кількість учнів у паралелі.

Приклад

Вхідні дані  

40 50 5 5

Вихідні дані

20

Пропоную проаналізувати не лише один тестовий приклад, а сформувати кілька таких прикладів і розв’язати задачу спочатку аналітично. Оформимо все в таблицю:

Всі, хто відвідував або відвідує уроки математики, мабуть, відчувають, що тут є простий математичний розв’язок. Так і є. Якщо знайти найбільше число, на яке діляться всі чотири числа умови, то задача стає зовсім простою.

Давайте знайдемо найбільше число, на яке діляться ці чотири числа: 40 50 5 5. Звичайно, це число 5. В математиці це число зветься найбільшим спільним дільником (НСД). І тоді виходить, що вісім учнів отримали п’ятірку (40/5), десять учнів отримали четвірку (50/5), один учень отримав трійку (5/5) і один учень отримав двійку (5/5). Разом виходить 20 учнів. А через те, що нас не питають в задачі, скільки учнів яку оцінку отримали, а питають загальну мінімальну кількість учнів, то можна порахувати так: (40+50+5+5) / НСД.

Перевірити саме цей алгоритм розв'язку можна на додаткових прикладах. І задача стає зовсім простою,  бо НСД можна знайти у тому числі і підбором.  

Але в Python є готова функція, яка обчислює НСД. І робить код простим і лаконічним:

import math
a, b, c, d = map(int, input().split())
print((a + b + c + d) // math.gcd(a, b, c, d))

Але не все так просто. Річ у тому, що цей код не завжди працює. Звернемся до документації Python. Функція gcd() з’явилась у версії 3.5. При цьому можна було вказати лише два аргументи функції. А вказувати чотири аргументи стало можливо лише з версії 3.9:

А якщо учень програмує на Windows 7, то, як відомо, остання версія, яка встановиться на дану операційну систему – це 3.8.10, тому для gcd() треба буде вказувати лише два аргумента. Це не проблема, але код все ж таки буде інший. Наприклад, в Python 3.8.10 цю задачу можна здати таким кодом:

from math import gcd
a, b, c, d = map(int, input().split())
nsd = gcd(gcd(a, b), gcd(c, d))
print((a + b + c + d) // nsd)
 

Якщо учень програмує на Windows XP, то остання версія Python для цієї операційної системи — 3.4.4, а, відповідно, фунцією gcd() учень не зможе скористатися взагалі і йому доведеться шукати НСД іншим шляхом.

Можна, звичайно, користуватися онлайн-середовищами. На replit.com  та еolymp.com  встановлені останні версії Python і багато учнів взагалі не зіштовхнуться з проблемою. Але учням, що планують своє майбутнє в IT, на мою думку, треба розповідати про різноманіття версій та подібні ситуації. Мова не про надглибоку деталізацію, а про загальні факти і приклади. Ну і про відвідування уроків математики, звичайно. Задачу з інформатики «Контрольна робота», що була щойно розглянута без застосування НСД розв’язати буде, IMHO, не так просто і гарно.

Сайт «Плетиво» представляє авторську задачу і наступний алгоритм:

1. Кажемо відповідь
2. Ліземо в гаманець
3. Самооцінювання :)

26 січня 2024 року відбувся III (обласний) етап Всеукраїнської учнівської олімпіади з інформатики Житомирської області. Учні-програмісти змагалися в розв’язанні задач на платформі «Contest Management System», розгорнутій в університеті «Житомирська політехніка».

Учасникам олімпіади було запропоновано сім задач і чотири години часу для їх розв’язання. Для контролю на всіх робочих місцях учасників було встановлено вебкамери, що в режимі онлайн транслювали зображення і звук для журі. Крім того, учасники проводили відеозапис екранів своїх комп’ютерів і по завершенню олімпіади передали журі покликання на чотиригодинні відеозвіти.

Після завершення олімпіади задачі традиційно з’явилися на сайті eolymp.com, всі бажаючі можуть тепер спробувати свої сили в їх розв’язанні.

Розглянемо одну з задач олімпіади — «Балансуючі елементи» (https://www.eolymp.com/uk/problems/11658).

Умова:

Задано послідовність з N елементів, які є цілими числами. Назвемо «балансуючим елементом» такий, що сума всіх елементів перед ним дорівнює сумі елементів після нього. При цьому перший та останній елементи послідовності не можуть бути «балансуючими».

Знайдіть кількість «балансуючих елементів» у заданій послідовності.

Вхідні дані:

У першому рядку записане ціле число N. У другому рядку записано N цілих чисел, розділених пробілом. Всі числа не перевищують за модулем 100000.

Вихідні дані:

Виведіть одне число – кількість «балансуючих елементів».

Приклад

Вхідні дані:

3

1 2 1

Вихідні дані:

1

— Ліміт часу: 1 секунда

— Ліміт використання пам'яті: 256 Mb

Зрозуміле формулювання задачі та знання програмістами функції SUM() при роботі зі списками створює багатьом солодку ілюзію рівня «я зараз цю задачу  як Тузик ганчірку». Але, згідно статистики олімпіади,  лише 22%  учасників обласної олімпіади зробили її на 100%. Чому так мало?  Мабуть, за це варто подякувати авторам задачі і тим, хто складав для неї тести.

Нескладно представити, як працює функція SUM(). Звичайно, це повний перебір елементів з додаванням їх значень. І, незважаючи, що всередині мови програмування функція максимально оптимізована, на її виконання потрібен деякий час.

Давайте представимо варіант, коли зліва і справа від елементу, що перевіряється, стоїть по мільйону елементів. Відповідно, для перевірки «балансовості» поточного елемента треба виконати SUM(мільйон елементів) для елементів, що стоять лівіше його і SUM(мільйон елементів) для елементів, що стоять правіше. Тобто, два мільйони елементів перебираються задля перевірки одного поточного. Далі беремося перевіряти на балансовість наступний елемент — і знову перебираємо два мільйони елементів.  Але ж у нас на всю задачу ліміт в 1 секунду.

Якщо б автори задачі сформували лише невеличкі по розміру масиви-списки для тестів, то задачу би здали більше програмістів. А на великих списках одної секунди для розв’язку таким алгоритмом очікувано не вистачало. При чому як на Python, так і на C# (дякую за перевірку Захару з i7).

Хоча певні питання до укладачів тестів у нас є. Наприклад, восьмикласник Андрій з i7 вважає, що за розв’язок

print(1)

 зараховувати цій задачі 30% - то багато. Як на мене — дійсно багато.

Але давайте спробуємо знайти алгоритм розв’язку задачі «Балансуючи елементи», що розв’яже її на 100% за секунду навіть на повільному Python.

Якщо ви хочете спробувати самостійно, то не читайте далі, а пробуйте.

Удачі!

Для тих відвідувачів «Плетива», що не знайшли рішення, після натискання на покликання «Детальніше» я запропоную свою версію і код.

Буває програмування молоде і скоре, як олімпіада. Коли змінні можуть зватися як завгодно, на оптимізацію спагетті-коду нема часу, а годинник голосно підганяє секундною стрілкою.  А буває програмування доросле, виважене.  Смачне і терпке. Коли хочеться зробити гарно, щоб не соромно було показати собі та людям.

Саме так пропонується розв’язати задачу  II етапу Всеукраїнської олімпіади 2010-2011 міста Бердичева. Задача зветься  «Піраміда з символів» і розміщена на сайті eolymp.com (https://www.eolymp.com/uk/problems/1119).

Умова:

Вася хоче надрукувати на принтері піраміду з якогось символу висотою h. Напишіть програму, яка допоможе йому у цьому, не забуваючи, що програма повинна бути "економічно вигідною", тобто друкувати найменшу кількість символів.

Приклади пірамід наведено у прикладах вхідних та вихідних даних.

Вхідні дані:

У єдиному рядку задано спочатку символ, при допомозі якого повинна друкуватись піраміда, а потім через пропуск і натуральне число, яке задає висоту піраміди h (h ≤ 50).

Вихідні дані:

У першому рядку виведіть загальну кількість надрукованих "друкованих" символів а нижче саму піраміду.

Приклад 1.

Вхідні дані:

A 3

Вихідні дані:

12

  A

 AAA

AAAAA

Приклад 2.

 Вхідні дані:

M 9

Вихідні дані:

117

        M

       MMM

      MMMMM

     MMMMMMM

    MMMMMMMMM

   MMMMMMMMMMM

  MMMMMMMMMMMMM

 MMMMMMMMMMMMMMM

MMMMMMMMMMMMMMMMM

Розв’язувати задачу ми будемо мовою Python. Звичайно, в 2010 році  на міській шкільній олімпіаді міста Бердичева не програмували на Python. Більше того, ми будемо використовувати F-рядки, що з’явились в Python в грудні 2016 року.  

Але цікава задача гарна ідеєю, а якою мовою з нею боротися – то деталі )

Для чого нам F-рядки? Тому ще це гарно і ефективно. Це чудовочитабельний спосіб форматування рядків у Python, що дає змогу вставляти значення змінних всередину рядкового літерала, використовувати вирази і навіть викликати методи об'єктів прямо всередині рядка.  А ще за допомогою F-рядків легко центрується текст, що нам і потрібно. 

Але в першу чергу визначимо кількість друкованих символів, включаючи пробіли на початку рядків. Намалюємо кілька пірамід, символом «O», а замість пробілів будемо писати плюси. 

Піраміда з одного шару буде складатися з 1 символу:

O

Піраміда з трьох шарів буде складатися з 12 символів:

++O

+OOO

OOOOO

Піраміда з п’яти шарів буде складатися з 35 символів:

++++O

+++OOO

++OOOOO

+OOOOOOO

OOOOOOOOO

Піраміда з семи шарів буде складатися з 70 символів:

++++++O

+++++OOO

++++OOOOO

+++OOOOOOO

++OOOOOOOOO

+OOOOOOOOOOO

OOOOOOOOOOOOO

Згідно умови піраміда з дев’яти шарів буде складатися з 117 символів.

У нас є відповідність аргументу і результату, спробуємо вивести формулу:

1 >> 1

3 >> 12

5 >> 35

7 >> 70

9 >> 117

Це той випадок, коли можна не поспішати. Покрутити, спробувати,  подумати. Щоб зробити гарно. І якщо у вас вийде, то можете себе перевірити традиційним для «Плетива» способом. Підставте аргументом в вашу формулу найбільший аргумент з умови. В результаті ви отримаєте кількість друкованих символів при h = 50. Допишіть це число в посилання і перевірте.

Наприклад, згідно вашої формули при h = 50 кількість друкованих символів — 915.

Тоді перейдіть за посиланням:

https://pletyvo.in.ua/answers/915

Якщо ваша формула вірна, то за посиланням вам про це скажуть )) Будь ласка, не треба DDoS-ити сайт перебором ))

А щодо коду з використанням F-рядків, то пропоную не обговорювати. Як на мене – це  просто гарно і стильно:

data = input().split()

symbol, h = data[0], int(data[1])

print(тут буде ваша формула, в якій аргумент - h)

for x in range(1, h * 2, 2):

    print(f'{symbol * x:^{h * 2 - 1}}')

Успіхів вивести формулу і здати задачу!

Кількість відвідувачів платформи Canva до 2023 року перевищує 100 млн користувачів у 190 країнах світу.  В Canva є можливість генерації фото з тексту.  Ми попросили штучний інтелект Canva намалювати собаку, наприклад, так: «dog in the style of Claude Monet».  

Які вони чудові!