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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <cstdio>
#include <cstring>
#include <cstdlib>

static char alfabet[] = "PKN";

static unsigned get3bits(const char *s)
{
	unsigned v = 0;
	for (unsigned i = 0; i < 3; i++)
		v = (v << 1) | (*s++ == '1');
	return v;
}

static void put3bits(char *p, unsigned v)
{
	for (unsigned i = 0; i < 3; i++, v <<= 1)
		*p++ = '0' + !!(v & 4);
}

static int delta(int wyslalem, int odebralem)
{
	int x = odebralem - wyslalem;
	switch (x) {
		case +2:
			x = -1;
			break;
		case -2:
			x = +1;
			break;
	}
	return x;
}

static unsigned n;

static void interakcja(void)
{
	static char moj[5005];
	fgets(moj, sizeof(moj), stdin);
	memset(moj + n, '0', sizeof(moj) - n);
	static char ich[5005];
	int przewaga = 0;	// moja przewaga
	unsigned moj_i = 0, ich_i = 0;
	int symbol = -1, odebrano = -1;
	while (ich_i < n) {
		int wyslij, odb;
		if (!przewaga) {
			if (symbol < 0) {
				unsigned v = get3bits(moj + moj_i);
				moj_i += 3;
				if (v == 7) {
					wyslij = symbol = 2;
				} else {
					div_t dm = div(v, 3);
					wyslij = dm.quot;
					symbol = dm.rem;
				}
			} else {
				wyslij = symbol;
				symbol = -1;
			}
		} else {
			wyslij = 1 - przewaga;
		}
		printf("%c\n", alfabet[wyslij]);
		char buf[5];
		fgets(buf, sizeof(buf), stdin);
		odb = strchr(alfabet, buf[0]) - alfabet;
		if (!przewaga) {
			if (odebrano < 0) {
				odebrano = odb;
			} else {
				unsigned v = odebrano * 3 + odb;
				if (v == 8)
					v--;
				put3bits(ich + ich_i, v);
				ich_i += 3;
				odebrano = -1;
			}
		}
		int d = delta(wyslij, odb);
		przewaga += d;
	}
	printf("! %.*s\n", n, ich);
}

int main(void)
{
	char buf[15];
	fgets(buf, sizeof(buf), stdin);
	unsigned t;
	scanf("%u%u\n", &n, &t);
	setlinebuf(stdout);
	for (unsigned i = 0; i < t; i++)
		interakcja();
	return 0;
}