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

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

Буває так, що задача нескладна, але умова не відразу є зрозумілою. І тоді звичайний графічний аналіз дуже допомогає розв’язанню. Пропоную розібрати задачу «Гра з перемикачами»
https://www.e-olymp.com/uk/problems/335

Умова:
Є нескінченна кількість ламп, що знаходяться у вимкненому стані. На кожному етапі гри вмикаються (якщо вони були вимкнені) або вимикаються (якщо вони були увімкнені) всі ті лампи, номери яких кратні номеру етапу гри.

Задача:
Визначити стан n-ої лампи після n-го етапу гри.

Вхідні дані
У першому рядку задано кількість тестів t (1 ≤ t ≤ 10). Далі йде t рядків з номером n (0 < n ≤ 105) етапу гри.

Вихідні дані
Вивести t рядків зі станами відповідних ламп: 0 - лампу вимкнено, 1 - увімкнуто.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Приклад вхідних даних:
2
1
5

Приклад вихідних даних:
1
0

Розв’яжемо задачу графічно. Візьмемо, наприклад, деяку кількість ламп і проаналізуємо їх стан під час проходження етапів гри. На старті гри всі лампи вимкнені, згідно умови.

Після першого етапу всі лампи ввімкнуться, тому що будь-яке число кратне одиниці, тобто націло ділиться на одиницю.

Після другого етапу гри всі лампи, номери яких кратні двом, змінять свій стан. Оскільки після першого етапу всі лампи увімкнені, то лампи з парними номерами вимкнуться.

Ось як можна графічно показати стан ламп після другого етапу гри, жовтий колір – це лампи, що світяться, чорні - вимкнені:

Далі можна аналогічно розписати стан наших 17 ламп після проходження етапів гри і окремо проаналізувати, який стан матиме кожна лампа після чергового етапу:

З нашого прикладу бачимо, що відповідні лампи залишаються увімкненими після 1, 4, 9 і 16 етапів гри, відповідно, в тих випадках, коли квадратний корінь з номера етапу (відповідно, і номера лампи) – ціле число.

Код – питання другорядне, ось один з варіантів на Python:

from math import sqrt
t = int(input())
for _ in range(t):
    n = int(input())
    if sqrt(n) == int(sqrt(n)):
        print(1)
    else:
        print(0)

У даному випадку графічний аналіз значно допоміг нам знайти логіку і розв'язок.

