From 8302da73a4ef0c3d0c44c689aba9161ae8eb8d17 Mon Sep 17 00:00:00 2001 From: sijanec Date: Mon, 4 Jan 2021 22:24:14 +0100 Subject: =?UTF-8?q?sloven=C5=A1=C4=8Dina=20in=20nekaj=20zajebancije=20z=20?= =?UTF-8?q?rtk=20laNSKO=20offline=20nalogo?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- inf/rtk/offline/.gitignore | 4 +++ inf/rtk/offline/Makefile | 23 ++++++++++++++ inf/rtk/offline/npk.c | 60 +++++++++++++++++++++++++++++++++++ inf/rtk/offline/offline.h | 8 +++++ inf/rtk/offline/origprog.c | 78 ++++++++++++++++++++++++++++++++++++++++++++++ inf/rtk/offline/razdeli.c | 65 ++++++++++++++++++++++++++++++++++++++ inf/rtk/offline/resi.c | 67 +++++++++++++++++++++++++++++++++++++++ inf/rtk/offline/test.txt | 2 ++ 8 files changed, 307 insertions(+) create mode 100644 inf/rtk/offline/.gitignore create mode 100644 inf/rtk/offline/Makefile create mode 100644 inf/rtk/offline/npk.c create mode 100644 inf/rtk/offline/offline.h create mode 100644 inf/rtk/offline/origprog.c create mode 100644 inf/rtk/offline/razdeli.c create mode 100644 inf/rtk/offline/resi.c create mode 100644 inf/rtk/offline/test.txt (limited to 'inf') diff --git a/inf/rtk/offline/.gitignore b/inf/rtk/offline/.gitignore new file mode 100644 index 0000000..ffeb5c9 --- /dev/null +++ b/inf/rtk/offline/.gitignore @@ -0,0 +1,4 @@ +stiskanje-unix.in +stiskanje.in +naloge/ +*.out diff --git a/inf/rtk/offline/Makefile b/inf/rtk/offline/Makefile new file mode 100644 index 0000000..dde543e --- /dev/null +++ b/inf/rtk/offline/Makefile @@ -0,0 +1,23 @@ +default: + @echo "offline naloga in rešitev za ijs.rtk. recepti:" + @echo "- make prepare: prenese datoteke, potrebne za nalogo" + @echo "- make razdeli: razdeli naloge v posamezne datoteke" + @echo "- make npk: naredi program za najdaljši ponavljajoči kos" + @echo "- make resi: naredi program za reševanje" + +prepare: + wget http://rtk.ijs.si/2020/stiskanje/stiskanje-unix.in -c + wget http://rtk.ijs.si/2020/stiskanje/stiskanje.in -c + +resi: + gcc -Wall -pedantic -I. -g -oresi.out resi.c + +npk: + gcc -Wall -pedantic -I. -g -onpk.out npk.c + +razdeli: + gcc -Wall -pedantic -I. -g -orazdeli.out razdeli.c + ./razdeli.out < stiskanje-unix.in + rm -rf naloge + mkdir -p naloge + mv naloga*.txt naloge/ diff --git a/inf/rtk/offline/npk.c b/inf/rtk/offline/npk.c new file mode 100644 index 0000000..a18b38a --- /dev/null +++ b/inf/rtk/offline/npk.c @@ -0,0 +1,60 @@ +#if __INCLUDE_LEVEL__ != 0 +#pragma once +#endif +/* najdaljši ponavljajoči kos niza */ +#include +#include +#include +#include +/* lahko bi šli čez niz znakov for(strlen)for(strlen)for(strlen), ampak to + * bi trajalo zelo dolgo, čas*1000000^3 in bi imelo O(n^3) kompleksnost. + * ta implementacija najde najdaljši string in ima kompleksnost + * PRIBLIŽNO OKOLI O(n^2), kar je bistveno hitreje, PRIBLIŽNO čas*1000000^2. */ +struct rtk_kos npk (char * s) { + struct rtk_kos k; + k.l = 0; k.o = 0; + const size_t l = strlen(s); + unsigned char ** z = calloc(l+1, sizeof(unsigned char *)); + size_t i = 0; + size_t j = 0; + for (i = 0; i < l+1; i++) + z[i] = calloc(l+1, sizeof(unsigned char)); + for (i = 1; i <= l; i++) + for (j = i+1; j <= l; j++) + if (s[i-1] == s[j-1] && z[i-1][j-1] < (j-1)) { + z[i][j] = z[i-1][j-1] + 1; + if (z[i][j] > k.l) { + k.l = z[i][j]; + k.o = k.o > i ? k.o : i; + } + } else + z[i-1][j-1] = 0; + k.o = k.o-k.l; + for (i = 0; i < l+1; i++) { + free(z[i]); z[i] = NULL; + } + free(z); + z = NULL; + return k; +} +#if __INCLUDE_LEVEL__ == 0 +int main (int argc, char ** argv) { + char c = getchar(); + size_t v = 0; + char * s = malloc(sizeof(char)*1); + struct rtk_kos k; + while (!feof(stdin)) { + s = realloc(s, sizeof(char)*v+2); + s[v++] = c; + s[v] = '\0'; + c = getchar(); + } + k = npk(s); + for (v = 0; v < k.l; v++) + putchar(s[v+k.o]); + putchar('\n'); /* za dobro mero */ + free(s); + s = NULL; + return 0; +} +#endif diff --git a/inf/rtk/offline/offline.h b/inf/rtk/offline/offline.h new file mode 100644 index 0000000..9724846 --- /dev/null +++ b/inf/rtk/offline/offline.h @@ -0,0 +1,8 @@ +#define RTK_EOL '\r' +#define RTK_IDC(x,y) (x/y + (x % y != 0)) /* int devide ceil */ +#define RTK_RAM_KOS 128 +struct rtk_kos { + size_t o; /* ffset */ + size_t l; /* ength */ + size_t p; /* ojavi */ +}; diff --git a/inf/rtk/offline/origprog.c b/inf/rtk/offline/origprog.c new file mode 100644 index 0000000..631d61d --- /dev/null +++ b/inf/rtk/offline/origprog.c @@ -0,0 +1,78 @@ +#include +#include +#include +#include +size_t rtk_resi (/* const */ char * s, struct rtk_kos * p) { + size_t i = 0; + size_t j = 0; + size_t k = 0; + size_t l = strlen(s); + size_t p_sizeof = RTK_RAM_KOS; size_t pzi = 0; /* pieces za izdelavo */ + size_t pjev = 0; size_t psd = 0; /* pieces sigma dolžin */; + /* struct rtk_kos * */ p = malloc(sizeof(struct rtk_kos)*p_sizeof); + /* začnemo s preprosto rešitvijo: en kos, celoten niz */ + p[0].o = 0; p[0].l = l; p[0].p = 1; pjev++; psd = l; pzi = 1; + /* iščemo ponovitve za izboljšavo, začnemo z dolžino 2 */ + /* kosov, velikih 1, še ne potrebujemo */ + /* POMNI: izračun točk: psd+pzi */ + for (i = 2; i < l; i++) { /* za vsako možno dolžino kosa */ + for (j = 0; j < l-i; j++) { /* za vsako lokacijo, kjer bi se začel kos */ + // fprintf(stderr, "%.*s\n", i, s+j); + } + } + return pjev; +} +int main (int argc, char ** argv) { + char ** n = malloc(sizeof(char *) * 1); + size_t * v = malloc(sizeof(size_t) * 1); + size_t nalog = 0; + int returnstatus = 0; + char c = getchar(); + int vrs = 0; + size_t pjev; + char fn[69]; + FILE * fd; + struct rtk_kos * p; + n[0] = NULL; + v[0] = 0; + while (!feof(stdin)) { + n[nalog] = realloc(n[nalog], sizeof(char)*v[nalog]+2); + n[nalog][v[nalog]++] = c; + n[nalog][v[nalog]] = '\0'; + if (c == RTK_EOL) { + if (vrs == 0 && strncmp("Stiskanje", n[0], strlen("Stiskanje") != 0)) { + fprintf(stderr, "vhodna datoteka se ne začne s \"Stiskanje\"\n"); + returnstatus = 1; + goto returncleanly; + } + if ((vrs - 2) % 3 == 2) { /* če je bila to naloga */ + fprintf(stderr, "prepisal nalogo %lu\r", nalog); + nalog++; + n = realloc(n, sizeof(char*)*(nalog+1)); + n[nalog] = NULL; + v = realloc(v, sizeof(size_t)*(nalog+1)); + } + v[nalog] = 0; /* gremo na začetek prostora za nalogo */ + vrs++; + } + c = getchar(); + } + fprintf(stderr, "zapisal naloge v spomin. \n"); + for (vrs = 0; vrs < nalog; vrs++) { + fprintf(stderr, "rešujem nalogo %d\n", vrs); + pjev = rtk_resi(n[vrs], p); + free(p); + p = NULL; + } + returncleanly: + while (nalog > 0) { + nalog--; + free(n[nalog]); + n[nalog] = NULL; + } + free(n); + n = NULL; + free(v); + v = NULL; + return returnstatus; +} diff --git a/inf/rtk/offline/razdeli.c b/inf/rtk/offline/razdeli.c new file mode 100644 index 0000000..24c36c1 --- /dev/null +++ b/inf/rtk/offline/razdeli.c @@ -0,0 +1,65 @@ +#include +#include +#include +#include +int main (int argc, char ** argv) { + char ** n = malloc(sizeof(char *) * 1); + size_t * v = malloc(sizeof(size_t) * 1); + size_t nalog = 0; + int returnstatus = 0; + char c = getchar(); + int vrs = 0; + size_t pjev; + char fn[69]; + FILE * fd; + /* struct rtk_kos * p; */ + n[0] = NULL; + v[0] = 0; + while (!feof(stdin)) { + n[nalog] = realloc(n[nalog], sizeof(char)*v[nalog]+2); + n[nalog][v[nalog]++] = c; + n[nalog][v[nalog]] = '\0'; + if (c == RTK_EOL) { + if (vrs == 0 && strncmp("Stiskanje", n[0], strlen("Stiskanje") != 0)) { + fprintf(stderr, "vhodna datoteka se ne začne s \"Stiskanje\"\n"); + returnstatus = 1; + goto returncleanly; + } + if ((vrs - 2) % 3 == 2) { /* če je bila to naloga */ + n[nalog][--v[nalog]] = '\0'; + fprintf(stderr, "prepisal nalogo %lu\r", nalog); + nalog++; + n = realloc(n, sizeof(char*)*(nalog+1)); + n[nalog] = NULL; + v = realloc(v, sizeof(size_t)*(nalog+1)); + } + v[nalog] = 0; /* gremo na začetek prostora za nalogo */ + vrs++; + } + c = getchar(); + } + fprintf(stderr, "zapisal naloge v spomin. \n"); + for (vrs = 0; vrs < nalog; vrs++) { + fprintf(stderr, "shranjujem nalogo %d\n", vrs); + snprintf(fn, 69, "naloga%d.txt", vrs+1); + fd = fopen(fn, "w"); + pjev = 0; + while (n[vrs][pjev] != '\0') + putc(n[vrs][pjev++], fd); + fprintf(stderr, "zadnji znak je %02x\n", n[vrs][--pjev]); + fclose(fd); + /* pjev = rtk_resi(n[vrs], p); + free(p); */ + } + returncleanly: + while (nalog > 0) { + nalog--; + free(n[nalog]); + n[nalog] = NULL; + } + free(n); + n = NULL; + free(v); + v = NULL; + return returnstatus; +} diff --git a/inf/rtk/offline/resi.c b/inf/rtk/offline/resi.c new file mode 100644 index 0000000..43f97cc --- /dev/null +++ b/inf/rtk/offline/resi.c @@ -0,0 +1,67 @@ +#if __INCLUDE_LEVEL__ != 0 +#pragma once +#endif +/* najdaljši ponavljajoči kos niza */ +#include +#include +#include +#include +#define RTK_NAENKRAT 60000 +/* lahko bi šli čez niz znakov for(strlen)for(strlen)for(strlen), ampak to + * bi trajalo zelo dolgo, čas*1000000^3 in bi imelo O(n^3) kompleksnost. + * ta implementacija najde najdaljši string in ima kompleksnost + * PRIBLIŽNO OKOLI O(n^2), kar je bistveno hitreje, PRIBLIŽNO čas*1000000^2. */ +struct rtk_kos npk (const char * s, const size_t l) { + struct rtk_kos k; + k.l = 0; k.o = 0; + unsigned char ** z = calloc(l+1, sizeof(unsigned char *)); + size_t i = 0; + size_t j = 0; + for (i = 0; i < l+1; i++) + z[i] = calloc(l+1, sizeof(unsigned char)); + for (i = 1; i <= l; i++) + for (j = i+1; j <= l; j++) + if (s[i-1] == s[j-1] && z[i-1][j-1] < (j-1)) { + z[i][j] = z[i-1][j-1] + 1; + if (z[i][j] > k.l) { + k.l = z[i][j]; + k.o = k.o > i ? k.o : i; + } + } else + z[i-1][j-1] = 0; + k.o = k.o-k.l; + for (i = 0; i < l+1; i++) { + free(z[i]); z[i] = NULL; + } + free(z); + z = NULL; + return k; +} +#if __INCLUDE_LEVEL__ == 0 +int main (int argc, char ** argv) { + char c = getchar(); + size_t v = 0; + char * s = malloc(sizeof(char)*1); + struct rtk_kos k1; + struct rtk_kos k2; + size_t l = 0; + while (!feof(stdin)) { + s = realloc(s, sizeof(char)*v+2); + s[v++] = c; + s[v] = '\0'; + c = getchar(); + } + l = v; + for (v = 0; v*RTK_NAENKRAT <= l;) { + k1 = npk(s+(v*(RTK_NAENKRAT/2)), RTK_NAENKRAT); + k2 = npk(s+(++v*(RTK_NAENKRAT/2)), RTK_NAENKRAT); + } + + for (v = 0; v < k.l; v++) + putchar(s[v+k.o]); + putchar('\n'); /* za dobro mero */ + free(s); + s = NULL; + return 0; +} +#endif diff --git a/inf/rtk/offline/test.txt b/inf/rtk/offline/test.txt new file mode 100644 index 0000000..139597f --- /dev/null +++ b/inf/rtk/offline/test.txt @@ -0,0 +1,2 @@ + + -- cgit v1.2.3