From 9e3cdb5da0b4fc1ff3b0fca15b4118785aebe026 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Anton=20Luka=20=C5=A0ijanec?= <anton@sijanec.eu>
Date: Fri, 13 Jan 2023 17:25:46 +0100
Subject: =?UTF-8?q?=C5=A1olsko=20ra=C4=8Dunalni=C5=A1ko=20tekmovanje=20zot?=
 =?UTF-8?q?ks?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 inf/zotks/3.c | 98 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 98 insertions(+)
 create mode 100644 inf/zotks/3.c

(limited to 'inf/zotks/3.c')

diff --git a/inf/zotks/3.c b/inf/zotks/3.c
new file mode 100644
index 0000000..1d4208c
--- /dev/null
+++ b/inf/zotks/3.c
@@ -0,0 +1,98 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+#include <signal.h>
+#include <string.h>
+/* int ob (unsigned long long char * matrika, unsigned long long * obiskan, unsigned long long besed, unsigned long long ttl) {
+	for (int i = 0; i < besed; i++) {
+		for (int j = 0; j < besed; j++) {
+			if (matrika[i*d+j] && obiskan[j]) {
+				if (obiskan[i] == 0) {
+					obiskan[i] = obiskan[j]+1;
+					continue;
+				}
+				if (obiskan[j]+1 < obiskan[i])
+					obiskan[i] = obiskan[j]+1; // če obstaja krajša pot
+			}
+		}
+	}
+} */
+unsigned long long naivno (unsigned char * matrika, unsigned long long * obiskan, unsigned long long besed, unsigned long long ttl, unsigned long long d, unsigned long long lok) {
+#ifndef EVAL
+	fprintf(stderr, "ttl je %llu\n", ttl);
+#endif
+	if (!ttl)
+		return 0;
+	// if (obiskan[lok]) // nič več, smo že
+	//	return 0;
+	obiskan[lok]++;
+	unsigned long long povezav = 1;
+	for (unsigned long long i = 0; i < besed; i++) {
+		if (matrika[besed*i+lok])
+			povezav += naivno(matrika, obiskan, besed, ttl-1, d, i);
+	}
+	return povezav;
+}
+int main (void) {
+	char buf[256];
+	fgets(buf, 256, stdin);
+	char * c;
+	unsigned long long s = strtoul(buf, &c, 10);
+	unsigned long long d = strtoul(++c, &c, 10);
+	unsigned long long n = strtoul(++c, &c, 10); // število otrok
+	unsigned long long z = strtoul(++c, &c, 10); // ??? . edit kasneje: aja, razumem, prva izrečena beseda
+	char ** w = malloc(sizeof(char *)*s);
+	unsigned long long i = 0;
+	while (i++ <= s) {
+		fgets(buf, 256 /* še newline in NULL */, stdin);
+		w[i-1] = strdup(buf);
+#ifndef EVAL
+		fprintf(stderr, "w[%llu]: %s\n", i-1, w[i-1]);
+#endif
+		if (ferror(stdin) || feof(stdin))
+			break;
+	}
+	unsigned char matrika[s*s]; // en megabajt največ, gucci
+	memset(matrika, '\0', s*s);
+	for (unsigned long long i = 0; i < s; i++) {
+#ifndef EVAL
+		fprintf(stderr, "%llu\n", i);
+#endif
+		for (unsigned long long j = 0; j < s; j++) {
+			int ne = 0;
+			for (unsigned long long k = 0; k < d; k++)
+				if (w[i][k] != w[j][k]) 
+					ne++;
+			if (ne <= 1)
+				matrika[s*i+j] = 1;
+		}
+	}
+#ifndef EVAL
+	for (unsigned long long i = 0; i < s; i++) {
+		for (unsigned long long j = 0; j < s; j++) {
+			fprintf(stderr, "%u ", matrika[s*i+j]);
+		}
+		fprintf(stderr, "\n");
+	}
+#endif
+	unsigned long long obiskan[s]; // da vpisujemo TTLje
+	memset(obiskan, '\0', s*sizeof(unsigned long long));
+	fprintf(stderr, "%llu\n", naivno(matrika, obiskan, s, n+1, d, z));
+	unsigned cx = 0;
+	for (int i = 0; i < s; i++) {
+		if (obiskan[i])
+			cx++;
+	}
+	fprintf(stdout, "%u\n", cx);
+	/* 
+	int ret = ob(matrika, obiskan, d, n);
+	if (ret == -1) { // nihče ni bil dodatno obiskan
+		unsigned long long obiskanih = 0;
+		for (int i = 0; i < d; i++)
+			if (obiskan[d])
+				obiskanih++;
+		fprintf(stdout, "%u\n", obiskanih);
+		return 0;
+	}*/
+	return 0;
+}
-- 
cgit v1.2.3