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».  

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

Свої знають, що інформатика — то не про комп’ютери. Певною мірою можна розвиватися в предметі за допомогою дуже різних інструментів.

З високою вірогідністю нас чекає непроста зима. Військові кажуть про накопичення противником ракет. Повітряні тривоги стають довшими. Що робити в укриттях вчителям з дітьми? Як можна продовжити розвиватися і в таких умовах?

Один із простих інструментів в таких умовах — паперова інформатика.  І не лише тому, що комп’ютера в укритті немає. Паперова інформатика — самодостатній освітній інструмент.

І традиційно на «Плетиві» — практичний досвід

В кабінеті інформатики, де я працюю, є окремий стіл для «Паперової інформатики». Звичайно, там бувають чудові гості у вигляді книжки проєкту «Ukraїner», як на світлині. Але головними на столі «Паперової інформатики» є  папірці, які можна після уроку або на перерві взяти собі назавжди. На папірцях — цікаві задачі різного типу.

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

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

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

Знайти відмінності

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

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

Веселі задачки

Прості і безпосередні. Які не вимагають занадто багато думати і веселі. Молодші школярі можуть зробити краще за дорослих. Приклад:

Розумні задачі

Прості, але треба подумати.  Приклад (зображення тут не просто так, це підказка):

Ще один приклад:

Складні

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

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

Поясню умову. В першому рядку — прибульці. Їх всіх щось об’єднує.

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

Сірникові задачки

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

Приклад:

Пам’ятаю, як я був вражений експериментом з шістьма сірниками.

Орігамі

Орігамі — ще один цікавий напрям. Можна складати квіти, іграшки. На жабках, складених в техніці орігамі, можна влаштовувати чудові «заскоки» — чия жабка до фінішу доскаче першою.

Ще чудова забава — Flextangles. Разом з шаблонами – кольоровим і творчим. Робиться з одного листа паперу:

Можна ще подивитися цікавого у нас на сайті в розділі «Handmade» і в тематичних пабліках.

Задачі на обговорення 

Якось в спільноті вчителів інформатики показав свою задачу:

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

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

— Хто буде відповідати, якщо Марія Іванівна помилиться? І що з нею потім робити? Яка у неї відповідальність?

— Чому вирішення проблеми залежить від батьків Хуліганова, які не чують звичайних аргументів? Чому інші батьки не беруться до уваги, а цих слухають? А можна інакше?

— Де верифікація науковим апаратом такого способу пошуку істини?

— Хто ким і як маніпулює в даній історії?

— Чи допустимі такі методи пошуку істини?

— Чи не принижує Марія Іванівна дітей таким алгоритмом пошуку винуватих?

А хто запропонує інший алгоритм пошуку істини? А в межах законодавства?

Таке спілкування принесе користь. Це те саме критичне мислення, про яке пушать в івентних кейсах і розмовляють с дітьми на уроках. 

Просте запитання в фіналі 

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

Ви теж вважаєте, що воно того варто?

Анатолій Анатолійович,
листопад 2023 року

У 1970 році перестали існувати «The Beatles». Через 53 роки, 2 листопада 2023 року «The Beatles» випустив ще одну пісню — «Now And Then».

Джон Леннон, один з чотирьох музикантів гурту був застрелений в 1980 році, але його аудіозапис став основою «Now And Then». Для вирішення проблеми низької якості аудіо було використано штучний інтелект.

Джордж Гаррісон помер в 2001, але у фінальну версію останньої пісні увійшли партії ритм-гітари, що Джордж встиг записати у 1990-х.

Свої партії 83-річний Рінго Старр та  81-річний Пол Маккартні записали заново.

За перші п’ять годин після публікації на YouTube — більше як півтора мільйона прослуховувань.  

The Beatles. Now And Then.

ps. На наступний день, 3 листопада вийшов кліп на цю пісню. Неймовірний кліп з 21 мільоном переглядів за перші три дні:

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

Розглянемо ще одну спробу: сервіс «Творець зображень».  Дякую Максиму, що звернув мою увагу на даний сервіс. Ну, подумав я, ще один сервіс. І малює це чудо, мабуть, різноманітні абстракції, в кращому випадку — котиків, схожих на котиків. Але у сервісу «Творець зображень» виявилися дуже амбіційні батьки: компанія OpenAI, що створила платформу для генерації зображень DALL·E 3 та компанія Microsoft, що виклала цей сервіс на свій сайт bing.com Поважна спільнота.

І тоді шо ж воно вміє? Давайте спробуємо. Не знаю, яким художником захоплюєтесь Ви, а я задав сервісу наступний текстовий запит:  «Українське сонце в стилі Леоніда Афремова».  Пробував питати англійською, а потім з’ясував що сервіс розуміє і українську.

І мені показали такі чудеса:

Вау, сказав я, так це ж неймовірно схоже по стилю на Афремова! І я ніколи не бачив таких картин у Леоніда Аркадійовича, а нових він не напише.  То, виходить, що це — генеративне мистецтво платформи DALL·E 3?  А чому воно так гарно?!

А якби попросити Ван Гога намалювати українське сонце? Як би воно виглядало, яким би було?

Шановний DALL·E, я не знаю, як ти це зробиш (іноді краще не уявляти), але як би це показав Вінсент?

DALL·E відповідає, що так:

