Районна олімпіада 2019 (розбір) | Статті

A. Перехiд дороги

Задано масив цілих чисел. Треба сказати, скільки є таких індексів $i$, що $a_i$ та $a_{i+1}$ різної парності.

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

B. Щасливенькі числа

Задано натуральне число $n$. Треба сказати кількість натуральних чисел, що не перевищують $n$, таких, що їхня сума цифр — щаслива.

Переберемо всі числа від 1 до $n$ і перевіримо, чи сума цифр щаслива.

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

C. Покращення середнього балу

Задано масив чисел. Можна видалити деякі з них так, щоб сума чисел, які залишаться, була не меншою за $x$ і середнє арифметичне цих чисел було максимальне.

Ми хочем, щоб $\frac{sum}{count}$ чисел, які залишаться, було максимальним. Припустимо, що в нас фіксований $count$, тоді ми хочем максимізувати суму. Тоді нам достатньо видалити $n-count$ найменших чисел, щоб максимізувати суму.

Оптимальним рішенням задачі буде видаляти найменше число, поки це можливо.

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

D. Нерівноправна гра

Марічка й Зеник грають у гру. Є $n$ купок каменів. Марічка ходить першою і може вибрати підмножину купок розміру від 1 до $n-1$ і забрати будь-яку ненульову кількість каменів з кожної із цих купок. Зеник має право забирати будь-яку ненульову кількість каменів тільки з однієї купки. Програє той хто не зможе зробити ходу. Хто виграє при оптимальній грі обох?

Припустим, $n \ge 3$. Марічка може забрати 1 купку першим ходом. Незалежно від ходу Зеника на наступному ході Марічки буде щонайменше $n-2$ купки і не більше ніж $n-1$ купка, тому Марічка зможе забрати їх усіх. Якщо $n = 2$, то Зеник виграє тоді й тільки тоді, коли $a_0 = a_1$. Він зможе завжди повторювати хід Марічки, але в протилежну купку. Інакше виграє Марічка, звівши гру першим ходом до гри, де $a_0 = a_1$

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

E. Математична задача

У вас є число $n < 10^9$. Ви можете поділити (якщо ділиться) його на 4 або відняти 7. Треба сказати, чи можна отримати 1.

Розглянемо задачу з іншого боку — ми можем помножити число на 4 й додати 7. Переберем кількість множень на 4. Їх буде не більше ніж $\log_4 n$. Нехай кількість множень — $x$. Наше число — це $4^x$ і тепер ми можемо додати $7 \cdot 4^y$, де $y \le x$. Будем додавати числа жадібно — знаходити таке найбільше $y$, що $7 \cdot 4^y$ в сумі з нашим поточним числом менше або рівне тому числу, яке нам потрібне.

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

F. Хімічні експерименти

Вам задано натуральне число $n$, та потрібно сказати яку максимальну кількість елементів можна вибрати з множини $\{1, 2, \ldots, n\}$, так щоб жодні два вибрані елементи не відрізнялись на 4 або 7.

Спершу наведемо приклад розв’язку динамічним програмуванням. Позначимо через $dp[i][mask]$ найбільшу кількість елементів, які ми можемо вибрати з множини $\{1, 2, ..., i\}$, причому маска $mask$ відповідає за те, чи брали ми 7 останніх елементів. З кожного стану є не більше ніж два переходи: ми можемо або взяти поточний елемент (якщо він не конфліктуватиме із жодним з попередніх), або ж пропустити його.

Складність такого алгоритму: $O(n \cdot 2^7)$ по часу та пам’яті, що проходитиме  80% тестів, втім його можна оптимізувати до $O(n)$ по пам’яті, тримаючи динаміку пошарово, хоч це й доволі складно реалізовувати.

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

