Чудово, коли все чітко, як домовлялися. Ви купили квиток у застосунку, гроші з картки без проблем списалися. В потрібний час ви прийшли на перон, сіли в потяг, що стоїть саме на цьому пероні. Ваше місце у вагоні ніхто не зайняв і потяг вчасно приїхав до пункту призначення. Все чітко і надійно — як у німців. Чудово, так? До речі, а хто вам сказав, що в Deutsche Bahn завжди саме так? Хтось казав? І ви от просто так наївно та безкоштовно повірили? )
Погодьтесь, у реальних системах часто виникає багато проблемних ситуацій. Частину з них розробники передбачають і закладають відповідні алгоритми обробки, частину виловлюють при тестуваннях, решта дістається службам підтримки.
Якщо ми говоримо про формулювання умови в програмуванні, то програмісти хочуть щоб лаконічно та однозначно. Нічого зайвого, нічого такого, що можна зрозуміти по-різному. Але сьогодні ми розв’язуємо задачу з «поганою» умовою. Де купа зайвих деталей, кольоровий навоз та екстравагантний президент Бананової республіки. Але то реальне життя, а не чітка стерильність професійних авторів олімпіадних батлів.
Задача: «Кольоровий дощ»
https://basecamp.eolymp.com/uk/problems/994
У Банановій республіці дуже багато пагорбів, з'єднаних мостами. На хімічному заводі відбулась аварія, у результаті чого випарувалось експериментальне добриво "зован". На наступний день випав кольоровий дощ, причому він пройшов лише над пагорбами. У деяких місцях падали червоні каплі, у деяких - сині, а в інших - зелені, у результаті чого пагорби стали відповідного кольору. Президенту Бананової республіки це сподобалось, але він забажав пофарбувати мости між вершинами пагорбів так, щоб мости були пофарбовані у колір пагорбів, які вони з'єднують. На жаль, якщо пагорби різного кольору, то пофарбувати міст таким чином не вдасться. Порахуйте кількість таких "не гарних" мостів.
Вхідні дані
У першому рядку записано кількість пагорбів n (0 < n ≤ 100). Далі йде матриця суміжності, яка описує наявність мостів між пагорбами (1-міст є, 0-немає). В останньому рядку записано n чисел, які позначають колір пагорбів: 1 - червоний; 2 - синій; 3 - зелений.
Вихідні дані
Вивести кількість "не гарних" мостів.
(фото до задачі з сайту basecamp.eolymp.com)
Приклади
Вхідні дані #1
7
0 1 0 0 0 1 1
1 0 1 0 0 0 0
0 1 0 0 1 1 0
0 0 0 0 0 0 0
0 0 1 0 0 1 0
1 0 1 0 1 0 0
1 0 0 0 0 0 0
1 1 1 1 1 3 3
Відповідь #1
4
Незважаючи на фото в умові, з якого на нас дивиться граф, незважаючи на двомірну матрицю, яку не всі діти люблять, задача, погодьтесь, нескладна. Записуємо матрицю суміжності у двовимірний список а список кольорів також у відповідний список. Далі — нескладний аналіз.
Повернемося до тестового прикладу. Згідно матриці суміжності і малюнку бачимо, що перший пагорб має мости з другим, шостим і сьомим пагорбом. Згідно умови, перший пагорб після кольорового дощу став червоний (1), другий – червоний (1), шостий – зелений (3), сьомий – також зелений(3). «Негарний» міст — це коли кольори пагорбів по його сторонах мають різний колір. Тому від першого пагорбу відходять два «негарних» мости 1-6, та 1-7.
Якщо ми опрацюємо таким чином всі пагорби, ми визначимо кількість «негарних» мостів. Звичайно, результат треба буде поділити на два, бо «негарний» міст 1-6 — це той самий міст, що і 6-1. Ось один з варіантів коду:
n = int(input())
m = []
bad_bridge = 0
for row in range(n):
m.append([int(element) for element in input().split()])
colors = [int(i) for i in input().split()]
for i in range(n):
for j in range(n):
if m[i][j]==1 and colors[i] != colors[j]:
bad_bridge += 1
print(bad_bridge // 2)
Все добре, але цей код здає задачу лише на 10%. Чому? Тому що специфічно написана умова. Зверніть увагу на тестовий приклад. Бачите після матриці суміжності пустий рядок? Про нього нема жодного слова в умові, але він є в тестовому прикладі. Я червоним кольором виділю рядок, який треба включити в програму:
n = int(input())
m = []
bad_bridge = 0
for row in range(n):
m.append([int(element) for element in input().split()])
input()
colors = [int(i) for i in input().split()]
for i in range(n):
for j in range(n):
if m[i][j]==1 and colors[i] != colors[j]:
bad_bridge += 1
print(bad_bridge // 2)
І от тепер задача буде прийнята системою на 100%.
Можна по різному це оцінювати. Формально, нам про необхідність пустого рядка у вхідних даних повідомили в тестовому прикладі, який є частиною умови. Але в умові, мабуть, варто про це писати текстом. Чи ні? Ви самостійно можете визначите власне відношення до такої ситуації. Чи варто учням-школярам давати такі задачі? А тим учням, що збираються бути айтішниками? Розв’язання таких задач сприяє розвитку критичного мислення? Купа філософських питань, відповіді на які я залишаю кожному з тих, хто сюди дочитав. Як таке відчуваєте саме Ви?
Анатолій Анатолійович
липень 2025
Сьогодні вкотре запрошую поговорити про красу. Хтось заради краси малює, хтось шукає красу в музиці, а в чому може бути краса у програмістів? Що може бути такого для програміста гарного, або, хоча б, прикольного?
Давайте розглянемо задачу в тему:
Маршрутне таксі
https://basecamp.eolymp.com/uk/problems/7410
У годину пік на зупинку одночасно під'їхали три маршрутних таксі, які слідують по одному маршруту, в які тут же набилися пасажири. Водії виявили, що кількість людей у різних маршрутках різна, і вирішили пересадити частину пасажирів так, щоб у кожній маршрутці було порівну пасажирів. Потрібно визначити, яку найменшу кількість пасажирів доведеться при цьому пересадити.
Вхідні дані
Три натуральних числа, що не перевищують 100 - кількості пасажирів у першій, другій і третій маршрутках відповідно.
Вихідні дані
Виведіть одне число - найменшу кількість пасажирів, яку потрібно пересадити. Якщо це неможливо, виведіть слово IMPOSSIBLE (великими літерами).
Приклади
Вхідні дані #1
1 2 3
Відповідь #1
1
Пропоную відразу розібратися, коли неможливо буде рівномірно розподілити пасажирів по маршрутках. Така ситуація виникне, коли загальна кількість пасажирів у всіх маршрутках не буде націло ділитися на три.
В інших випадках пересадити пасажирів можна. Можна визначити для початку, скільки пасажирів повинно бути після пересадки в кожній маршрутці — кількість всіх пасажирів поділити на три.
Далі по кожній маршрутці знайти кількість людей, які повинно вийти з кожної маршрутки або зайти в неї. Скористаємся модулем і врахуємо, що людина, що вийшла з однієї маршрутки, зайшла в іншу і при такому підході врахована двічі. Ось як може виглядати код:
a, b, c = map(int, input().split())
if (a + b + c) % 3 != 0:
print('IMPOSSIBLE')
else:
avg = (a + b + c) // 3
print((abs(avg - a) + abs(avg - b) + abs(avg - c)) // 2)
Це гарно? Мабуть, так. І вчителька математики не проти. Але чи існують ще гарні рішення?
А якщо прийде програміст Петрик, що проспав урок про модулі і скаже, що двічі рахувати пасажирів негарно, а він без усіляких модулів вирішив рахувати лише тих, хто виходить з маршруток для пересадки? Ось так:
counts = [int(x) for x in input().split()]
if sum(counts) % 3 != 0:
print('IMPOSSIBLE')
else:
avg = sum(counts) // 3
move = 0
for count in counts:
if count > avg:
move += count - avg
print(move)
А от це — гарно? Здається і це гарно, навіть якщо вчителька математики буде вважати, що не треба придумувати дурню і їсти картоплю черпаком.
А яких з кодів гарніший? А який — швидший? А який більше подобається саме Вам, шановний читач? А чому? Який код гарніший саме для Вас? Бо ми ж сьогодні — про красу.
Розглянемо задачу, що на basecamp.eolymp.com має дуже дивний коефіцієнт прийняття – 24%. При цьому для успішного розв’язання треба… уважно прочитати умову. Давайте розбиратися.
Подвоєння
https://basecamp.eolymp.com/uk/problems/6275
Подвоїти кожну цифру заданого тризначного числа.
Вхідні дані
Трицифрове ціле число.
Вихідні дані
Відповідь до задачі.
Приклади
Вхідні дані #1
123
Відповідь #1
112233
Здається, куди ж простіше? Але тоді незрозуміло чому такий низький кофеціцієнт прийняття.
Можливо, тому що автори задачі в тестах на початку понаставили пробілів. Бо ніхто ж нам не обіцяє, що число буде обов’язково «123». А якщо « 123». Якщо ми будемо розв’язувати задачу, сприймаючи вхідні дані як текст, то це важливо. Але ми можемо швидко обрізати всі пробіли, і на початку і на кінці: x = input().strip()
А далі, якщо знову-таки працюємо з текстовими даними, то можна, наприклад, так:
print(a[0] * 2 + a[1] * 2 + a[2] * 2)
Але задача здається лише на 60%. Що ж не так?
А якщо вхідними даними буде трицифрове число? Розв'яжемо, наприклад, так:
x = int(input())
x2, x3 = divmod(x, 10)
x1, x2 = divmod(x2, 10)
print(x1 * 100000 + x1 * 10000 + x2 * 1000 + x2 * 100 + x3 * 10 + x3)
І знову та сама проблема: задача приймається лише на 60%
Давайте хоч тут уважно прочитаємо умову )
Вхідні дані: трицифрове ціле число.
І тому просте питання: чи є число -123 трицифровим цілим числом?
Успіхів!
Сьогодні, в день Великодня давайте визначимо дату цього свята в різні роки.
Цю не саму тривіальну задачу намагалися розв’язати різними способами. Наприклад, в музеї Равенського собору в Італії знаходиться календар визначення дат Великодня на 95 років (532–626):
Фото з Вікіпедії
Ще та проблема цю графіку розтлумачити. Мабуть, саме так у 1800 році подумав Карл Фрідріх Гаусс і записав алгоритм визначення дня Великодня математично, формулами, при чому за старим і новим стилем. Через шість років його студент Петер Пауль Тіттель виявив помилку в алгоритмі щодо параметра p. Гаусс виправив цю помилку та подякував студенту за допомогу. Ще через 64 роки професор Базельського університету Герман Кінкелін поясненив кожен крок даного алгоритму. Ця все відомі факти, Вікіпедія досить непогано описує неспокійне життя церковників та математиків.
Як на мене, визначити дату Великодня за формулами Гаусса — це досить проста задача для програмістів-початківців. Тут і ділення націло і залишок від ділення і розгалуження.
Беремо алгоритм і пробуємо. У мене вийшло так, якщо цікаво.
Успіхів!
