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

Question

Информатика

Юлюся

5 ноября, 14:33

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

+4

Ответы (1)

Знаете ответ на вопрос?

Томуня · 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)