Задано масив цілих чисел. Треба сказати, скільки є таких індексів \(i\), що \(a_i\) та \(a_{i+1}\) різної парності.
Задано натуральне число \(n\). Треба сказати кількість натуральних чисел, що не перевищують \(n\), таких, що їхня сума цифр — щаслива.
Переберемо всі числа від 1 до \(n\) і перевіримо, чи сума цифр щаслива.
Задано масив чисел. Можна видалити деякі з них так, щоб сума чисел, які залишаться, була не меншою за \(x\) і середнє арифметичне цих чисел було максимальне.
Ми хочем, щоб \(\frac{sum}{count}\) чисел, які залишаться, було максимальним. Припустимо, що в нас фіксований \(count\), тоді ми хочем максимізувати суму. Тоді нам достатньо видалити \(n-count\) найменших чисел, щоб максимізувати суму.
Оптимальним рішенням задачі буде видаляти найменше число, поки це можливо.
Марічка й Зеник грають у гру. Є \(n\) купок каменів. Марічка ходить першою і може вибрати підмножину купок розміру від 1 до \(n-1\) і забрати будь-яку ненульову кількість каменів з кожної із цих купок. Зеник має право забирати будь-яку ненульову кількість каменів тільки з однієї купки. Програє той хто не зможе зробити ходу. Хто виграє при оптимальній грі обох?
Припустим, \(n \ge 3\). Марічка може забрати 1 купку першим ходом. Незалежно від ходу Зеника на наступному ході Марічки буде щонайменше \(n-2\) купки і не більше ніж \(n-1\) купка, тому Марічка зможе забрати їх усіх. Якщо \(n = 2\), то Зеник виграє тоді й тільки тоді, коли \(a_0 = a_1\). Він зможе завжди повторювати хід Марічки, але в протилежну купку. Інакше виграє Марічка, звівши гру першим ходом до гри, де \(a_0 = a_1\)
У вас є число \(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\) в сумі з нашим поточним числом менше або рівне тому числу, яке нам потрібне.
Вам задано натуральне число \(n\), та потрібно сказати яку максимальну кількість елементів можна вибрати з множини \(\{1, 2, \ldots, n\}\), так щоб жодні два вибрані елементи не відрізнялись на 4 або 7.
Спершу наведемо приклад розв’язку динамічним програмуванням. Позначимо через \(dp[i][mask]\) найбільшу кількість елементів, які ми можемо вибрати з множини \(\{1, 2, ..., i\}\), причому маска \(mask\) відповідає за те, чи брали ми 7 останніх елементів. З кожного стану є не більше ніж два переходи: ми можемо або взяти поточний елемент (якщо він не конфліктуватиме із жодним з попередніх), або ж пропустити його.
Складність такого алгоритму: \(O(n \cdot 2^7)\) по часу та пам’яті, що проходитиме 80% тестів, втім його можна оптимізувати до \(O(n)\) по пам’яті, тримаючи динаміку пошарово, хоч це й доволі складно реалізовувати.
Другий розв’язок конструктивний. Розглянемо групу з 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)\) по пам’яті.
Вам задано \(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)\) часу та пам’яті.