Два масива
(https://www.e-olymp.com/uk/problems/2099)

Умова:

Задано два масиви чисел. Потрібно вивести ті елементи першого масиву (у том ж порядку, у якому вони йдуть у першому масиві), яких немає у другому масиві.

Вхідні дані:

Спочатку на вхід подається кількість елементів n у першому масиві, потім n чисел - елементи масиву. Далі записано кількість елементів m у другому масиві. Потім записано елементи другого масиву. Кількість елементів кожного масиву не перевищує 100. Усі елементи - цілі числа.

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

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

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

Ліміт використання пам'яті: 128 MiB

Джерело: Китеня 2011 м.Ковров

Приклад вхідних даних:

7

3 1 3 4 2 4 12

6

4 15 43 1 15 1

Приклад вихідних даних:

4

3 3 2 12

Задача нескладна, має на сайті e-olymp.com рейтинг cкладності всього 8%.

Проте під час розв’язку варто звернути увагу на одну цікаву особливість роботи зі списками.

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

input()

first = [int(x) for x in input().split()]

input()

second = [int(x) for x in input().split()]

third = []

for x in first:

    if x not in second:

        third.append(x)

print(len(third))

print(' '.join(map(str, third)))

Хоча для оптимального розв’язку буде логічним мінімальне використання пам’яті, тому спробуємо розв’язати дану задачу без додаткового списку. Наприклад:

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

Приклад коду:

input()

first = [int(x) for x in input().split()]

input()

second = [int(x) for x in input().split()]

for x in first:

    if x in second:

        first.remove(x)

print(len(first))

print(' '.join(map(str, first)))

Це виглядає значно оптимальніше, програма відпрацьовує тестовий приклад, але не проходить всі тести на сайті e-olymp.com  Що ж не так?

Справа в тому, що ми змінюємо список, який перебираємо. І отримуємо проблему.

Поясню на прикладі.

Нехай наш перший список: [1,2,3,4,5]

Другий список: [2,3]

Який ми повинні отримати результат? [1,4,5].

Але програма видає [1,3,4,5].

Звідки взялася трійка, програма ж повинна була її видалити!

Ось тут і є особливість. Як цикл for  буде перебирати числа? По черзі. Перший елемент, другий елемент, третій елемент і т.д.

А тепер давайте послідовно проаналізуємо значення елементів першого списку: [1,2,3,4,5]

Перший елемент – одиниця, якої немає в другому списку. Отже, одиниця – унікальна, ми її не чіпаємо.

Другий елемент в прикладі – двійка. Вона є в другому списку. Тому ми її видаляємо.  

Який список залишається? [1,3,4,5]. Отже, який елемент списку ми відпрацювали? Другий?

Правильно. Беремо третій. Це четвірка. А чому четвірка?

А тому що при видаленні двійки, всі елементи зсунулися і місце видаленої двійки зайняла трійка. Саме трійка стала другим елементом після видалення двійки.

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

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

Цю задачу, звичайно, можна розв'язати без використання третього списку. Але треба враховувати, що при видаленні, наприклад, другого елемента, список змінюється і далі потрібно знову аналізувати другий елемент.  Наприклад:

count = int(input())

first = [int(x) for x in input().split()]

input()

second = [int(x) for x in input().split()]

x = 0

while count > x:

    if first[x] in second:

        first.remove(first[x])

        count -= 1

    else:

        x += 1

print(len(first))

print(' '.join(map(str, first)))

Який шлях краще обрати для розв’язку? Якщо у програміста цейтнот і немає обмежень по пам’яті, то, можливо, варто скористатися простим і логічним варіантом з третім списком. А якщо ви прийшли на співбесіду щодо працевлаштування, то, мабуть… також. Як це не дивно. Але ж ми ж використовуємо менше пам’яті! Це правда, але давайте уважно перечитаємо умову: «Потрібно вивести ті елементи першого масиву…». Хто ж нам дозволяв змінювати цей масив? :)

В 2020 році обласна олімпіада Житомирської області проходила під прапором змін. Змінився університет проведення — аудиторії Житомирського Державного Університету змінили аудиторії університету «Житомирська Політехніка». Змінилась платформа проведення — цього року це був не e-olymp.com, розроблений в ЖДУ, змагання проводились на платформі Ejudge, яку дуже швидко розгорнули і настроїли. Змінилось і журі олімпіади.

Приємно, що не змінився гарний дух змагання. Ті самі лідери-програмісти так само показали шикарні результати.  Топ-список найкращих вчителів з програмування залишився практично таким самим. Технічно і організаційно ні у мене ні у моїх учнів претензій не було, як все добре працювало всі попередні роки, так все добре працювало і цього року. В сюжеті «Суспільного телебачення» можна побачити учасників, аудиторії, організаторів:

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

Задача «Змішана послідовність»

https://www.e-olymp.com/uk/problems/9610

Задано послідовність символів, розділених пробілами. Кожний символ послідовності представляє собою велику або маленьку літеру латинського алфавіту або цифру від 0 до 9.

Знайдіть суму цифр, які входять до цієї послідовності. Кількість символів, які входять до послідовності – не більше 10 000.

Вхідні дані.

Послідовність символів, розділених пробілами.

Вихідні дані.

Сума цифр, які входять до послідовності або значення 0, якщо у послідовності немає цифр.

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

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

Вхідні дані #1

