Порахуємо, скільки разів Марічка може виграти каменем. Ця кількість не може бути більша за кількість ігор, у яких Марічка поставила камінь, і не може бути більша за кількість ігор, у яких Зеник поставив ножиці, тобто \(min(r_M, s_Z)\). Аналогічно, кількість ігор, у яких Марічка може перемогти ножицями й папером рівна \(min(s_M, p_Z)\) i \(min(p_M, r_Z)\), відповідно. Відповідь до задачі буде рівна сумі цих трьох доданків.
Нехай кількість одиниць рівна \(a\), а кількість нулів рівна \(b\). Якщо \(a \le b\) тоді \(2 \cdot a \le a + b = n\). Тому одиниць є не більше ніж половина, і якщо ми видалимо їх усіх, то отримаємо рядок з нулів, який є паліндромом. Аналогічно, коли \(b \le a\), ми можемо видалити всі нулі й отримати рядок з одиниць, який також є паліндромом.
Можна зауважити, що оптимальний рядок — це конкатенація рядків виду
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)\) часу та пам’яті.
Розв’язок зі складністю \(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\).