summaryrefslogtreecommitdiffstats
path: root/inf/ioi/1
diff options
context:
space:
mode:
Diffstat (limited to 'inf/ioi/1')
-rwxr-xr-xinf/ioi/1/a.outbin0 -> 17200 bytes
-rw-r--r--inf/ioi/1/in.txt5
-rw-r--r--inf/ioi/1/prog.c106
3 files changed, 111 insertions, 0 deletions
diff --git a/inf/ioi/1/a.out b/inf/ioi/1/a.out
new file mode 100755
index 0000000..09601da
--- /dev/null
+++ b/inf/ioi/1/a.out
Binary files differ
diff --git a/inf/ioi/1/in.txt b/inf/ioi/1/in.txt
new file mode 100644
index 0000000..98a8264
--- /dev/null
+++ b/inf/ioi/1/in.txt
@@ -0,0 +1,5 @@
+1000 4
+1 3
+2 1
+0 2
+3 4
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;
+}