Розглянемо складну задачу. На сайті 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, не так просто і гарно.

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}}')

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

Пропоную розглянути чудову задачу «Булочки» з сайту 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 (скільки Хусейну треба купити булочок)

Звичайно, що тоді Хусейну і дарма не треба такі оптові ціни, бо поштучно булочки дешевше.

Гарна задача, так?

То здавайте! )