Недавно Иван купил очень интересный детектив. На каждой странице книги появляется какая-то тайна, разгадка которой находится где-то дальше по тексту. Формально, i
-я страница содержит тайну, которая проясняется на странице ai
(ai≥i
).
Иван хочет прочесть всю книгу. Каждый день он читает первую из еще не прочитанных страниц и продолжает читать их подряд, пока не прояснятся все тайны, о которых он прочитал (Иван прекращает чтение, если не существует такой страницы i
, что ее Иван прочитал, а ai
— нет). После этого он закрывает книгу и откладывает чтение следующей страницы до завтра.
Сколько дней понадобится Ивану, чтобы прочесть всю книгу?
9
1 3 3 6 7 6 8 8 9
выходные данные
4
Пояснение к примеру из условия:
В первый день Иван прочтет только первую страницу. Во второй день он прочтет страницы 2
и 3
. В третий день — страницы 4
-8
. В четвертый и последний день Иван прочтет оставшуюся 9
def days_to_read_book(a):
days = 0 # Счетчик дней
current_page = 0 # Текущая страница, начинаем с первой страницы
max_a = 0 # Максимальный индекс страницы, до которой нужно дойти
# Проходим по всем страницам книги
for i in range(len(a)):
# Обновляем max_a, если текущая страница содержит ссылку на более позднюю страницу
max_a = max(max_a, a)
# Если текущая страница равна max_a, это означает, что все тайны до этой страницы разгаданы
if i == max_a - 1:
days += 1 # Заканчиваем чтение на этот день
return days
# Пример из условия
a = [1, 3, 3, 6, 7, 6, 8, 8, 9]
print(days_to_read_book(a))