Другий розв’язок конструктивний. Розглянемо групу з 11 елементів, що йдуть підряд. Можна показати (або на папері, або програмно згенерувати попереднім розв’язком), що з них не можна вибрати більше ніж 5 елементів, що не конфліктуватимуть між собою. Причому саме 5 елементів можна вибрати, наприклад, узявши набори $\{1, 3, 4, 6, 9\}$ чи $\{1, 2, 4, 7, 10\}$. Тепер будуватимемо відповідь так: розіб’ємо множинну $\{1, 2, \ldots, n\}$ на блоки по 11 чисел у кожному (можливо, менше в останньому). Ясно, що з кожного блоку ми можемо взяти не більше ніж 5 чисел. Розглянувши кілька простих випадків, бачимо, що якщо остача $n$ за модулем 11 рівна 2, то можна в кожній групі вибирати елементи з множини остач $\{1, 2, 4, 7, 10\}$, а в інших випадках — з множини $\{1, 3, 4, 6, 9\}$. Формальне доведення залишаємо вам на домашнє завдання :)

Складність такого розв’язку: $O(n)$ по часу та $O(1)$ по пам’яті.

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

G. Фізичні експерименти

Вам задано $n$ ламп, кожна початково може бути або вимкненою, або ввімкненою. Вам потрібно зробити рівно $n$ ходів, на $i$-ому з них ви вибираєте рівно $i$ ламп та змінюєте їхній стан на протилежний. Чи можна вимкнути всі лампи?

Як і в попередній задачі, опишемо два розв’язки — конструктивний та за допомогою динамічного програмування.

Спершу розв’язок динамічним програмуванням. Нехай $dp[i][j]$ — це кількість ламп, які треба було вимкнути на $і$-ому кроці, щоб після нього рівно $j$ ламп були ввімкнені. Зауважимо, що таких можливих кількостей може бути декілька. У такому разі $dp[i][j]$ — будь-яка з них. Якщо ж після $i$-ого кроку взагалі неможливо мати рівно $j$ ввімкнених ламп, то в $dp[i][j]$ триматимемо відповідну мітку (наприклад, -1).

Якщо після $i$-ого кроку в нас рівно $j$ увімкнених ламп і на $(i + 1)$-ому кроці ми вимикаємо $k$ ламп, то вмикаємо $(i + 1 - k)$ ламп. Тоді кількість ввімкнених ламп стане $(j - k + i + 1 - k)$. Тобто, якщо в стан $dp[i][j]$ можливо перейти, то можна оновити $dp[i + 1][j - k + i + 1 - k]$ значенням $k$. Якщо в стан $dp[n][0]$ неможливо прийти, то відповідь — No. Інакше — Yes. Для кожного стану ми знаємо, скільки ламп треба було вимкнути на попередньому кроці, і можемо симулювати процес. Складність: $O(n^3)$ часу та $O(n^2)$ пам’яті.

Конструктивний розв’язок. Покажемо, що з початкового стану ми завжди можемо перейти в стан, де всі (крім, можливо, однієї) лампи є вимкнутими. Спочатку зауважимо, що порядок ходів не має значення, тому робитимемо спочатку $n$ перемикань, потім $n - 1$ і так далі. Підтримуватимемо такий інваріант: після ходу з $і$ перемиканнями є не більше за $i$ ввімкнених ламп. Спочатку таке, звісно ж, виконується. На кожному кроці будемо в першу чергу вимикати всі ввімкненні лампи, а в другу — вмикати вимкнуті. Якщо на якомусь кроці ми маємо змінити стан $i$ ламп, причому на його початку було не більше ніж $i + 1$ ввімкнута лампа, то таким процесом ми залишимо не більше за $і$ ввімкнутих ламп.

Тепер покажемо, що з ніякого стану ми не можемо перейти якимись ходами в стан, де всі лампи вимкнуті, а якимись іншими — де всі, крім рівно однієї, вимкнуті. Це зрозуміло з міркувань парності, адже парності кількостей перемикань всіх ламп у цих двох кінцевих станах відрізняються, що неможливо з огляду на те, що сума перемикань для досягнення кожного з них є однаковою, а саме $1 + 2 + \ldots + n = \frac{n \cdot (n + 1)}{2}$, де $n$ — початкова кількість ламп.

Тому ми виконуватимемо процес, описаний у першій частині, і якщо в кінцевому стані всі лампи вимкнені, то це і є розв’язок, інакше — розв’язку не існує.

Складність такого розв’язку: $O(n^2)$ часу та пам’яті.

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