-
Notifications
You must be signed in to change notification settings - Fork 11
/
kattis_dragondropped.py
84 lines (66 loc) · 1.89 KB
/
kattis_dragondropped.py
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
''' Kattis - dragondropped
An interactive cycle finding problem. This is annoying because
1. its an interactive problem so its hard to debug
2. the constraints are kinda tight
The key observation is that in this case, we don't need to know mu. After doing the first phase of Floyd's cycle finding algorithm, we already
know how many steps it takes to get into the cycle to that position. From there, we just move around the cycle to determine lambda. Using the
information on how many steps left after getting into the position where the tortise and hare meet, we can get the number of steps to take to get
into the final position.
Time: O(mu + lambda*3 = mu + lambda)
Space: O(1)
'''
import sys
from sys import stdout
n = int(input())
tor_counter = 0
hare_counter = 0
def move_tor():
global tor_counter
tor_counter += 1
print("NEXT SPIKE")
stdout.flush()
okay, same_place = map(int, input().split())
if (tor_counter) == n:
print("ASK SPIKE")
stdout.flush()
sys.exit()
return okay, same_place
def move_hare():
global hare_counter
hare_counter+= 1
print("NEXT GABBY")
stdout.flush()
okay, same_place = map(int, input().split())
if (hare_counter) == n:
print("ASK GABBY")
stdout.flush()
sys.exit()
return okay, same_place
def reset_hare():
global hare_counter
hare_counter = 0
print("RETURN GABBY")
stdout.flush()
okay, same_place = map(int, input().split())
# Move both at once
x = 0
while (1):
move_tor()
move_hare()
okay, same_place = move_hare()
x += 1
if same_place == 1:
break # i = k * lambda
# Get lambda
l = 0
while (1):
okay, same_place = move_hare()
l += 1
if same_place == 1:
break
# Go to the end
num_steps = (n-x)%l
for i in range(num_steps):
move_hare()
print("ASK GABBY")
stdout.flush()