diff options
Diffstat (limited to '')
-rwxr-xr-x | inf/ioi/1/a.out | bin | 0 -> 17200 bytes | |||
-rw-r--r-- | inf/ioi/1/in.txt | 5 | ||||
-rw-r--r-- | inf/ioi/1/prog.c | 106 |
3 files changed, 111 insertions, 0 deletions
diff --git a/inf/ioi/1/a.out b/inf/ioi/1/a.out Binary files differnew file mode 100755 index 0000000..09601da --- /dev/null +++ b/inf/ioi/1/a.out 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; +} |