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

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