Чудово, коли все чітко, як домовлялися. Ви купили квиток у застосунку, гроші з картки без проблем списалися. В потрібний час ви прийшли на перон, сіли в потяг, що стоїть саме на цьому пероні. Ваше місце у вагоні ніхто не зайняв і потяг вчасно приїхав до пункту призначення. Все чітко і надійно — як у німців. Чудово, так? До речі, а хто вам сказав, що в 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