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

A. «Камiнь-ножицi-папiр»

Порахуємо, скільки разів Марічка може виграти каменем. Ця кількість не може бути більша за кількість ігор, у яких Марічка поставила камінь, і не може бути більша за кількість ігор, у яких Зеник поставив ножиці, тобто $min(r_M, s_Z)$. Аналогічно, кількість ігор, у яких Марічка може перемогти ножицями й папером рівна $min(s_M, p_Z)$ i $min(p_M, r_Z)$, відповідно. Відповідь до задачі буде рівна сумі цих трьох доданків.

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

B. Пошук паліндрома

Нехай кількість одиниць рівна $a$, а кількість нулів рівна $b$. Якщо $a \le b$ тоді $2 \cdot a \le a + b = n$. Тому одиниць є не більше ніж половина, і якщо ми видалимо їх усіх, то отримаємо рядок з нулів, який є паліндромом. Аналогічно, коли $b \le a$, ми можемо видалити всі нулі й отримати рядок з одиниць, який також є паліндромом.

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

C. Найкраща назва

Можна зауважити, що оптимальний рядок — це конкатенація рядків виду bohdan, danylo, maksym та bohdanylo. Без обмеження загальності, уважатимемо, що $d \le b$, а отже немає сенсу використовувати рядок danylo в нашій назві (якщо він не є частиною рядка bohdanylo).

Розглянемо два варіанти:

• Не використовувати рядок maksym у назві. Припустимо, що в оптимальній назві рядок bohdan зустрічається принаймні 9 разів, а bohdanylo — принаймні 6 разів. Тоді при заміні дев’яти рядків bohdan на шість рядків bohdanylo (або навпаки) прибуток не зменшиться, а отже існує оптимальна назва, де кількість рядків bohdan менша ніж 9, або кількість рядків bohdanylo менша ніж 6. Тому переберемо кількість рядків bohdan від 0 до 8, а рeшту вільного місця виділимо під рядок bohdanylo (та навпаки). У такий спосіб ми отримаємо оптимальну назву для команди.

• Використаємо рядок maksym принаймні один раз. Тоді легко бачити, що рядки maksym ітимуть поряд, і для $1 \le k$ рядків maksym потрібно рівно $5k + 1$ символів. Аналогічно до попереднього пункту, можна показати, що існує оптимальна назва, у якій або кількість рядків maksym, або bohdan, або bohdanylo не перевищує, наприклад, 20 (існують і строгіші оцінки). Тому перебравши кількість рядків одного із цих типів, зведемо отриману задачу до попереднього пункту (див. код для кращого розуміння).

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

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

D. Розбиття на прямокутники

Розв’язок зі складністю $O(nmk)$. Переберемо всі можливі $a$ і $b$ та перевіримо, чи точки, що з’єднані між собою, належать різним прямокутникам.

Розв’язок зі складністю $O(n(m^2+k))$. Переберемо $a$. Якщо для деяких з’єднаних точок $(x_1, y_1), (x_2, y_2)$ виконується $\left \lfloor{\frac{x_1}{a}}\right \rfloor \ne \left \lfloor{\frac{x_2}{a}}\right \rfloor$, то ці точки будуть у різних прямокутниках. Тепер розглядаємо лише ті пари точок, для яких ця умова не виконується. Треба задовольнити умову $\left \lfloor{\frac{y_1}{b}}\right \rfloor \ne \left \lfloor{\frac{y_2}{b}}\right \rfloor$.

Тепер маємо одновимірну задачу. Для її розв’язання заведемо масив $d$. Значення $d[i]$ означає найменшу $y$-координату, не меншу за $i$, серед усіх точок, що з’єднані з якоюсь точкою з $y$-координатою рівною $i$. Іншими словами, це координата найближчої зверху точки, з’єднаної з точкою з $y$-координатою рівною $i$. Після обчислення такого масиву можемо перебрати $b$ та перевірити, чи виконується умова $\left \lfloor{\frac{i}{b}}\right \rfloor \ne \left \lfloor{\frac{d[i]}{b}}\right \rfloor$ для всіх $i$.

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