From 1b055c87170fad129990d04ecbc3cb08b4f7017e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Anton=20Luka=20=C5=A0ijanec?= Date: Fri, 31 Mar 2023 12:23:05 +0200 Subject: z: zotksd, fizvaje10, infsemin --- inf/rn/dok/lyx/Summary.lyx | 28 ++++++++-- inf/rn/dok/lyx/eksperimentalni.lyx | 24 ++++++++- inf/rn/dok/lyx/thesis.lyx | 78 +++++++++++++++++++++++++-- inf/rn/dok/lyx/uvod.lyx | 26 ++++++++- "inf/rn/dok/lyx/zaklju\304\215ek.lyx" | 25 ++++++++- inf/zotksd/1 | Bin 0 -> 282656 bytes inf/zotksd/1.c | 57 ++++++++++++++++++++ inf/zotksd/1.txt | 8 +++ inf/zotksd/1.txt2 | 8 +++ inf/zotksd/2 | Bin 0 -> 284000 bytes inf/zotksd/2.c | 88 +++++++++++++++++++++++++++++++ inf/zotksd/2.txt | 3 ++ inf/zotksd/2.txt2 | 4 ++ inf/zotksd/3 | Bin 0 -> 282408 bytes inf/zotksd/3.c | 22 ++++++++ inf/zotksd/4 | Bin 0 -> 283072 bytes inf/zotksd/4.c | 96 ++++++++++++++++++++++++++++++++++ inf/zotksd/4.txt | 2 + inf/zotksd/4.txt2 | 2 + 19 files changed, 460 insertions(+), 11 deletions(-) create mode 100755 inf/zotksd/1 create mode 100644 inf/zotksd/1.c create mode 100644 inf/zotksd/1.txt create mode 100644 inf/zotksd/1.txt2 create mode 100755 inf/zotksd/2 create mode 100644 inf/zotksd/2.c create mode 100644 inf/zotksd/2.txt create mode 100644 inf/zotksd/2.txt2 create mode 100755 inf/zotksd/3 create mode 100644 inf/zotksd/3.c create mode 100755 inf/zotksd/4 create mode 100644 inf/zotksd/4.c create mode 100644 inf/zotksd/4.txt create mode 100644 inf/zotksd/4.txt2 (limited to 'inf') diff --git a/inf/rn/dok/lyx/Summary.lyx b/inf/rn/dok/lyx/Summary.lyx index 963d4f6..c4bb94a 100644 --- a/inf/rn/dok/lyx/Summary.lyx +++ b/inf/rn/dok/lyx/Summary.lyx @@ -145,9 +145,31 @@ Porazdeljene razpršilne tabele (angl. \end_layout \begin_layout Standard -V raziskovalni nalogi je preverjena praktična zmožnost pridobivanja velike - količine podatkov v omrežju BitTorrent za P2P izmenjavo datotek, pridobljeni - podatki pa so analizirani. +V +\begin_inset Branch seminarska +inverted 1 +status open + +\begin_layout Standard +raziskovalni +\end_layout + +\end_inset + + +\begin_inset Branch seminarska +inverted 0 +status open + +\begin_layout Standard +seminarski +\end_layout + +\end_inset + + nalogi je preverjena praktična zmožnost pridobivanja velike količine podatkov + v omrežju BitTorrent za P2P izmenjavo datotek, pridobljeni podatki pa so + analizirani. Vsaka poizvedba po seznamu imetnikov datotek vsebuje ključ podatka v DHT in se prenese preko okoli \begin_inset Formula $\log_{2}n$ diff --git a/inf/rn/dok/lyx/eksperimentalni.lyx b/inf/rn/dok/lyx/eksperimentalni.lyx index 4fd6797..980ee7f 100644 --- a/inf/rn/dok/lyx/eksperimentalni.lyx +++ b/inf/rn/dok/lyx/eksperimentalni.lyx @@ -306,7 +306,29 @@ Eksperimentalni del \end_layout \begin_layout Standard -Namen raziskovalne naloge je prenesti čim več +Namen +\begin_inset Branch seminarska +inverted 1 +status open + +\begin_layout Standard +raziskovalne +\end_layout + +\end_inset + + +\begin_inset Branch seminarska +inverted 0 +status open + +\begin_layout Standard +seminarske +\end_layout + +\end_inset + + naloge je prenesti čim več \family typewriter info \family default diff --git a/inf/rn/dok/lyx/thesis.lyx b/inf/rn/dok/lyx/thesis.lyx index 36056a0..00c2a10 100644 --- a/inf/rn/dok/lyx/thesis.lyx +++ b/inf/rn/dok/lyx/thesis.lyx @@ -165,6 +165,11 @@ customHeadersFooters \filename_suffix 0 \color #faf0e6 \end_branch +\branch seminarska +\selected 1 +\filename_suffix 0 +\color #faf0e6 +\end_branch \index Index \shortcut idx \color #008000 @@ -278,9 +283,30 @@ Use the official terms and title page layout of your university instead \end_layout \begin_layout Title +\begin_inset Branch seminarska +inverted 1 +status open + +\begin_layout Standard Pridobivanje podatkov iz omrežja DHT \end_layout +\end_inset + + +\begin_inset Branch seminarska +inverted 0 +status open + +\begin_layout Standard +Odjemalec za komunikacijski protokol in omrežni teleskop +\end_layout + +\end_inset + + +\end_layout + \begin_layout Subtitle Analiza pretočnega prometa skozi vozlišča protokola BitTorrent in prenos metapodatkov @@ -342,11 +368,53 @@ status open \end_layout \begin_layout Subject +\begin_inset Branch seminarska +inverted 1 +status open + +\begin_layout Standard Računalništvo in informatika \end_layout +\end_inset + + +\begin_inset Branch seminarska +inverted 0 +status open + +\begin_layout Standard +Seminarska naloga pri informatiki +\end_layout + +\end_inset + + +\end_layout + \begin_layout Publishers -Raziskovalna naloga +\begin_inset Branch seminarska +inverted 1 +status open + +\begin_layout Standard +Raziskovalna +\end_layout + +\end_inset + + +\begin_inset Branch seminarska +inverted 0 +status open + +\begin_layout Standard +Seminarska +\end_layout + +\end_inset + + naloga \end_layout \begin_layout Publishers @@ -427,10 +495,14 @@ Gimnazija Bežigrad \end_inset -\begin_inset Note Note +\end_layout + +\begin_layout Publishers +\begin_inset Branch seminarska +inverted 0 status open -\begin_layout Dedication +\begin_layout Standard \begin_inset Quotes eld \end_inset diff --git a/inf/rn/dok/lyx/uvod.lyx b/inf/rn/dok/lyx/uvod.lyx index fd303d6..d593bf4 100644 --- a/inf/rn/dok/lyx/uvod.lyx +++ b/inf/rn/dok/lyx/uvod.lyx @@ -1009,8 +1009,30 @@ V seznam soležnikov za torrent, opisan z njegovim infohashom, vstavi IP \end_layout \begin_layout Standard -Cilj raziskovalne naloge je s sodelovanjem v DHT omrežju pridobiti čim več - obstoječih ključev v razpršilni tabeli, da lahko z operacijo +Cilj +\begin_inset Branch seminarska +inverted 1 +status open + +\begin_layout Standard +raziskovalne +\end_layout + +\end_inset + + +\begin_inset Branch seminarska +inverted 0 +status open + +\begin_layout Standard +seminarske +\end_layout + +\end_inset + + naloge je s sodelovanjem v DHT omrežju pridobiti čim več obstoječih ključev + v razpršilni tabeli, da lahko z operacijo \series bold pridobi soležnike \series default diff --git "a/inf/rn/dok/lyx/zaklju\304\215ek.lyx" "b/inf/rn/dok/lyx/zaklju\304\215ek.lyx" index 28c2ef3..c430135 100644 --- "a/inf/rn/dok/lyx/zaklju\304\215ek.lyx" +++ "b/inf/rn/dok/lyx/zaklju\304\215ek.lyx" @@ -306,8 +306,29 @@ Zaključek \end_layout \begin_layout Standard -Raziskovana naloga predstavi kako je praktično mogoče preprosto implementirati - učinkovito metodo za pridobivanje izvlečka metapodatkov iz omrežja BitTorrent. +\begin_inset Branch seminarska +inverted 1 +status open + +\begin_layout Standard +Raziskovana +\end_layout + +\end_inset + + +\begin_inset Branch seminarska +inverted 0 +status open + +\begin_layout Standard +Seminarska +\end_layout + +\end_inset + + naloga predstavi kako je praktično mogoče preprosto implementirati učinkovito + metodo za pridobivanje izvlečka metapodatkov iz omrežja BitTorrent. Prav tako je prikazana uporabna vrednost korpusa prenesenih podatkov za nadaljnje raziskave in osnovne metode analize takih podatkov. \end_layout diff --git a/inf/zotksd/1 b/inf/zotksd/1 new file mode 100755 index 0000000..a11970d Binary files /dev/null and b/inf/zotksd/1 differ diff --git a/inf/zotksd/1.c b/inf/zotksd/1.c new file mode 100644 index 0000000..7a2de18 --- /dev/null +++ b/inf/zotksd/1.c @@ -0,0 +1,57 @@ +// naloge ne razumem najbolje +#include +#include +#include +#define S 25000 +int main (void) { + int crke[25]; + char buf[S]; + fgets(buf, S, stdin); + int n = strtol(buf, NULL, 10); + for (int i = 0; i < n; i++) { + int crkecopy[25]; + memcpy(crkecopy, crke, sizeof(crke)); + fgets(buf, S, stdin); + char dodaten = -1; +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wsign-compare" + if (strlen(buf) != i+1 && 0) { +#ifndef EVAL + fprintf(stderr, "napačna dolžina niza %s na indeksu %d\n", buf, i); +#endif + printf("%d\n", i); + return 0; + } +#pragma GCC diagnostic pop +#ifndef EVAL + fprintf(stderr, "pri i==%d obdelujem niz %s", i, buf); +#endif + for (int j = 0; j <= i; j++) { + int crka = buf[j]-'A'; + if (--crkecopy[crka] < 0) { + if (dodaten != -1) { + printf("%d\n", i); +#ifndef EVAL + fprintf(stderr, "konec, ker je preveč novih, dodaten je %c\n", dodaten+'A'); +#endif + return 0; + } + dodaten = crka; +#ifndef EVAL + fprintf(stderr, "i==%d, dodaten je sedaj %c\n", i, dodaten+'A'); +#endif + crke[crka]++; + } + } + for (int j = 0; j < 25; j++) + if (crkecopy[j] != 0 && crkecopy[j] != -1) { + printf("%d\n", i); +#ifndef EVAL + fprintf(stderr, "konec, ker ni pobrisal vseh\n"); +#endif + return 0; + } + } + printf("%d\n", n); + return 0; +} diff --git a/inf/zotksd/1.txt b/inf/zotksd/1.txt new file mode 100644 index 0000000..9820f10 --- /dev/null +++ b/inf/zotksd/1.txt @@ -0,0 +1,8 @@ +7 +R +AR +RAK +TRAK +KARTA +RAKETA +TRAKTOR diff --git a/inf/zotksd/1.txt2 b/inf/zotksd/1.txt2 new file mode 100644 index 0000000..334d077 --- /dev/null +++ b/inf/zotksd/1.txt2 @@ -0,0 +1,8 @@ +7 +R +AR +RAK +TRAK +KARTA +RAKETAx +TRAKTOR diff --git a/inf/zotksd/2 b/inf/zotksd/2 new file mode 100755 index 0000000..d5071c2 Binary files /dev/null and b/inf/zotksd/2 differ diff --git a/inf/zotksd/2.c b/inf/zotksd/2.c new file mode 100644 index 0000000..4b6be92 --- /dev/null +++ b/inf/zotksd/2.c @@ -0,0 +1,88 @@ +// todo: moje karte so drevo +#include +#include +#ifdef EVAL +#define NDEBUG 1 +#endif +#include +#define SI 10000000 +static int compar (const void * a, const void * b) { + return *(int *) a < *(int *) b; +} +int in_arr (int elem, int * ar /* najv do najm */, int len) { + int prej = -1; // zadnja obstoječa karta + for (int i = 0; i < len; i++) { + if (ar[i] == -1) // prazen element -- vzeta karta + continue; + if (elem == ar[i]) + return -1; // moja karta + if (elem > ar[i]) { + if (prej == -1) + return -2; // njegova karta, izguba + return prej; + } + prej = i; + } +#ifndef EVAL + fprintf(stderr, "najmanjša karta idx %d vrednost %d\n", len-1, ar[len-1]); +#endif + return len-1; +} +int main (void) { + char * buf = malloc(SI); + fgets(buf, SI, stdin); + char * cp = buf; + int igralcev = strtol(cp, &cp, 10); + int kart = strtol(++cp, NULL, 10); + int NK = igralcev*kart; + int * moje = malloc(sizeof*moje*kart); + int ** njihove = malloc(sizeof*njihove*igralcev); + fgets(buf, SI, stdin); + cp = buf; + for (int j = 0; j < kart; j++) { + moje[j] = strtol(cp, &cp, 10); + cp++; + } + qsort(moje, kart, sizeof(int), compar); + for (int i = 0; i < igralcev-1; i++) { + njihove[i] = malloc(sizeof*moje*kart); + fgets(buf, SI, stdin); + cp = buf; + for (int j = 0; j < kart; j++) { + njihove[i][j] = strtol(cp, &cp, 10); + cp++; + } + qsort(njihove[i], kart, sizeof(int), compar); + } +#ifndef EVAL + for (int i = 0; i < kart; i++) + fprintf(stderr, "%d ", moje[i]); + fprintf(stderr, "\n%d %d\n", in_arr(6, moje, kart), in_arr(3, moje, kart)); + for (int i = 0; i < igralcev-1; i++) { + fprintf(stderr, "igralec %d: ", i); + for (int j = 0; j < kart; j++) + fprintf(stderr, "%d ", njihove[i][j]); + fprintf(stderr, "\n"); + } +#endif + for (int stih = 0; stih < kart; stih++) { + int najv = 0; + for (int i = 0; i < igralcev-1; i++) + if (najv < njihove[i][stih]) + najv = njihove[i][stih]; +#ifndef EVAL + fprintf(stderr, "štih z najv karto %d ", najv); +#endif + int ret = in_arr(najv, moje, kart); + assert(ret != -1); // ne more biti moja karta + if (ret == -2) { + puts("NE\n"); // on ima večjo karto + return 0; + } +#ifndef EVAL + fprintf(stderr, "premagam in porabim karto %d na idx %d\n", moje[ret], ret); +#endif + moje[ret] = -1; // porabim karto + } + puts("DA\n"); +} diff --git a/inf/zotksd/2.txt b/inf/zotksd/2.txt new file mode 100644 index 0000000..68d7fe9 --- /dev/null +++ b/inf/zotksd/2.txt @@ -0,0 +1,3 @@ +2 3 +4 2 6 +5 1 3 diff --git a/inf/zotksd/2.txt2 b/inf/zotksd/2.txt2 new file mode 100644 index 0000000..77472da --- /dev/null +++ b/inf/zotksd/2.txt2 @@ -0,0 +1,4 @@ +3 4 +7 10 6 12 +8 11 4 9 +1 3 5 2 diff --git a/inf/zotksd/3 b/inf/zotksd/3 new file mode 100755 index 0000000..ffb3da7 Binary files /dev/null and b/inf/zotksd/3 differ diff --git a/inf/zotksd/3.c b/inf/zotksd/3.c new file mode 100644 index 0000000..b7723b1 --- /dev/null +++ b/inf/zotksd/3.c @@ -0,0 +1,22 @@ +#include +#include +#include +#define ABS(x) ((x) > 0 ? (x) : -(x)) +#define N unsigned long long int +int main (void) { + char buf[512]; + fgets(buf, 512, stdin); + N n = strtoull(buf, NULL, 10); + N num = 0; + for (N i = 1; i < ceill(sqrtl(n)); i++) { + if (n % i) + continue; + if (ABS(i-n/i) % 2) + continue; + num++; +#ifndef EVAL + fprintf(stderr, "(%llu, %llu)\n", i, n/i); +#endif + } + printf("%llu\n", num); +} diff --git a/inf/zotksd/4 b/inf/zotksd/4 new file mode 100755 index 0000000..634ce55 Binary files /dev/null and b/inf/zotksd/4 differ diff --git a/inf/zotksd/4.c b/inf/zotksd/4.c new file mode 100644 index 0000000..4c3113a --- /dev/null +++ b/inf/zotksd/4.c @@ -0,0 +1,96 @@ +// todo: pazi na težave s prvim elementom +#include +#include +#include +#define S 1600002 +#define ABS(x) ((x) > 0 ? (x) : -(x)) +int main (void) { + int ukazov = 0; + char buf[S]; + fgets(buf, S, stdin); + int n = strtol(buf, NULL, 10); + fgets(buf, S, stdin); + char * cp = buf; + int * arr = calloc(n, sizeof *arr); + int * repr = calloc(10e6, sizeof *arr); + int najrepr = 0; + int najreprval = 0; + for (int i = 0; i < n; i++) { + arr[i] = strtol(cp, &cp, 10); + if (++repr[arr[i]] > najreprval) { + najreprval = repr[arr[i]]; + najrepr = arr[i]; + } + cp++; + } + free(repr); + int razd_od_centr = INT_MAX; + int center = 0; + if (najreprval == 1) { + najrepr = arr[n/2]; + center = n/2; + } + for (int i = 0; i < n; i++) { + if (arr[i] == najrepr && ABS(n/2-i) < razd_od_centr) { + razd_od_centr = ABS(n/2-i); + center = i; + } + } + if (najreprval == 1) { + center = n/2; + } +#ifndef EVAL + fprintf(stderr, "najrepr je število %d, ki ima toliko pojavitev: %d\n", najrepr, najreprval); +#endif + int levo = 0; + int desno = n-1; + s: + while (arr[levo] == najrepr) { + if (levo == n-1) + goto k; + levo++; + } + while (arr[desno] == najrepr) { + if (desno == 0) + goto k; + desno--; + } + if (levo == desno) { + ukazov++; + goto k; + } + if (center > levo && center < desno) { + ukazov++; + arr[levo] = najrepr; + arr[desno] = najrepr; +#ifndef EVAL + fprintf(stderr, "(%d, %d, %d) .. cached center\n", levo, center, desno); +#endif + goto s; + } + center = 0; + for (int i = levo+1; i < desno; i++) { + if (arr[i] == najrepr) { + center = i; + arr[levo] = najrepr; + arr[desno] = najrepr; + ukazov++; +#ifndef EVAL + fprintf(stderr, "(%d, %d, %d) .. našel center, en ukaz\n", levo, center, desno); +#endif + goto s; + } + } + if (center == 0) { + ukazov += 2; + arr[levo] = najrepr; + arr[desno] = najrepr; + arr[(center = levo+(desno-levo)/2)] = najrepr; +#ifndef EVAL + fprintf(stderr, "(%d, %d, %d) .. ni bilo centra, dva ukaza\n", levo, center, desno); +#endif + goto s; + } + k: + printf("%d\n", ukazov); +} diff --git a/inf/zotksd/4.txt b/inf/zotksd/4.txt new file mode 100644 index 0000000..b10a269 --- /dev/null +++ b/inf/zotksd/4.txt @@ -0,0 +1,2 @@ +5 +1 3 2 3 4 diff --git a/inf/zotksd/4.txt2 b/inf/zotksd/4.txt2 new file mode 100644 index 0000000..7191255 --- /dev/null +++ b/inf/zotksd/4.txt2 @@ -0,0 +1,2 @@ +11 +2 2 2 1 1 1 1 1 2 2 2 -- cgit v1.2.3