From 9e3cdb5da0b4fc1ff3b0fca15b4118785aebe026 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Anton=20Luka=20=C5=A0ijanec?= Date: Fri, 13 Jan 2023 17:25:46 +0100 Subject: =?UTF-8?q?=C5=A1olsko=20ra=C4=8Dunalni=C5=A1ko=20tekmovanje=20zot?= =?UTF-8?q?ks?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- .gitignore | 1 + inf/zotks/.gitignore | 8 +++++ inf/zotks/1.c | 25 ++++++++++++++ inf/zotks/1.txt | 5 +++ inf/zotks/2.c | 32 +++++++++++++++++ inf/zotks/2.txt | 3 ++ inf/zotks/3.c | 98 ++++++++++++++++++++++++++++++++++++++++++++++++++++ inf/zotks/3.txt | 13 +++++++ inf/zotks/makefile | 15 ++++++++ 9 files changed, 200 insertions(+) create mode 100644 inf/zotks/.gitignore create mode 100644 inf/zotks/1.c create mode 100644 inf/zotks/1.txt create mode 100644 inf/zotks/2.c create mode 100644 inf/zotks/2.txt create mode 100644 inf/zotks/3.c create mode 100644 inf/zotks/3.txt create mode 100644 inf/zotks/makefile diff --git a/.gitignore b/.gitignore index e317e69..8f583da 100644 --- a/.gitignore +++ b/.gitignore @@ -7,3 +7,4 @@ core .RData .Rhistory *.out +.gdb_history diff --git a/inf/zotks/.gitignore b/inf/zotks/.gitignore new file mode 100644 index 0000000..1aa921d --- /dev/null +++ b/inf/zotks/.gitignore @@ -0,0 +1,8 @@ +1 +2 +3 +4 +5 +6 +core +*.pdf diff --git a/inf/zotks/1.c b/inf/zotks/1.c new file mode 100644 index 0000000..0fcd69e --- /dev/null +++ b/inf/zotks/1.c @@ -0,0 +1,25 @@ +#include +#include +#include +#include +int main (void) { + char buf[256]; + unsigned long long prev = 0; + unsigned long long d; + unsigned long long numl = 0; + unsigned long long a1; + while (1) { + fgets(buf, 256, stdin); + if (ferror(stdin) || feof(stdin)) + break; + numl++; + unsigned long long cur = strtoull(buf, NULL, 10); + if (numl == 1) + a1 = cur; + if (numl == 2) + d = cur-prev; + prev = cur; + } + printf("%llu\n", (prev-a1)/d+1-numl); + return 0; +} diff --git a/inf/zotks/1.txt b/inf/zotks/1.txt new file mode 100644 index 0000000..0160b72 --- /dev/null +++ b/inf/zotks/1.txt @@ -0,0 +1,5 @@ +30 +40 +70 +90 +110 diff --git a/inf/zotks/2.c b/inf/zotks/2.c new file mode 100644 index 0000000..6f71e5b --- /dev/null +++ b/inf/zotks/2.c @@ -0,0 +1,32 @@ +#include +#include +#include +#include +#define N unsigned long long int +N s (N n) { + return (n*(n+1))/2; +} +int main (void) { + char buf[256]; + fgets(buf, 256, stdin); + while (1) { + fgets(buf, 256, stdin); + if (ferror(stdin) || feof(stdin)) + break; + char * c; + N n = strtoull(buf, &c, 10); // imamo n števil + N m = strtoull(++c, &c, 10); // vsota vseh teh n števil je m + N k = strtoull(++c, NULL, 10); // teh n števil razdelimo v k skupin + if (k > n) { // ni možno imeti več skupin kot elementov + fprintf(stdout, "NE\n"); + continue; + } + N smallest_max_in_group = n / k; + // fprintf(stderr, "smallest_max_in_group: %llu, s(smig+1)\n", smallest_max_in_group); + if ((n % k)*s(smallest_max_in_group+1) + (k-(n % k))*s(smallest_max_in_group) > m) + fprintf(stdout, "NE\n"); + else + fprintf(stdout, "DA\n"); + } + return 0; +} diff --git a/inf/zotks/2.txt b/inf/zotks/2.txt new file mode 100644 index 0000000..1f2f1b6 --- /dev/null +++ b/inf/zotks/2.txt @@ -0,0 +1,3 @@ +2 +5 100 2 +2 2 1 diff --git a/inf/zotks/3.c b/inf/zotks/3.c new file mode 100644 index 0000000..1d4208c --- /dev/null +++ b/inf/zotks/3.c @@ -0,0 +1,98 @@ +#include +#include +#include +#include +#include +/* int ob (unsigned long long char * matrika, unsigned long long * obiskan, unsigned long long besed, unsigned long long ttl) { + for (int i = 0; i < besed; i++) { + for (int j = 0; j < besed; j++) { + if (matrika[i*d+j] && obiskan[j]) { + if (obiskan[i] == 0) { + obiskan[i] = obiskan[j]+1; + continue; + } + if (obiskan[j]+1 < obiskan[i]) + obiskan[i] = obiskan[j]+1; // če obstaja krajša pot + } + } + } +} */ +unsigned long long naivno (unsigned char * matrika, unsigned long long * obiskan, unsigned long long besed, unsigned long long ttl, unsigned long long d, unsigned long long lok) { +#ifndef EVAL + fprintf(stderr, "ttl je %llu\n", ttl); +#endif + if (!ttl) + return 0; + // if (obiskan[lok]) // nič več, smo že + // return 0; + obiskan[lok]++; + unsigned long long povezav = 1; + for (unsigned long long i = 0; i < besed; i++) { + if (matrika[besed*i+lok]) + povezav += naivno(matrika, obiskan, besed, ttl-1, d, i); + } + return povezav; +} +int main (void) { + char buf[256]; + fgets(buf, 256, stdin); + char * c; + unsigned long long s = strtoul(buf, &c, 10); + unsigned long long d = strtoul(++c, &c, 10); + unsigned long long n = strtoul(++c, &c, 10); // število otrok + unsigned long long z = strtoul(++c, &c, 10); // ??? . edit kasneje: aja, razumem, prva izrečena beseda + char ** w = malloc(sizeof(char *)*s); + unsigned long long i = 0; + while (i++ <= s) { + fgets(buf, 256 /* še newline in NULL */, stdin); + w[i-1] = strdup(buf); +#ifndef EVAL + fprintf(stderr, "w[%llu]: %s\n", i-1, w[i-1]); +#endif + if (ferror(stdin) || feof(stdin)) + break; + } + unsigned char matrika[s*s]; // en megabajt največ, gucci + memset(matrika, '\0', s*s); + for (unsigned long long i = 0; i < s; i++) { +#ifndef EVAL + fprintf(stderr, "%llu\n", i); +#endif + for (unsigned long long j = 0; j < s; j++) { + int ne = 0; + for (unsigned long long k = 0; k < d; k++) + if (w[i][k] != w[j][k]) + ne++; + if (ne <= 1) + matrika[s*i+j] = 1; + } + } +#ifndef EVAL + for (unsigned long long i = 0; i < s; i++) { + for (unsigned long long j = 0; j < s; j++) { + fprintf(stderr, "%u ", matrika[s*i+j]); + } + fprintf(stderr, "\n"); + } +#endif + unsigned long long obiskan[s]; // da vpisujemo TTLje + memset(obiskan, '\0', s*sizeof(unsigned long long)); + fprintf(stderr, "%llu\n", naivno(matrika, obiskan, s, n+1, d, z)); + unsigned cx = 0; + for (int i = 0; i < s; i++) { + if (obiskan[i]) + cx++; + } + fprintf(stdout, "%u\n", cx); + /* + int ret = ob(matrika, obiskan, d, n); + if (ret == -1) { // nihče ni bil dodatno obiskan + unsigned long long obiskanih = 0; + for (int i = 0; i < d; i++) + if (obiskan[d]) + obiskanih++; + fprintf(stdout, "%u\n", obiskanih); + return 0; + }*/ + return 0; +} diff --git a/inf/zotks/3.txt b/inf/zotks/3.txt new file mode 100644 index 0000000..65d9d10 --- /dev/null +++ b/inf/zotks/3.txt @@ -0,0 +1,13 @@ +12 4 3 1 +DOZA +KOZA +ROZA +KOMA +VRBA +KOSA +KODA +GRBA +ROBA +RIBA +DOBA +KOST diff --git a/inf/zotks/makefile b/inf/zotks/makefile new file mode 100644 index 0000000..f6c8f90 --- /dev/null +++ b/inf/zotks/makefile @@ -0,0 +1,15 @@ +CF=-Wall -Wextra -Wformat -Wformat-security -pedantic -g -O0 -I. +LF=-lm +default: $(subst .c,,$(shell find -name '*.c')) +%: %.c + $(CC) $(CF) $(CFLAGS) $< -o$@ $(LF) $(LDFLAGS) + +navodila: s1_super_trojcek.pdf s1_tek.pdf s1_telefon.pdf + +%.pdf: + wget http://upload/d/$@ + +clean: + rm -f 1 2 3 4 5 6 *.pdf + +.PHONY: default clean navodila -- cgit v1.2.3