Задача Задача №3723583
А
А
Краткий ответ: пройдём по ответам слева направо и будем хранить длину текущей серии единиц и длину лучшей серии.
import sys
input = sys.stdin.buffer.readline
n = int(input())
current_len = 0
current_start = 0
best_len = 0
best_start = 0
for question in range(1, n + 1):
answer = int(input())
if answer == 1:
# Начало новой серии
if current_len == 0:
current_start = question
current_len += 1
# Обновляем лучшую серию только при строгом увеличении.
# Поэтому при равенстве останется более ранняя серия.
if current_len > best_len:
best_len = current_len
best_start = current_start
else:
# Неверный ответ прерывает серию
current_len = 0
print(best_len)
print(best_start if best_len > 0 else 0)
Как работает алгоритм
- Если встретили
1, увеличиваем длину текущей серии. - Если это первая единица серии, запоминаем её номер.
- Если встретили
0, текущая серия заканчивается, поэтому её длина становится равной0. - Если текущая серия длиннее лучшей, сохраняем её.
- Используется условие
>, а не>=: при одинаковой длине останется серия, которая началась раньше.
Для примера на изображении серии имеют длины \(2\), \(3\) и \(3\). Самая длинная начинается с вопроса №4, поэтому вывод:
3
4
Сложность решения — \(O(n)\) по времени и \(O(1)\) по дополнительной памяти.
