Задача 1. Игра в мяч Дети встали в круг и бросают друг другу мяч. Известно, что каждый...

Question

Задача 1. Игра в мяч Дети встали в круг и бросают друг другу мяч. Известно, что каждый ребёнок бросает мяч всегда одному и тому же ребёнку, например, первый ребёнок бросает всегда седьмому, второй ребёнок всегда бросает третьему, и так далее. Известно, у какого ребёнка находится мяч в начале игры. Требуется определить, у какого ребёнка будет мяч после заданного количества бросков. Входные данные В первой строке записываются целые числа n – количество детей, a – номер ребёнка, у которого находится мяч в начале игры, и m – количество бросков мяча (2 ≤ n ≤ 1000, 1 ≤ a ≤ n, 0 ≤ m ≤ 1000000). Во второй строке содержится n целых чисел k1, k2, …, kn, где ki – номер ребёнка, которому бросает мяч ребёнок номер i (1 ≤ ki ≤ n, ki ≠ i). Выходные данные Выведите номер ребёнка, у которого окажется мяч в конце игры.

Answer 1

Если m > n, то рано или поздно процесс зациклится. Найдём этот цикл (O(n)), а затем за O(n) получим ответ. Для удобства в массивы добавлен пустой нулевой элемент.

python 3.5
a, m, n = map(int, input().split())
to = [None for _ in range(n + 1)]
to[0], to[1:] = None, map(int, input().split())
first_pass = [None for _ in range(n + 1)]
length_of_cycle = None

move = 1
current_kid = a
while move < m:
    if length_of_cycle is None:
        if first_pass[current_kid] is not None:
            length_of_cycle = move - first_pass[current_kid]
            move += (m - move) // length_of_cycle * length_of_cycle
            if move == m:
                break
        else:
            first_pass[current_kid] = move
    move += 1
    current_kid = to[current_kid]

print(current_kid)