summaryrefslogtreecommitdiffstats
path: root/šola/p2/dn/DN08b_63230317.c
diff options
context:
space:
mode:
Diffstat (limited to 'šola/p2/dn/DN08b_63230317.c')
-rw-r--r--šola/p2/dn/DN08b_63230317.c114
1 files changed, 114 insertions, 0 deletions
diff --git a/šola/p2/dn/DN08b_63230317.c b/šola/p2/dn/DN08b_63230317.c
new file mode 100644
index 0000000..e481d7c
--- /dev/null
+++ b/šola/p2/dn/DN08b_63230317.c
@@ -0,0 +1,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);
+} \ No newline at end of file