Аркадный мяч: когда начнётся петля

В школьной аркаде стоит круг из n игроков, пронумерованных от 1 до n по часовой стрелке. Мяч начинает у игрока 1, и сначала он летит по часовой стрелке.

У каждого игрока i на футболке написано число a[i]. Игра идёт раундами.

Состояние игры — это (у кого мяч, направление полёта).

Правила одного раунда такие: 1) Пусть мяч у игрока i. Он кидает мяч на a[i] шагов в текущем направлении по кругу (шаг — перейти к соседу). Если a[i] может быть большим, берите шаги по модулю n. 2) Мяч прилетает к некоторому игроку j. Если a[j] — чётное, то направление меняется на противоположное. Если нечётное — направление не меняется.

Игра продолжается, пока в начале раунда не повторится какое-то состояние (то есть уже было раньше точно такое же «у кого мяч и куда летит»).

Нужно вывести:

• μ — сколько раундов прошло до первого состояния цикла (длина «разгона»),
• λ — длину самого цикла.

Формат ввода

В первой строке целое число n (2 ≤ n ≤ 8000). Во второй строке n целых чисел a1, a2, …, an (0 ≤ ai ≤ 10^9).

Формат вывода

Выведите два целых числа μ и λ.

Ограничения

• 2 ≤ n ≤ 8000
• 0 ≤ ai ≤ 10^9
• Время: 1500 мс, память: 256 МБ

Пример

Ввод:

5
1 3 2 1 4

Вывод:

2 4

Ключевое наблюдение: состояние игры полностью задаётся парой (позиция игрока, направление). Позиция — n вариантов, направление — 2 варианта, значит всего 2n состояний. Переход из состояния в следующее однозначный, то есть мы идём по «функциональному графу» и обязательно когда-нибудь попадём в уже встреченное состояние — с этого места начинается цикл.

Почему работает: если мы знаем, на каком раунде впервые встретили состояние S, а потом встретили S снова на раунде t, то

• μ = first_time[S] (сколько раундов до входа в цикл),
• λ = t - first_time[S] (длина цикла).

План:

• Храним seen[2][n], где seen[d][p] — номер раунда, когда в начале раунда впервые было состояние (p, d). Изначально везде -1.
• Старт: pos = 0 (игрок 1), dir = 0 (по часовой), t = 0.
• Пока seen[dir][pos] == -1:
• Записываем seen[dir][pos] = t.
• Делаем бросок на step = a[pos] % n шагов в текущем направлении, например:
• по часовой: pos = (pos + step) % n
• против: pos = (pos - step) % n
• После прилёта, если a[pos] чётное — меняем направление (dir ^= 1).
• t += 1.
• Когда цикл найден: mu = seen[dir][pos], lam = t - mu.

Сложность: максимум 2n итераций, то есть O(n) по времени и O(n) по памяти.

Частая ошибка: отмечать состояние после броска. По условию повтор ищем «в начале раунда», поэтому помечать нужно ДО перемещения.