Solve D that could not be solved yesterday
** Thoughts ** Since $ K $ is big, it seems that it can not be solved unless it is looped somewhere → Let's detect the loop. And it will be classified according to the size of $ K $. All you need to implement is a list to determine if you are visiting and a list to record the order of visits. The former list prevents infinite loops and the latter list facilitates later implementations.
n, k = map(int,input().split())
a = list(map(int,input().split()))
s = [True] * n #List to determine if you are visiting
c = [1] #List that records the order of visits
now = 0 #Current location
while s[now]:
s[now] = False #Record the points you visited
now = a[now] - 1
c.append(now+1)
start_cycle = c.index(c[-1]) #Point to enter the loop
loop = c[start_cycle:-1] #Loop list
cycle = len(loop)
if k < start_cycle: #K unable to reach the loop
print(c[k])
else:
k -= start_cycle
k %= cycle
print(loop[k])
If I was calm, I was disappointed because I could solve it during the contest. see you.
Recommended Posts