blob: a4c1727ac60079c0da39d79a709165e1896edcdc (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
import fileinput
import re
import sys
# start = '389125467'
start = "496138527"
def solve(is_p2):
n = len(start) if (not is_p2) else int(1e6)
N = [None for i in range(n + 1)]
X = [int(x) for x in start]
for i in range(len(X)):
N[X[i]] = X[(i + 1) % len(X)]
if is_p2:
N[X[-1]] = len(X) + 1
for i in range(len(X) + 1, n + 1):
N[i] = i + 1
N[-1] = X[0]
t = 0
current = X[0]
nmoves = int(1e7) if is_p2 else 100
for _ in range(nmoves):
t += 1
pickup = N[current]
N[current] = N[N[N[pickup]]]
dest = n if current == 1 else current - 1
while dest in [pickup, N[pickup], N[N[pickup]]]:
dest = n if dest == 1 else dest - 1
N[N[N[pickup]]] = N[dest]
N[dest] = pickup
current = N[current]
if is_p2:
return N[1] * N[N[1]]
else:
ans = []
x = N[1]
while x != 1:
ans.append(x)
x = N[x]
return "".join([str(x) for x in ans])
print(solve(False))
print(solve(True))
|