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

A. Політ на Марс

Знаючи відстань і швидкість, час подорожі можна порахувати відомою формулою \(t = \frac{s}{v}\), отже відповідь — це \(\frac{225000000}{v}\).

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

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

B. Стипендія

Зчитавши циклом кожну оцінку, потрібно перевірити, чи є хоча б одна оцінка нижча за 51. Якщо така оцінка є, стипендії не буде. Інакше потрібно перевірити, чи є хоча б одна оцінка нижча за 90, тоді стипендія буде звичайною. У протилежному разі стипендія буде підвищеною.

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

C. Стоянка

Потрібно знайти кількість прямокутників з координатами верхнього лівого кута \((x_1, y_1)\) та нижнього правого \((x_2, y_2)\), у межах якого кількість одиниць більша за кількість нулів.

Перепозначимо 0 як -1 у заданій таблиці. Це дозволить нам шукати кількість прямокутників, сума чисел у яких є додатною.

Переберемо \(x_1\) та \(x_2\), і для кожного \(j\) (\(1 \le j \le m\)) будемо підтримувати суму \(s_j\) усіх елементів у стовпці \(j\) між рядками \(x_1\) та \(x_2\). Після цього задача зводиться до одновимірного випадку — потрібно знайти кількість проміжків з додатною сумою. Аналогічно першим циклом переберемо \(y_1\), а другим — \(y_2\), підтримуючи суму усіх \(s_j\) між ними. Якщо ця сума додатна, то прямокутник між \((x_1, y_1)\) та \((x_2, y_2)\) є шуканим, тому додаємо 1 до відповіді.

Складність розв’язку — \(O(n^2m^2)\) з дуже малою константою.

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

D. Зеник і Марсіанська перестановка

Зауважмо, що для того, аби поміняти місцями два елементи з індексами \(i\) та \(j\), потрібно аби абсолютна різниця цих індексів \(|i-j|\) ділилася на \(k\). Це можна пояснити тим, що будь-яка операція обміну, описана в умові, відбувається завжди між елементами в індексах з однаковою остачею від ділення на \(k\).

Отже, для того, аби посортувати перестановку, потрібно аби абсолютна різниця поточної позиції елемента та його позиції в посортованому масиві (\(|p_i - i|\)) ділилась на \(k\) для всіх \(i\) від 1 до \(n\) включно. Обчислимо \(g\) — найбільший спільний дільник (НСД) усіх абсолютних різниць \(|p_i - i|\). Неважко побачити, що число \(g\), а також усі його дільники, будуть відповіддю до задачі.

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