summaryrefslogtreecommitdiffstats
path: root/šola/p2/dn
diff options
context:
space:
mode:
authorAnton Luka Šijanec <anton@sijanec.eu>2024-05-14 22:19:27 +0200
committerAnton Luka Šijanec <anton@sijanec.eu>2024-05-14 22:19:27 +0200
commitf65e7733a59efe8bfd8cfe33e699c1e750deb274 (patch)
treeae8918ee0766f26f3c74b1d97a5edbbb550d5646 /šola/p2/dn
parentdn08 (diff)
downloadr-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 'šola/p2/dn')
-rw-r--r--šola/p2/dn/23kol1a.c18
-rw-r--r--šola/p2/dn/DN09a_1.txt2
-rw-r--r--šola/p2/dn/DN09a_63230317.c106
3 files changed, 126 insertions, 0 deletions
diff --git a/šola/p2/dn/23kol1a.c b/šola/p2/dn/23kol1a.c
new file mode 100644
index 0000000..bafd30e
--- /dev/null
+++ b/šola/p2/dn/23kol1a.c
@@ -0,0 +1,18 @@
+#include <stdio.h>
+#include <stdlib.h>
+#define MAX(x,y) ((x)>(y)?(x):(y))
+int vsote (int n, int m) {
+ int r = 0;
+ if (!n)
+ return 1;
+ for (int a = 1; a <= n; a++)
+ for (int b = MAX(m, a); a*b <= n; b++)
+ if (n-a*b >= 0)
+ r += vsote(n-a*b, m);
+ return r;
+}
+int main (void) {
+ int n, m;
+ scanf("%d %d\n", &n, &m);
+ printf("%d\n", vsote(n, m));
+}
diff --git a/šola/p2/dn/DN09a_1.txt b/šola/p2/dn/DN09a_1.txt
new file mode 100644
index 0000000..788f7a3
--- /dev/null
+++ b/šola/p2/dn/DN09a_1.txt
@@ -0,0 +1,2 @@
+10 4
+1 2 3 4 5 6 8 9 10 16
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);
+}