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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
/*
bool kva (bool * črni, int n, int k, int * sklad, int globina) { // stara neuporabljena funkcija ... preskoči to
if (črni[n-1]) // memo recall
return true;
if (n <= k) {
for (int i = 0; i < globina; i++)
printf("%d -> [%d] -> ", sklad[2*i], sklad[2*i+1]);
printf("%d\n", n);
return false;
}
bool črni_zmaga = true; // začnimo s tako predpostavko in jo ovržimo, čim najdemo kandidata za zmago belega
for (int i = 1; i < n && i <= k; i++) { // pobiranje belega
if (n-i <= k) // črni izprazni kup
break; // s takim ali večjim pobiranjem ne najdemo za belega ugodne rešitve
sklad[globina*2] = i;
bool beli_zmaga = true; // beli mora zmagati za vse možne odgovore črnega, da ...
for (int j = 1; j < n-i && j <= k; j++) { // možni odgovori črnega
sklad[globina*2+1] = j;
beli_zmaga &= !kva(črni, n-i-j, k, sklad, globina+1);
}
črni_zmaga &= !beli_zmaga; // ... lahko nastavimo črni_zmaga na false
sklad[globina] = i;
}
if (črni_zmaga) {
črni[n-1] = true; // memo sto
return true;
}
return false;
}
*/
void zmage (int n, int k, bool dp[n+1], bool bele_poteze[n+1][k+1], int sklad[2*n], int globina) {
if (n <= k) {
for (int i = 0; i < globina; i++)
printf("%d -> [%d] -> ", sklad[2*i], sklad[2*i+1]);
printf("%d\n", n);
return;
}
/* if (!dp[n])
return; */
for (int i = 1; i <= k && i <= n; i++) { // iščemo zmagovito belo potezo
if (bele_poteze[n][i]) { // i je zmagovita bela poteza ob številu preostalih žetonov n
sklad[2*globina] = i;
for (int j = 1; j <= k && j <= n-i; j++) { // vsi črni odgovori vodijo v zmagovito belo stanje žetonov
sklad[2*globina+1] = j;
zmage(n-i-j, k, dp, bele_poteze, sklad, globina+1);
}
}
}
/* for (int i = 1; i <= k && i <= n; i++) { // bela poteza
if (dp[n-i]) { // je zmagovita
sklad[2*globina] = i;
for (int j = 1; j <= k && j <= n-i; j++) { // črni odgovor
sklad[2*globina+1] = j;
zmage(n-i-j, k, dp, bele_poteze, sklad, globina+1);
}
}
} */
}
int main (void) {
int n, k;
scanf("%d %d\n", &n, &k);
bool dp[n+1]; // true je beli, false je črni, beli je na potezi, indeks je preostalih žetonov, vrednost je zmagovalec
bool bele_poteze[n+1][k+1]; // prevelika 2d tabela za bele odgovore ob danem preostalem številu žetonov. druga dimenzija je bitfield. true, če beli zmaga, false, če črni, za dano potezo belega.
for (int i = 1; i <= n; i++) {
dp[i] = false;
for (int j = 1; j <= k && j <= i; j++) { // bela poteza
bool beli_zmaga = true;
if (i-j == 0)
beli_zmaga = true;
else
for (int l = 1; l <= k && l <= i-j; l++) // iščemo en črni odgovor
if (!dp[i-j-l]) { // a črni s tem odgovorom zmaga
beli_zmaga = false;
break;
}
if (beli_zmaga) {
dp[i] = true;
bele_poteze[i][j] = true;
} else
bele_poteze[i][j] = false;
}
}
fprintf(stderr, " ");
for (int i = 0; i <= n; i++)
if (!(i % 10))
fprintf(stderr, "%d ", i/10);
fprintf(stderr, "\n ");
for (int i = 0; i <= n; i++)
fprintf(stderr, "%d", i%10);
fprintf(stderr, "\ndp: ");
for (int i = 1; i <= n; i++)
fprintf(stderr, "%s", dp[i] ? "@" : "_");
fprintf(stderr, "\t(@ je zmaga belega, _ je zmaga črnega)\n");
for (int i = 1; i <= n; i++) {
fprintf(stderr, "preostalo žetonov %d. poteze belega: ", i);
for (int j = 1; j <= k; j++) {
if (bele_poteze[i][j]) {
fprintf(stderr, "%d, ", j);
}
}
fprintf(stderr, "\n");
}
if (!dp[n]) {
printf("CRNI\n");
return 0;
}
int sklad[2*n];
memset(sklad, 0, sizeof sklad);
zmage(n, k, dp, bele_poteze, sklad, 0);
}
|