Як до цього відноситись, як це оцінювати? Не знаю, не цікаво. А от чим я хочу наразі зайнятися — знаю…

Чудовий сайт replit.com ми з учнями активно використовуємо як середовище програмування. Можливість збереження власних проєктів, можливість поділитися своїм розв’язком, чудова робота з бібліотеками, інструмент форматування коду — все це відомо і дуже зручно.

Наразі replit.com має в своєму арсеналі безкоштовний штучний інтелект (AI). Можна запостити умову задачі отримати код. AI  вже розуміє умови і українською мовою. Просто умови, написані людською мовою, без адаптації.

І це серйозно змінює правила проведення олімпіад і конкурсів. Тепер мало не дозволяти учням користуватися під час олімпіад і конкурсів системами штучного інтелекту, тепер треба жорстко контролювати неможливість використання смартфонів, бо іноді невеличкий шматок коду, легко отриманий учасником від штучного інтелекту може серйозно деформувати  принцип справедливості змагань.

Давайте подивимся як працює AI сайту replit.com на прикладі двох задач.

Задача «Різні-різні»

https://www.eolymp.com/uk/problems/5337

Умова:

Задано n чисел. Вияснити, скільки серед них різних.

Вхідні дані

У першому рядку задано кількість чисел n (1 ≤ n ≤ 10^6). У другому рядку задано n чисел, кожне з яких не перевищує 2 ·10^9 за модулем.

Вихідні дані

Виведіть кількість різних чисел серед заданих.

Приклад

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

1

3

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

1

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

5

9 15 22 15 22

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

3

Мій розв’язок:

input()

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

print(len(set(n)))

Розв’язок, запропонований AI:

n = int(input())

numbers = list(map(int, input().split()))

unique_numbers = set(numbers)

count = len(unique_numbers)

print(count)

Погодьтесь, зовсім непогано.

Друга задача —  «Світлофори»

https://www.eolymp.com/uk/problems/993

Умова:

У підземеллі m тунелів і n перехресть, кожен тунель з'єднує якісь два перехрестя. Мишиний король вирішив поставити по світлофору у кожному тунелі перед кожним перехрестям. Напишіть програму, яка порахує, скільки світлофорів повинно бути встановлено на кожному з перехресть. Перехрестя пронумеровані числами від 1 до n.

Вхідні дані

У першому рядку записано два числа n і m (0 < n ≤ 100, 0 ≤ m ≤ n · (n - 1) / 2). У наступних m рядках записано по два числа i та j (1 ≤ i, j ≤ n), які означають, що перехресткя i та j з'єднані тунелем.

Вихідні дані

Вивести n чисел: k-те число означає кількість світлофорів на k-му перехресті.

Можна вважати, що довільні два перехрестя з'єднані не більше, ніж одним тунелем. Немає тунелів від перехрестя i до нього самого.

(зображеня з сайту eolymp.com)

Приклад

Вхідні дані:

7 10

5 1

3 2

7 1

5 2

7 4

6 5

6 4

7 5

2 1

5 3

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

3 3 2 2 5 2 3

На сайті eolymp.com задачу по класифікації віднесено до групи «теорія графів». І це певною мірою може злякати учнів. Бо чули про алгоритми Дейкстри, про різні обходи графів і все це не такі вже прості задачі. Але тут задача проста, незважаючи на лякаючу картинку.  

З умови нам відома кількість перехресть. Можна створити список на таку саму кількість елементів і заповнити цей список нулями. І коли будемо аналізуватися кожен тунель, то він починається з перехрестя і завершується перехрестям. Відповідно біля перехрестя де починається тунель ставиться один світлофор і біля перехрестя, де завершується тунель ставиться так само один світлофор. Відповідно, при опрацюванні кожного тунелю будемо збільшувати на одиничку значення двох перехресть  — перехрестя початку і перехрестя завершення тунелю.  Після опрацювання всіх тунелів у нас буде відома кількість світлофорів біля кожного перехрестя.

Це мій давній розв’язок цієї задачі. Чому у мене перехрестя (crossing) названі змінною s – не знаю, вибачайте:

n, m = map(int, input().split())

s = [0 for i in range(n)]

for _ in range(m):

    i, j = map(int, input().split())

    s[i - 1] += 1

    s[j - 1] += 1

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

А тепер передамо умову цієї задачі AI сайту replit.com

Без адаптації, методом copy-paste:

Ось перший варіант, запропонований AI:

n, m = map(int, input().split())

traffic_lights = [0] * n

for _ in range(m):

    i, j = map(int, input().split())

    traffic_lights[i-1] += 1

    traffic_lights[j-1] += 1

print(" ".join(map(str, traffic_lights)))

Ще один варіант, запропонований AI:

def calculate_traffic_lights(n, m, tunnels):

    intersections = [0] * n

    for i, j in tunnels:

        intersections[i - 1] += 1

        intersections[j - 1] += 1

    return ' '.join(map(str, intersections))

n, m = map(int, input().split())

tunnels = [list(map(int, input().split())) for _ in range(m)]

calculate_traffic_lights(n, m, tunnels)

print(calculate_traffic_lights(n, m, tunnels))

В останньому рядку я лише додав print, щоб вивести результат. Погодьтесь, все зрозуміло.

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

ps. Дякую Захару Зінчуку, який звернув увагу на якість запропонованих AI рішень.

Анатолій Анатолійович