1 files changed, 106 insertions, 0 deletions

diff --git a/inf/ioi/1/prog.c b/inf/ioi/1/prog.c
new file mode 100644
index 0000000..219dd87
--- /dev/null
+++ b/inf/ioi/1/prog.c
@@ -0,0 +1,106 @@
+#include <stdio.h>
+#include <stdlib.h>
+/* testni program, da vidim, če razumem nalogo */
+struct voznik {
+	int t;
+	int v;
+};
+int najdi (int ** sp, int n, int * prijatelji, int * po, int prij) {
+	int s = 0;
+	/* preverimo, če smo našli */
+	for (int i = 0; i < prij; i++) {
+		if (po[i])
+			continue;
+		s++;
+		for (int j = 0; j < prij; j++) {
+			if (po[i])
+				continue;
+			if (i == j)
+				continue;
+			if (!sp[prijatelji[i]][prijatelji[j]] && !sp[prijatelji[j]][prijatelji[i]])
+				goto n;
+		}
+	}
+	return s;
+n:
+	s = -1;
+	for (int i = 0; i < prij; i++) {
+		if (po[i]) /* je bil odstranjen */
+			continue;
+		po[i]++;
+		int ns = najdi(sp, n, prijatelji, po, prij);
+		po[i]--;
+		if (ns > s)
+			s = ns;
+	}
+	return s;
+}
+int spop (int l, struct voznik * i, struct voznik * j) {
+	return (i->t < j->t && l/i->v+i->t > l/j->v+j->t);
+}
+int primerjaj_voznike (const void * a, const void * b) {
+	const struct voznik * c = (const struct voznik *) a;
+	const struct voznik * d = (const struct voznik *) b;
+	return c->t - d->t;
+}
+int main (int argc, char ** argv) {
+	int l, n, i, s, ** sp, * prijatelji, * po;
+	char * c, * buf;
+	struct voznik * vozniki;
+	buf = malloc(500);
+	fgets(buf, 500, stdin);
+	l = strtol(buf, &c, 10);
+	c++;
+	n = strtol(c, NULL, 10);
+	vozniki = calloc(n, sizeof(struct voznik));
+	sp = calloc(n, sizeof(int *));
+	prijatelji = calloc(n, sizeof(int));
+	po = calloc(n, sizeof(int));
+	for (int i = 0; i < n; i++)
+		sp[i] = calloc(n, sizeof(int)); /* alloc bi lahko zgolj (n-i)-1 ampak ok */
+	i = 0;	
+	while (i < n) {
+		fgets(buf, 500, stdin);
+		vozniki[i].t = strtol(buf, &c, 10);
+		c++;
+		vozniki[i++].v = strtol(c, NULL, 10);
+	}
+	qsort(vozniki, n, sizeof(struct voznik), primerjaj_voznike);
+	for (int i = 0; i < n-1; i++)
+		for (int j = i+1; j < n; j++)
+			if (spop(l, vozniki+i, vozniki+j) && !sp[i][j])
+				sp[i][j]++;
+	/* debug, tabelica */
+	for (int i = 0; i < n; i++) {
+		fprintf(stderr, "%d:", i);
+		for (int j = 0; j < n; j++)
+			fprintf(stderr, " %d", sp[i][j]);
+		fprintf(stderr, "\n");
+	}
+	s = 0;
+	/* sedaj gremo po voznikih in najdemo osebo z največ skupinskimi prijatelji */
+	for (int v = 0; v < n; v++) {
+		int sest = 0;
+		int prij = 1;
+		prijatelji[0] = v;
+		/* po vrstici */
+		for (int j = v+1; j < n; j++)
+			if (sp[v][j])
+				prijatelji[prij++] = j;
+		/* po stolpcu */
+		for (int i = 0; i < v; i++)
+			if (sp[i][v])
+				prijatelji[prij++] = i;
+		/* rekurzivno odstranjujemo prijatelje dokler ne najdemo najbolj optimalne skupine */
+		sest = najdi(sp, n, prijatelji, po, prij);
+		if (sest > s)
+			s = sest;
+	}
+	for (int i = 0; i < n; i++)
+		free(sp[i]);
+	free(buf);
+	free(vozniki);
+	free(sp);
+	fprintf(stdout, "%d\n", s);
+	return 0;
+}