Районна олімпіада 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\).

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