diff options
| -rw-r--r-- | šola/p2/dn/DN08a_63230317.c | 106 | ||||
| -rw-r--r-- | šola/p2/dn/DN08b_63230317.c | 114 |
2 files changed, 220 insertions, 0 deletions
diff --git a/šola/p2/dn/DN08a_63230317.c b/šola/p2/dn/DN08a_63230317.c new file mode 100644 index 0000000..860c422 --- /dev/null +++ b/šola/p2/dn/DN08a_63230317.c @@ -0,0 +1,106 @@ +#include <stdio.h> +#include <stdlib.h> +// #include <search.h> +#include <stdbool.h> +#include <assert.h> +#include <string.h> +void swap (int * seq, int i, int j, int r) { + while (r--) { + int bckp = seq[i+r]; + seq[i+r] = seq[j+r]; + seq[j+r] = bckp; + } +} +/* +#define N 10 +struct seq { + int elem[N]; + int count; +}; +int compar (const void * a, const void * b) { + for (int i = 0; i < N; i++) + if (((struct seq *) a)->elem[i] != ((struct seq *) b)->elem[i]) + return ((struct seq *) a)->elem[i] > ((struct seq *) b)->elem[i] ? 1 : -1; + return 0; +} +void insert (void ** root, struct seq * seq, int n, int r, int remain) { + for (int i = 0; i+2*r <= n; i++) + for (int j = i+r; j+i <= n; j++) { + struct seq * seq2 = calloc(1, sizeof *seq2); + memcpy(seq2, seq, sizeof *seq2); + swap(seq2->elem, i, j, r); + struct seq ** ret = tsearch(seq2, root, compar); + if (seq2 == *ret) { + free(seq2); + seq2 = *ret; + } + seq2->count++; + if (remain-1) + insert(root, seq, n, r, remain-1); + } +} +int count (void ** root, struct seq * seq, int n, int r, int remain) { + int število = 0; + for (int i = 0; i+2*r <= n; i++) + for (int j = i+r; j+i <= n; j++) { + swap(seq->elem, i, j, r); + struct seq ** ret = tfind(seq, root, compar); + if (ret) + število += (*ret)->count; + if (remain-1) + count(root, seq, n, r, remain-1); + swap(seq->elem, i, j, r); + } + return število; +} +int intcompar (const void * a, const void * b) { + if (*((int *)a) == *((int *)b)) + return 0; + return *((int *) a) < *((int *) b) ? -1 : 1; +} +*/ +bool sorted (int * seq, int n) { + bool up = true; + bool down = true; + while (--n) { + if (seq[n] < seq[n-1]) + up = false; + if (seq[n] > seq[n-1]) + down = false; + } + return up; +} +int count (int * seq, int n, int r, int remain) { + int število = 0; + for (int i = 0; i+2*r <= n; i++) + for (int j = i+r; j+r <= n; j++) { + swap(seq, i, j, r); + if (sorted(seq, n)) + število++; + if (remain-1) + število += count(seq, n, r, remain-1); + swap(seq, i, j, r); + } + return število; +} +int main (void) { + int n, k, r; + scanf("%d %d %d\n", &n, &k, &r); + /* struct seq seq; + memset(&seq, 0, sizeof seq); + for (int i = 0; i < n; i++) + scanf("%d", &seq.elem[i]); + void * root = NULL; + tsearch(&seq, &root, compar); + insert(&root, &seq, n, r, k/2); + qsort(seq.elem, n, sizeof seq.elem[0], intcompar); */ + /* int seqdebug[10] = {14, 12, 19, 16, 18, 11, 15, 10, 13, 17}; + swap(seqdebug, 0, 3, 3); + swap(seqdebug, 2, 5, 3); + swap(seqdebug, 0, 4, 3); + swap(seqdebug, 2, 7, 3); */ + int seq[n]; + for (int i = 0; i < n; i++) + scanf("%d", &seq[i]); + printf("%d\n", count(seq, n, r, k) + sorted(seq, n)); +} 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 |