Подзадача 1: N ≤ 8.
В этой подзадаче можно решить задачу “на бумаге”. Мы можем перебрать все возможные варианты разделения слова на две части. Например, для N = 5 мы можем разделить слово УЛУУУЛУУ на УЛУУ и УУЛУ или на УЛУУУ и ЛУУ. Затем мы проверяем, сколько раз можно прочитать каждую из двух частей, и выбираем наименьшее значение. В конечном итоге, ответом будет наименьшее количество прочтений одного слова.
Шаги решения:
1. Считываем значение N.
2. Инициализируем переменную minReads значением infinity.
3. Перебираем значения i от 1 до N – 1:
– Делим слово на две части: substring1 = УЛУУ…УЛУ (длина i) и substring2 = УЛУУ…УЛУ (длина (N – i)).
– Вычисляем, сколько раз можно прочитать каждую часть:
* reads1 = (N – i) // gcd(N – i, i)
* reads2 = i // gcd(i, N – i)
– Обновляем minReads, если reads1 или reads2 меньше текущего значения minReads.
4. Выводим значение minReads.
Подзадача 2: N ≤ 100.
В этой подзадаче мы можем использовать более эффективный подход для решения задачи. Заметим, что слово УЛУУ повторяется с периодом наименьшего общего делителя (НОД) длины слова и позиции делителя. То есть, период повторения будет равен НОД(N, i), где i – позиция делителя от 1 до N – 1.
Таким образом, мы можем найти НОД(N, i) для каждого i от 1 до N – 1 и выбрать наименьшее значение периода повторения. Затем мы можем вычислить количество прочтений слова, разделив длину слова на период повторения.
Шаги решения:
1. Считываем значение N.
2. Инициализируем переменную minPeriod значением infinity.
3. Перебираем значения i от 1 до N – 1:
– Вычисляем НОД(N, i) и обновляем minPeriod, если НОД(N, i) меньше текущего значения minPeriod.
4. Вычисляем количество прочтений слова: reads = N // minPeriod.
5. Выводим значение reads.