Задача 1. Игра в мяч Дети встали в круг и бросают друг другу мяч. Известно, что каждый ребёнок бросает мяч всегда одному и тому же ребёнку, например, первый ребёнок бросает всегда седьмому, второй ребёнок всегда бросает третьему, и так далее. Известно, у какого ребёнка находится мяч в начале игры. Требуется определить, у какого ребёнка будет мяч после заданного количества бросков. Входные данные В первой строке записываются целые числа n – количество детей, a – номер ребёнка, у которого находится мяч в начале игры, и m – количество бросков мяча (2 ≤ n ≤ 1000, 1 ≤ a ≤ n, 0 ≤ m ≤ 1000000). Во второй строке содержится n целых чисел k1, k2, …, kn, где ki – номер ребёнка, которому бросает мяч ребёнок номер i (1 ≤ ki ≤ n, ki ≠ i). Выходные данные Выведите номер ребёнка, у которого окажется мяч в конце игры.
More Questions From This User See All
Answers & Comments
Verified answer
Если 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)