Шкільна олімпіада 2020 (розбір) | Articles

A. Соціальна дистанція

Потрібно перевірити для всіх $i$ умову $x_{i+1}-x_i \ge 2$.

Код розв’язку С++

Код розв’язку Python

B. Розповсюдження вірусу

Один з варіантів, що дає максимальну кількість будинків з хворими — це коли початкові $k$ будинків з хворими знаходяться поруч на одній діагоналі. Тоді відповідь буде рівна $k^2$, але кількість будинків з хворими не може бути більшою за кількість будинків у місті. Отже, відповідь — min($k^2$, $n^2$).

Код розв’язку С++

Код розв’язку Python

C. Захисні маски

Зеник може в кожному магазині купувати одноразову маску. У цьому разі він заплатить $\sum_{i=1}^n a_i$. Цей дивний запис означає суму $a_i$ за всіма $i$ від 1 до $n$.

Якщо ж він вирішить придбати багаторазову маску в $j$-ому магазині, то йому доведеться купити одноразові маски в усіх магазинах перед $j$-им. Тоді він витратить $b_j + \sum_{i=1}^{j-1} a_i$. Можна перебрати $j$ — індекс магазину, де найвигідніше придбати багаторазову маску. Для цього будемо йти індексом $j$ від 1 до $n$ і підтримувати значення суми $a_i$ на префіксі.

Відповіддю буде найменший серед усіх цих варіантів.

Код розв’язку С++

Код розв’язку Python

D. Небезпечні друзі

Розглянемо граф, вершинами якого будуть люди, причому деякі пари з них будуть з’єднані ребрами, що означатиме дружбу між відповідними людьми.

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

Складність такого розв’язку — лінійна відносно розміру вхідних даних.

Код розв’язку С++

Код розв’язку Python