A 1 2 B C D A B C 1 9 B 3

Вихідні дані #1

16

Вхідні дані #2

A B C

Вихідні дані #2

0

В Python існує величезна купа зручних інструментів, знання яких значно спрощує життя програмісту. Звичайно, Python-програмісти, що працюють з текстом, знають, що для розв’язку можна не порівнювати кожний по циклу вирізаний символ на предмет відповідності його числу, а скористатися функцією isdigit(), що відповідає на запитання «Чи складається рядок з цифр».

Відповідно, використавши цю функцію,  задача здається в один рядок:

print(sum([int(x) for x in input().split() if x.isdigit()]))

Хочу звернути увагу програмістів-початківців на величезну купу вже існуючих в Python функцій для роботи з текстом:

Таблиця: «Функції і методи рядків»

x = 'Микола'

y = 'Оленка'

І це ще не  все :)

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

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

Шановні учні!

Даний довідник може стати вам у пригоді для розв'язку задач

Введення цілих чисел:

Якщо вам треба ввести ціле число від користувача в вашу програму, то використовуйте конструкцію:

x = int(input())

Якщо вам треба ввести два цілих числа, кожне з яких записане в окремому рядку, то це можна зробити так: 

x = int(input())

y = int(input())

Якщо вам треба ввести в вашу програму кілька цілих чисел, що записані через пропуск, то це можна зробити так: 

a, b, c = map(int, input().split())

Введення дійсних чисел:

Якщо вам треба ввести дійсне число від користувача в вашу програму, то використовуйте конструкцію:

x = float(input())

Якщо вам треба ввести в вашу програму кілька дійсних чисел, що записані через пропуск, то це можна зробити так: 

a, b, c = map(float, input().split())

Введення тексту:

Якщо вам треба ввести текст від користувача в вашу програму то використовуйте таку конструкцію:

x = input()

Якщо вам треба ввести текст від користувача в вашу програму, при цьому обрізати пропуски на початку тексту і в кінці, то використовуйте таку конструкцію:

x = input().strip()

Пам'ятайте, що з текстом не можна проводити математичні операції. З тексту ви можете вирізати один або кілька символів, і вирізана частина буде також текстом. Якщо ж вам треба виконати математичні дії з цими даними, то треба конвертувати текст в число. Якщо це стосується цілих чисел, то конструкція така:

y = int(x)

Приклад обчислення квадратного кореня:

import math

x = math.sqrt(4)

print(x)

Виведення даних:

Для виведення даних використовується оператор print()

Приклад виведення тексту:

print('Страшно хочу в школу!')

Приклад виведення числа:

a = 5

b = 3

print(a-b)

Для виведення дійсного числа з певною кількістю знаків після коми можна скористатися f-рядками. 

Приклад: Треба вивести дійсне число з трьома знаками після коми:

x = 12.34567

print(f"{x:.3f}")

Розгалуження:

Задача для прикладу:

Програма повинна прочитати від користувача ціле число та вивести -1, 0 або 1, якщо введене значення від’ємне, нульове і додатне, відповідно.

Приклад коду: 

n = int(input())

if n < 0:

    print(-1)

elif n == 0:

    print(0)

else:

    print(1)

Цикл FOR:

Задача для прикладу:

Програма повинна прочитати від користувача ціле число та вивести числа від одиниці до цього числа включно. Кожне число - в окремому рядку.

Приклад коду: 

 n = int(input())

for x in range(1, n + 1):

    print(x)

Задача для прикладу:

Програма повинна прочитати від користувача ціле число та вивести числа від цього числа до нуля в порядку зменшення. Кожне число - в окремому рядку.

Приклад коду: 

n = int(input())

for x in range(n, - 1, -1):

    print(x)

Якщо це саме треба зробити так, щоб всі числа були в одному рядку, ось приклад:

n = int(input())

for x in range(n, - 1, -1):

    print(x, end = ' ')