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

Умова:

Мінімальна кількість купюр
(https://basecamp.eolymp.com/uk/problems/2033)

Дано натуральне число N (8 ≤ N ≤ 1000000), яке визначає будь-яку цілочислову грошову суму ≤ 1000000. Відомо, що цілочислову грошову суму, більшу чи рівну 7 грошовим одиницям, можна видати лише купюрами номіналом у 2 та 5 грошових одиниць. Визначте, якою кількістю купюр у 2 та 5 грошових одиниць можна видати суму в N грошових одиниць, щоб їхня загальна кількість була найменшою.

Вхідні дані

Єдине число - задана сума.

Вихідні дані

Єдине число - шукана мінімальна кількість купюр.

Приклади

Вхідні дані:

9

Відповідь:

3

Логічним буде припущення, що для мінімізації кількості купюр, варто брати купюри більшого номіналу. Тобто, якщо нам треба набрати 10 гривень, то логічним буде спробувати брати більші купюри — в 5 гривень. Беремо таких дві штуки і у нас чудово набирається 10 гривень.

Записуємо: 10 = 5 + 5.

Відповіддю буде два – кількість купюр. Логічно? Логічно.

Проводимо наступний віртуальний експеримент. Припустимо, нам треба набрати 11 гривень і у нас так само — купюри в 5 і купюри в 2 гривні.

Беремо максимальну кількість купюр максимального номіналу. Що виходить?
11 = 5 + 5 + (1 це залишок)

А купюри в одну гривню у нас нема. Так само ми не розв’яжемо задачу якщо у нас в залишку буде 3 гривні, тобто якщо у нас в залишку буде непарне число. Що в такому випадку робити?

Пропоную наступний алгоритм: якщо залишок виходить непарним, то повертаємо назад одну купюру в 5 гривень, відповідно, залишок збільшується на 5 гривень і ми будемо його набирати купюрами в 2 гривні. П’ять — число непарне, відповідно після операції повернення залишок з непарного стане парним.

11 = 5 + 5 + 1. Ні, бо залишок (1) непарний, тому 11 = 5 + (6 це залишок). Відповідно, 11 = 5 + 2 + 2 + 2 (всього — чотири купюри).

Проведемо ще кілька  експериментів:

12 = 5 + 5 + 2 (три купюри)

13 = 5 + 5 + 3. Ні, бо залишок (3) непарний, тому 13 = 5 + 2 + 2 + 2 + 2 (п’ять купюр)

14 = 5 + 5 + 2 + 2 (чотири купюри)

15 = 5 + 5 + 5 (три купюри)

16 = 5 + 5 + 5 + 1. Ні, бо залишок (1) непарний, тому 16 = 5 + 5 + 2 + 2 + 2 (п’ять купюр)

17 = 5 + 5 + 5 + 2 (чотири купюри)

18 = 5 + 5 + 5 + 3. Ні, бо залишок (3) непарний, тому 18 = 5 + 5 + 2 + 2 + 2 + 2 (шість купюр)

Сподіваюсь, зрозуміло пояснив.  

Успіхів!

Іноді трапляється так, що умова задачі сформульована неточно. Буває, що в ній багато зайвих деталей, які відволікають. А іноді автори навмисно заплутують умову. Пропоную розглянути задачу «Сортуюча машина", в умові якої є приклад-пояснення. Проте алгоритм, описаний у прикладі, зовсім неоптимальний. Якщо зробити по-своєму, задача виявляється нескладною.

Умова:

Сортуюча машина
(https://www.eolymp.com/uk/problems/1144)

Є машина для сортування набору різних чисел. Вона має лише одну команду MOVE з одним аргументом. Ця команда переміщує число, вказане в аргументі, в кінець послідовності. Наприклад, щоб відсортувати масив чисел 19,7,8,25 у зростаючому порядку, потрібно виконати дві команди:

1. MOVE 19, отримаємо 7,8,25,19.
2. MOVE 25, отримаємо 7,8,19,25.

Для заданого набору чисел необхідно знайти мінімальну кількість команд MOVE, після виконання яких його елементи будуть упорядковані у зростаючому порядку.

Вхідні дані

Перший рядок містить кількість чисел n (n≤50). Другий рядок містить n цілих чисел у діапазоні від −1000 до 1000.

Вихідні дані

Виведіть мінімальну кількість команд MOVE, після виконання яких усі числа будуть упорядковані у зростаючому порядку.

Давайте розберемо приклад, представлений в умові.

У нас є послідовність: 19,7,8,25. І нам потрібно відсортувати її за зростанням.

Як це пропонується в умові ми робити не будемо. Робити це за алгоритмом, запропонованим в умові, складно. Спочатку нам потрібно перемістити число 19, але воно не є ані найбільшим, ані найменшим, чому варто починати саме з нього, з усім тим потрібно возитися. Пропоную інший підхід — метод стіни. Давайте після списку намалюємо червону стіну:

19,7,8,25|

Наступним кроком ми проаналізуємо список ліворуч від стіни. Може він вже відсортований. Тоді жодних переміщень робити  не потрібно, можна виводити нуль і йти спати. Якщо список не сортований, то виконуємо таку дію:

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

19,7,8|25

Ми зробили одне переміщення і у нас тепер один загнутий палець.

Знову аналізуємо список ліворуч від стіни, він не сортований (19,7,8). Знову відшукуємо максимальний елемент, перекидуємо його за стіну і загинаємо ще один палець:

7,8|19, 25

Продовжуємо. Список ліворуч від стіни відсортований? Так. Чудово. Виводим кількість загнутих пальців і завершуємо роботу програми.

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

Вхідні дані:

19,7,8,25

Не відсортований список? Тоді знаходимо максимум, видаляємо його, загинаємо палець. Що залишилось:

19,7,8

Не відсортований список? Тоді знаходимо максимум, видаляємо його, загинаємо ще один палець. Що залишилось:

7,8

Не відсортований список? Відсортований. Виводимо кількість загнутих пальців і завершуємо роботу програми.

Погодьтесь, цей спосіб значно простіший, ніж наведений в умові.

Який з цього всього можна зробити висновок?  Якщо ви досюди дочитали, то ви розумні. Сформулюйте самі )

Хто зрозумів моє пояснення  – можете написати код і здати задачу. У кого не виходить, натисність «детальніше» - побачите один з варіантів коду.

Успіхів!

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

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

Удачі!

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