Ещё одно красивое решение задачи на Python, благодаря слайсам. К тому же, это одна из тех задач, где нужно сначала провести небольшое исследование:
Простыми словами из математики в этой задаче требуется найти минимальный период.
Ограничения на входные данные кажутся довольно большими. Так и есть, если вы захотели перебрать все варианты, и для каждого из них пройтись по массиву и убедиться, что элементы совпадают.
Перебор можно сократить, заметив, что барабан сделал целое число оборотов. Ведь тогда получается, что количество секторов на барабане является делителем числа n - 1 (единичку вычитаем, потому что в последовательности записан сектор, на котором остановились, он же является и первым).
Отлично, значит проходить по массиву надо будет лишь в том случае, если остаток от деления равен 0. Но вдруг и этого будет недостаточно?
В таком случае, мы можем быстро накидать функцию, которая вычисляет количество делителей у числа:
И вызвать её для всех чисел от 1 до 30000:
Да, придётся немного подождать, но так мы точно убедимся, что количество делителей (количество проходов по массиву для проверки) для всех чисел из входных условий не будет превышать 96 (у числа 27720).
Быстро прикинув, что 100 проходов по массиву из 30000 элементов не очень долго, можно написать решение на Python:
Обращу внимание на несколько особенностей и важных моментов.
Здесь я не стал переводить данные в массиве в числа, а работал с ними как со строками, так как в этой задаче не нужны арифметические операции. Но надо помнить, что сравнение строк обычно дольше, чем чисел. В этой задаче это оказалось не так критично, поэтому можно чуть сократить код.
Важным является порядок сравнений в условии, так как интерпретатор Python (как и всех современных языков программирования) ведёт себя лениво: если первая часть составного условия с and оказалась ложной (и уже можно сделать вывод, что всё условие тоже будет ложно), то вторая часть не проверяется. Аналогично интерпретатор ведёт себя и с составными условия со связкой or. А нам это позволяет не писать вложенный if с проверкой равенства массивов.
Получилось довольно короткое решение, но с предварительной подготовкой. Если бы входные данные были больше, и результаты работы нашей вспомогательной программы пришлось ждать долго, то можно было бы воспользоваться примерной оценкой: количество делителей не превышает квадратного корня из числа (кроме экзотических случаев с маленькими числами, вроде 2 и 3), а для больших чисел примерно равно кубическому корню из числа.
Предыдущий выпуск: Задача 71. Две кучки камней
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.