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
import random
import sys

random.seed(231972473)

us = 0 if 'Algosia' in input() else 1
n, t = (int(x) for x in input().split(' '))
maxRounds = 0

for testcase in range(1, t+1):
    score = [0, 0]
    rounds = 0

    def send(x):
        global rounds
        assert 0 <= x <= 2
        print('PKN'[x])
        y = 'PKN'.index(input()[0])
        assert 0 <= y <= 2
        score[us] += ((x+1)%3 == y)
        score[1-us] += (x == (y+1)%3)
        rounds += 1
        return y

    bounds = [(1<<n)-1 for _ in range(2)]
    ourVal = int(input(), 2)
    trace = []

    def step(*prob):
        global ourVal
        rnd = [random.randrange(sum(x)) for x in prob]

        mod = sum(prob[us])
        rem = (ourVal + rnd[us]) % mod
        ourVal //= mod
        bounds[us] //= mod
        offset = 0
        for i, wnd in enumerate(prob[us]):
            if rem < wnd:
                msg = send(i)
                ourVal = ourVal*wnd + rem
                bounds[us] = bounds[us]*wnd + wnd - 1
                break
            rem -= wnd
            offset += wnd

        mod = sum(prob[1-us])
        offset = sum(prob[1-us][:msg]) - rnd[1-us]
        wnd = prob[1-us][msg]
        trace.append((offset, wnd, mod))
        bounds[1-us] = bounds[1-us] // mod * wnd + wnd - 1

    while max(bounds) > 0:
        S, C = 3, 1
        if score[0] < score[1]:
            if bounds[0] > bounds[1]:
                step([S, C, 0], [0, 1, 0])
            else:
                step([1, 0, 0], [C, S, 0])
        elif score[0] > score[1]:
            if bounds[0] > bounds[1]:
                step([C, S, 0], [1, 0, 0])
            else:
                step([0, 1, 0], [S, C, 0])
        else:
            step([1, 1, 1], [1, 1, 1])

    theirVal = 0
    for offset, wnd, mod in trace[::-1]:
        rem = (offset + theirVal % wnd + mod) % mod
        theirVal = (theirVal // wnd) * mod + rem

    print('! ' + format(theirVal, 'b').zfill(n) + '\n')
    if us == 0:
        print(f'({testcase}) rounds: {rounds}', file=sys.stderr)
    maxRounds = max(maxRounds, rounds)

if us == 0:
    print(f'max rounds: {maxRounds}', file=sys.stderr)