#include #include #include #include /* 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); }