Условие:
Решение на Python
Ограничение времени 1 секунда 15 секунд
Ограничение памяти 64 Мб 64 Мб
Ввод стандартный ввод
Вывод стандартный вывод
На крупном заводе решили проверить эффективность работы погрузчиков и провели
эксперимент: установили на складах датчики iBeacon и отслеживали перемещение
погрузчиков между различными зонами.
Каждая зона склада обозначается уникальным целым числом. Когда погрузчик перемещается
из одной зоны в другую, система регистрирует номер новой зоны, в которую он въехал. В
результате движение каждого погрузчика представлено в виде последовательности чисел.
Инженеры завода считают, что наиболее эффективный путь, который может совершить
погрузчик, — это поездка из некоторой начальной зоны в конечную, а затем возвращение по
тому же маршруту обратно. Такая последовательность перемещений формирует так
называемый «идеальный маршрут».
Вам необходимо найти длину самого длинного «идеального маршрута» в записи перемещений
погрузчика.
Формат ввода
Первая строка содержит одно целое число п (1 < п < 104) — количество записей о
перемещениях погрузчика.
Вторая строка содержит п целых чисел а1, а2, ..., аn (1 <аi < 109) — последовательность зон, через
которые проехал погрузчик.
Формат ввода
Первая строка содержит одно целое числоп (1 < п < 104) — количество записей о
перемещениях погрузчика.
Вторая строка содержит п целых чисел ат, а», ..., а» (1 <а, < 109) — последовательность з‹
которые проехал погрузчик.
Формат вывода
Выведите одно целое число — длину самого длинного «идеального маршрута» в записях
перемещений. Если такого маршрута не существует, выведите 0.
Пример 1
Ввод
7
1 2 3 4 3 2 1
Вывод
7
Пример 2
Ввод
5
1 2 3 4 5
Вывод
0
Решение:
Для решения задачи о нахождении самого длинного идеального маршрута погрузчика, мы можем использовать подход с использованием словаря для отслеживания индексов, где каждая зона впервые появляется. Затем мы будем проверять, образует ли последовательность перемещений идеальный маршрут.
Шаги решения:
1. Чтение входных данных: Сначала мы считываем количество перемещений и саму последовательность перемещений погрузчика.
2. Инициализация структуры данных: Создаем словарь для хранения индексов, где каждая зона впервые появляется.
3. Поиск идеальных маршрутов:
- Проходим по последовательности перемещений.
- Для каждой зоны проверяем, была ли она уже в словаре.
- Если была, то проверяем, образует ли текущая последовательность идеальный маршрут (т.е. если мы видим зону, которая уже была, и между ними есть последовательность, которая соответствует обратному порядку).
- Если идеальный маршрут найден, обновляем максимальную длину.
4. Вывод результата: Если максимальная длина маршрута осталась равной нулю, выводим 0, иначе выводим найденную максимальную длину.
Пример реализации на Python:
- Мы используем словарь , чтобы отслеживать индексы, где каждая зона впервые появляется. - При нахождении повторяющейся зоны мы проверяем, является ли последовательность между первым и текущим индексом идеальным маршрутом (т.е. симметричной). - Если такой маршрут найден, обновляем максимальную длину. - В конце выводим максимальную длину найденного маршрута. 1. Для ввода: Вывод будет , так как весь маршрут является идеальным. 2. Для ввода: Вывод будет , так как нет идеального маршрута.