diff options
author | Anton Luka Šijanec <anton@sijanec.eu> | 2024-05-14 22:19:27 +0200 |
---|---|---|
committer | Anton Luka Šijanec <anton@sijanec.eu> | 2024-05-14 22:19:27 +0200 |
commit | f65e7733a59efe8bfd8cfe33e699c1e750deb274 (patch) | |
tree | ae8918ee0766f26f3c74b1d97a5edbbb550d5646 /šola/p2/dn/DN09a_63230317.c | |
parent | dn08 (diff) | |
download | r-f65e7733a59efe8bfd8cfe33e699c1e750deb274.tar r-f65e7733a59efe8bfd8cfe33e699c1e750deb274.tar.gz r-f65e7733a59efe8bfd8cfe33e699c1e750deb274.tar.bz2 r-f65e7733a59efe8bfd8cfe33e699c1e750deb274.tar.lz r-f65e7733a59efe8bfd8cfe33e699c1e750deb274.tar.xz r-f65e7733a59efe8bfd8cfe33e699c1e750deb274.tar.zst r-f65e7733a59efe8bfd8cfe33e699c1e750deb274.zip |
Diffstat (limited to '')
-rw-r--r-- | šola/p2/dn/DN09a_63230317.c | 106 |
1 files changed, 106 insertions, 0 deletions
diff --git a/šola/p2/dn/DN09a_63230317.c b/šola/p2/dn/DN09a_63230317.c new file mode 100644 index 0000000..64c5e2b --- /dev/null +++ b/šola/p2/dn/DN09a_63230317.c @@ -0,0 +1,106 @@ +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <stdbool.h> +#include <limits.h> +#define ARRSIZ 32 +// komentar 2024-05-13: testi iz ucilnica2223 passajo, toda sem prepozen za oddajo +struct množica { + int n; + int arr[ARRSIZ]; +}; +void najdi_targete (struct množica ** shramba, int * shramba_len, int * shramba_sizeof, int n, int * t, int * stack, int globina, int target) { + if (target < 0) + return; + if (!target) { + if (*shramba_len >= *shramba_sizeof) + *shramba = realloc(*shramba, (*shramba_sizeof *= 2)*sizeof(struct množica)); + memcpy((*shramba)[*shramba_len].arr, stack, sizeof(int)*globina); + (*shramba)[(*shramba_len)++].n = globina; + return; + } + for (int i = globina == 0 ? 0 : stack[globina-1]+1; i < n; i++) { + stack[globina] = i; + najdi_targete(shramba, shramba_len, shramba_sizeof, n, t, stack, globina+1, target-t[i]); + } +} +void najdi_množice (struct množica * shramba, int shramba_len, int * stack, int * t, bool * used, int n, int globina, int k) { + if (globina == k) { + for (int i = 0; i < n; i++) + if (!used[i]) + return; + printf("{"); + for (int i = 0; i < k; i++) { + printf("{"); + int donefirst = false; + for (int j = 0; j < shramba[stack[i]].n; j++) { + printf("%s%d", donefirst ? ", " : "", t[shramba[stack[i]].arr[j]]); + donefirst = true; + } + printf("}"); + if (i != k-1) + printf(", "); + } + printf("}\n"); + return; + } + for (int i = globina == 0 ? 0 : stack[globina-1]+1; i < shramba_len; i++) { + bool contpls = false; + for (int j = 0; j < shramba[i].n; j++) + if (used[shramba[i].arr[j]]) { + contpls = true; + break; + } + if (contpls) + continue; + for (int j = 0; j < shramba[i].n; j++) + used[shramba[i].arr[j]] = true; + stack[globina] = i; + najdi_množice(shramba, shramba_len, stack, t, used, n, globina+1, k); + for (int j = 0; j < shramba[i].n; j++) + used[shramba[i].arr[j]] = false; + } +} +int compar (const void * a, const void * b) { + struct množica * c = ((struct množica *) a); + struct množica * d = ((struct množica *) b); + int e = INT_MAX; + int f = INT_MAX; + for (int i = 0; i < c->n; i++) { + if (c->arr[i] < e) + e = c->arr[i]; + } + for (int i = 0; i < d->n; i++) { + if (d->arr[i] < f) + f = d->arr[i]; + } + if (e == f) + return 0; + return e > f ? 1 : -1; +} +int main (void) { + int n, k, sum = 0; + scanf("%d %d\n", &n, &k); + int t[n]; + for (int i = 0; i < n; i++) { + scanf("%d", &t[i]); + sum += t[i]; + } + if (sum % k) + return 0; + int shramba_sizeof = 2; + int shramba_len = 0; + struct množica * shramba = malloc(sizeof (struct množica) * shramba_sizeof); + int stack[ARRSIZ]; + najdi_targete(&shramba, &shramba_len, &shramba_sizeof, n, t, stack, 0, sum/k); + qsort(shramba, shramba_len, sizeof (struct množica), compar); + for (int i = 0; i < shramba_len; i++) { + for (int j = 0; j < shramba[i].n; j++) { + fprintf(stderr, "%d, ", t[shramba[i].arr[j]]); + } + fprintf(stderr, "\n"); + } + bool used[n]; + memset(used, 0, sizeof used); + najdi_množice(shramba, shramba_len, stack, t, used, n, 0, k); +} |