From 3b691374cee62465a3ffac260ea915fc8233f73d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Anton=20Luka=20=C5=A0ijanec?= Date: Mon, 10 Feb 2025 13:35:52 +0100 Subject: t2izpadi plus vse aps1dn --- .gitignore | 10 + skripti/.gitignore | 1 + skripti/t2izpadi.php | 16 +- "skripti/zaokro\305\276i.py" | 14 + "\305\241ola/ana3/teor.lyx" | 1372 +++++++++++++++++++- "\305\241ola/aps1/dn/.gitignore" | 7 + .../aps1/dn/autocomplete/re\305\241itev.cpp" | 138 +- "\305\241ola/aps1/dn/druga/re\305\241itev.cpp" | 75 ++ "\305\241ola/aps1/dn/druga/test.cpp" | 10 + "\305\241ola/aps1/dn/funkcije/nova.cpp" | 52 + "\305\241ola/aps1/dn/funkcije/re\305\241itev.cpp" | 105 ++ "\305\241ola/aps1/dn/neboti\304\215niki/in.txt" | 6 + "\305\241ola/aps1/dn/neboti\304\215niki/nova.cpp" | 28 + .../aps1/dn/neboti\304\215niki/resitev.cpp" | 19 + "\305\241ola/aps1/dn/osvetlitev/geninput.py" | 13 + "\305\241ola/aps1/dn/otoki/nova.cpp" | 82 ++ "\305\241ola/aps1/dn/otoki/re\305\241itev.cpp" | 82 ++ .../aps1/dn/razporeditev/re\305\241itev.cpp" | 63 + .../aps1/dn/vre\304\215a/re\305\241itev.cpp" | 61 + "\305\241ola/aps1/dn/vzorec/re\305\241itev.cpp" | 94 ++ "\305\241ola/aps1/dn/vzorec/stara.cpp" | 76 ++ 21 files changed, 2269 insertions(+), 55 deletions(-) create mode 100755 "skripti/zaokro\305\276i.py" create mode 100644 "\305\241ola/aps1/dn/.gitignore" create mode 100644 "\305\241ola/aps1/dn/druga/re\305\241itev.cpp" create mode 100644 "\305\241ola/aps1/dn/druga/test.cpp" create mode 100644 "\305\241ola/aps1/dn/funkcije/nova.cpp" create mode 100644 "\305\241ola/aps1/dn/funkcije/re\305\241itev.cpp" create mode 100644 "\305\241ola/aps1/dn/neboti\304\215niki/in.txt" create mode 100644 "\305\241ola/aps1/dn/neboti\304\215niki/nova.cpp" create mode 100644 "\305\241ola/aps1/dn/neboti\304\215niki/resitev.cpp" create mode 100755 "\305\241ola/aps1/dn/osvetlitev/geninput.py" create mode 100644 "\305\241ola/aps1/dn/otoki/nova.cpp" create mode 100644 "\305\241ola/aps1/dn/otoki/re\305\241itev.cpp" create mode 100644 "\305\241ola/aps1/dn/razporeditev/re\305\241itev.cpp" create mode 100644 "\305\241ola/aps1/dn/vre\304\215a/re\305\241itev.cpp" create mode 100644 "\305\241ola/aps1/dn/vzorec/re\305\241itev.cpp" create mode 100644 "\305\241ola/aps1/dn/vzorec/stara.cpp" diff --git a/.gitignore b/.gitignore index 777d05d..405d979 100644 --- a/.gitignore +++ b/.gitignore @@ -29,3 +29,13 @@ core.* *.cmd *.symvers *.order +program +.swo +.swp +*.gcov.* +*.gcno +*.gcda +*.gcov +*.265t.optimized +coverage_report/ +coverage.info diff --git a/skripti/.gitignore b/skripti/.gitignore index c73a7f5..527e94e 100644 --- a/skripti/.gitignore +++ b/skripti/.gitignore @@ -1,2 +1,3 @@ code128 črtna_koda +t2izpadi.sqlite3 diff --git a/skripti/t2izpadi.php b/skripti/t2izpadi.php index 9ab3394..d1212de 100755 --- a/skripti/t2izpadi.php +++ b/skripti/t2izpadi.php @@ -44,11 +44,17 @@ if (!$db) { error_log("Ne morem odpreti podatnovne zbirke!"); exit(1); } -$db->query("create table if not exists izpadi (hash TEXT PRIMARY KEY UNIQUE NOT NULL, napovedan INTEGER, naslov TEXT NOT NULL, od TEXT NOT NULL, do TEXT NOT NULL, kraj TEXT, besedilo TEXT NOT NULL, first default CURRENT_TIMESTAMP, last default CURRENT_TIMESTAMP)"); +$db->query("create table if not exists izpadi (hash TEXT PRIMARY KEY UNIQUE NOT NULL, napovedan INTEGER, naslov TEXT NOT NULL, od TEXT NOT NULL, do TEXT NOT NULL, kraj TEXT, besedilo TEXT NOT NULL, first default CURRENT_TIMESTAMP, last default CURRENT_TIMESTAMP, lost)"); $db->query("create table if not exists poizvedbe (datum default CURRENT_TIMESTAMP, objavljenih INTEGER NOT NULL, zakasnitev INTEGER NOT NULL)"); +$stored_hashes = []; +$found_hashes = []; +$stmt = $db->query("select hash from izpadi where lost IS NULL;"); +while ($row = $stmt->fetch(PDO::FETCH_ASSOC)) + $stored_hashes[] = $row["hash"]; $stmt = $db->prepare("insert into izpadi (hash, napovedan, naslov, od, do, kraj, besedilo) values (:hash, :napovedan, :naslov, :od, :do, :kraj, :besedilo) ON CONFLICT(hash) DO UPDATE SET last=CURRENT_TIMESTAMP"); foreach ($izpadi as $izpad) { $hash = hex2bin($izpad["hash"]); + $found_hashes[] = $hash; $stmt->bindParam(":hash", $hash); $stmt->bindParam(":napovedan", $izpad["napovedan"]); $stmt->bindParam(":naslov", $izpad["naslov"]); @@ -58,4 +64,12 @@ foreach ($izpadi as $izpad) { $stmt->bindParam(":besedilo", $izpad["besedilo"]); $stmt->execute(); } +$lost_hashes = array_diff($stored_hashes, $found_hashes); +if (sizeof($found_hashes) /* mogoče je website crknil in nismo dobili nobenih obvestil, v tem primeru ne štejemo obvestil kot izgubljenih */) { + $stmt = $db->prepare("update izpadi set lost=CURRENT_TIMESTAMP where hash=:lost_hash"); + foreach ($lost_hashes as $lost_hash) { + $stmt->bindParam(":lost_hash", $lost_hash); + $stmt->execute(); + } +} $db->query("insert into poizvedbe (datum, objavljenih, zakasnitev) VALUES (CURRENT_TIMESTAMP, " . sizeof($izpadi) . ", " . hrtime(TRUE)-$hrstart . ")"); diff --git "a/skripti/zaokro\305\276i.py" "b/skripti/zaokro\305\276i.py" new file mode 100755 index 0000000..67d8270 --- /dev/null +++ "b/skripti/zaokro\305\276i.py" @@ -0,0 +1,14 @@ +#!/usr/bin/python3 +import sys +import itertools as it +if len(sys.argv) < 3: + print(f"uporaba: {sys.argv[0]} max_količina_posameznega cena1 [cena2 [cena3 ...]]", file=sys.stderr) + exit(1) +for i in it.product(range(int(sys.argv[1])+1), repeat=len(sys.argv)-2): + cena = 0 + for j in range(len(i)): + cena += i[j] * int(sys.argv[2+j]) + print(cena, end="\t") + for j in i: + print(j, end="\t") + print() diff --git "a/\305\241ola/ana3/teor.lyx" "b/\305\241ola/ana3/teor.lyx" index ea70ccd..646bb2d 100644 --- "a/\305\241ola/ana3/teor.lyx" +++ "b/\305\241ola/ana3/teor.lyx" @@ -32,6 +32,7 @@ \DeclareMathOperator{\End}{End} \DeclareMathOperator{\n}{n} \DeclareMathOperator{\Col}{Col} +\DeclareMathOperator{\Erf}{Erf} \usepackage{algorithm,algpseudocode} \providecommand{\corollaryname}{Posledica} \usepackage[slovenian=quotes]{csquotes} @@ -39,8 +40,8 @@ \use_default_options true \begin_modules enumitem -theorems-ams -theorems-ams-extended +theorems-ams-chap-bytype +theorems-ams-extended-chap-bytype \end_modules \maintain_unincluded_children no \language slovene @@ -189,8 +190,1373 @@ Ideja \end_layout \begin_layout Standard -Obbravnavali bomo funkcije, +Obravnavali bomo funkcije, katerih predpis je podan s pomočjo določenega integrala. + Spomnimo: + Določeni integral je operacija, + ki trojici +\begin_inset Formula $f,a,b$ +\end_inset + + priredi realno število. + +\begin_inset Formula $I=\int_{a}^{b}f\left(t\right)dt\in\mathbb{R}$ +\end_inset + +. + Imamo dva načina, + s katerima ta predpis pretvorimo v funkcijo. +\end_layout + +\begin_layout Itemize +variiramo integrand: + +\begin_inset Formula $F\left(x\right)=\int_{0}^{1}xtdt,x\in\mathbb{R}$ +\end_inset + + in velja +\begin_inset Formula $F\left(-1\right)=\frac{-1}{2}$ +\end_inset + +, + +\begin_inset Formula $F\left(1\right)=\frac{1}{2}$ +\end_inset + +, + +\begin_inset Formula $F\left(2\right)=1$ +\end_inset + +, + +\begin_inset Formula $F\left(0\right)=0$ +\end_inset + +. + +\begin_inset Formula $F\left(x\right)$ +\end_inset + + je podana s ploščino za konkreten +\begin_inset Formula $x$ +\end_inset + +. + Opisani primer je sila preprost, + saj lahko +\begin_inset Formula $x$ +\end_inset + + izrazimo: + +\begin_inset Formula +\[ +F\left(x\right)=\int_{0}^{1}xtdt=x\int_{0}^{1}tdt=\left.\frac{xt^{2}}{2}\right|_{0}^{1}=\frac{x}{2}-0=\frac{x}{2} +\] + +\end_inset + + +\end_layout + +\begin_layout Itemize +variiramo meje integrala: + +\begin_inset Formula $F\left(x\right)=\int_{0}^{x}tdt,x\in\mathbb{R}$ +\end_inset + +. + Opomba: + iz 1. + letnika vemo, + da je +\begin_inset Formula $F'\left(x\right)=\left(\int_{0}^{x}tdt\right)'=x$ +\end_inset + + — + osnovni izrek analize: +\begin_inset Formula +\[ +\frac{\partial\int_{0}^{x}f\left(t\right)dt}{\partial x}=f\left(x\right) +\] + +\end_inset + + +\end_layout + +\begin_layout Standard +Ko oba načina združimo, + dobimo splošen predpis. +\end_layout + +\begin_layout Definition +Integral s parametrom je +\begin_inset Formula $F\left(x\right)=\int_{u\left(x\right)}^{v\left(x\right)}f\left(x,t\right)dt$ +\end_inset + + za +\begin_inset Formula $x\in D\subseteq\mathbb{R}$ +\end_inset + +, + +\begin_inset Formula $u,v:D\to\mathbb{R}$ +\end_inset + +, + +\begin_inset Formula $f:D\times\left[u\left(x\right),v\left(x\right)\right]\to\mathbb{R}$ +\end_inset + +, + kjer +\begin_inset Formula $\forall x\in D:f$ +\end_inset + + integrabilna po +\begin_inset Formula $t\in\left[u\left(x\right),v\left(x\right)\right]$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Naš cilj je obravnavati zveznost, + odvedljivost in integrabilnost integrala s parametrom preko lastnosti +\begin_inset Formula $u,v$ +\end_inset + + in +\begin_inset Formula $f$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Tovrstne integralske funkcije so pomembne za: +\end_layout + +\begin_layout Enumerate +razširjanje nabora elementarnih funkcij. + Doslej spoznane funkcije so elementarne (racionalne, + trigonometrične, + eksponentne, + krožne, + hiperbolične, + njihovi inverzi in kompozitumi). + Integrali s parametrom pa ta nabor razširjajo. + Netrivialno dejstvo, + sicer dokazano z računalnikom, + je, + da +\begin_inset Formula +\[ +\int\frac{\sin x}{x}dx +\] + +\end_inset + +ni elementarna funkcija. + Posledično sta tudi +\begin_inset Formula +\[ +F\left(x\right)=\int_{0}^{x}\frac{\sin t}{t}dt\quad\text{in}\quad G\left(x\right)=\int_{0}^{\pi}\frac{\sin\left(xt\right)}{t}dt +\] + +\end_inset + +neelementarni funkciji. + Komentar: + po osnovnem izreku velja +\begin_inset Formula $F'\left(x\right)=\left(\int_{0}^{x}\frac{\sin t}{t}dt\right)'=\frac{\sin x}{x}$ +\end_inset + +, + torej ima neelementarna funkcija lahko elementaren odvod. +\end_layout + +\begin_deeper +\begin_layout Standard +S ploščinami je podana neelementarna funkcija +\begin_inset Formula $G\left(x\right)$ +\end_inset + +. + Radi bi jo odvajali. +\end_layout + +\end_deeper +\begin_layout Enumerate +modeliranje. + Gravitacijsko silo med za +\begin_inset Formula $r$ +\end_inset + + oddaljenima telesoma z masama +\begin_inset Formula $m$ +\end_inset + + in +\begin_inset Formula $M$ +\end_inset + + izračunamo kot +\begin_inset Formula $F_{g}=\frac{GMm}{r^{2}}$ +\end_inset + +. + Imejmo palico od +\begin_inset Formula $-1$ +\end_inset + + do +\begin_inset Formula $1$ +\end_inset + + z nehomogeno gostoto +\begin_inset Formula $\rho\left(t\right)$ +\end_inset + + in delec z maso +\begin_inset Formula $m$ +\end_inset + + na koordinati +\begin_inset Formula $x>1$ +\end_inset + + vzdolž palice. + S kakšno silo palica privlači delec? + +\begin_inset Formula +\[ +F\left(x\right)=\int_{-1}^{1}\frac{G\rho\left(t\right)m}{\left(x-t\right)^{2}}dt. +\] + +\end_inset + + +\end_layout + +\begin_layout Enumerate +reševanje diferencialnih enačb. + Rešimo +\begin_inset Formula $y'=y^{2}\cos x^{3}$ +\end_inset + + pri pogoju +\begin_inset Formula $y\left(0\right)=1$ +\end_inset + +. +\begin_inset Formula +\[ +\frac{\partial y}{\partial x}=y^{2}\cos x^{3} +\] + +\end_inset + + +\begin_inset Formula +\[ +\frac{dy}{y^{2}}=\cos x^{3}dx\quad\quad\quad/\int +\] + +\end_inset + + +\begin_inset Formula +\[ +\int\frac{dy}{y^{2}}=\int\cos x^{3}dx +\] + +\end_inset + + +\begin_inset Formula +\[ +\frac{-1}{y}=\int\cos x^{3}dx +\] + +\end_inset + +Desne strani enačbe ne znamo integrirati, + ni elementarna. + Zapišimo jo kot integral s parametrom. + Namesto +\begin_inset Formula $\int\cos x^{3}dx$ +\end_inset + + zapišimo +\begin_inset Formula $\int_{0}^{x}\cos t^{3}dt$ +\end_inset + +, + saj ima ta funkcija ustrezen odvod: + +\begin_inset Formula $\cos x^{3}=\left(\int_{0}^{x}\cos t^{3}dt\right)'$ +\end_inset + +. + Torej +\begin_inset Formula +\[ +\frac{-1}{y}=\int_{0}^{x}\cos t^{3}dt+\tilde{C} +\] + +\end_inset + + +\begin_inset Formula +\[ +y=\frac{1}{C-\int_{0}^{x}\cos t^{3}dt} +\] + +\end_inset + +Začetni pogoj: + +\begin_inset Formula $1=y\left(0\right)=\frac{1}{C-\cancel{\int_{0}^{0}\cdots}}=\frac{1}{C}\Rightarrow C=1$ +\end_inset + +, + torej +\begin_inset Formula +\[ +y\left(x\right)=\frac{1}{1-\int_{0}^{x}\cos t^{3}dt}. +\] + +\end_inset + + +\end_layout + +\begin_layout Subsection +Analiza integralov s parametrom +\end_layout + +\begin_layout Standard +Osrednja orodja za analizo podajo naslednji trije izreki. +\end_layout + +\begin_layout Theorem +\begin_inset CommandInset label +LatexCommand label +name "thm:zveznost" + +\end_inset + +Naj bo +\begin_inset Formula $f\left(x,t\right)$ +\end_inset + + zvezna na +\begin_inset Formula $\left[a,b\right]\times\left[c,d\right]$ +\end_inset + +. + Potem je tudi integral s parametrom +\begin_inset Formula $F\left(x\right)=\int_{c}^{d}f\left(x,t\right)dt$ +\end_inset + + zvezen na +\begin_inset Formula $\left[a,b\right]$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Theorem +\begin_inset CommandInset label +LatexCommand label +name "thm:odvedljivost" + +\end_inset + +Naj bo +\begin_inset Formula $f\left(x,t\right)$ +\end_inset + + zvezna in zvezno parcialno odvedljiva po +\begin_inset Formula $x$ +\end_inset + + na +\begin_inset Formula $\left[a,b\right]\times\left[c,d\right]$ +\end_inset + +. + Potem je +\begin_inset Formula $F\left(x\right)=\int_{c}^{d}f\left(x,t\right)dt$ +\end_inset + + odvedljiva na +\begin_inset Formula $\left[a,b\right]$ +\end_inset + + in za njen odvod velja, + da lahko odvajamo pod integralom, + t. + j. +\begin_inset Formula +\[ +F'\left(x\right)=\int_{c}^{d}\frac{\partial f\left(x,t\right)}{\partial x}dt. +\] + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Theorem +\begin_inset CommandInset label +LatexCommand label +name "thm:integrabilnost" + +\end_inset + +Naj bo +\begin_inset Formula $f\left(x,t\right)$ +\end_inset + + zvezna na +\begin_inset Formula $\left[a,b\right]\times\left[c,d\right]$ +\end_inset + +. + Tedaj je +\begin_inset Formula $F\left(x\right)=\int_{c}^{d}f\left(x,t\right)dt$ +\end_inset + + integrabilna na +\begin_inset Formula $\left[a,b\right]$ +\end_inset + + in lahko integriramo pod integralom oziroma menjamo vrstni red integriranja, + ZDB velja +\begin_inset Formula +\[ +\int_{a}^{b}F\left(x\right)dx=\int_{a}^{b}\int_{c}^{d}f\left(x,t\right)dtdx=\int_{c}^{d}\int_{a}^{b}f\left(x,t\right)dxdt. +\] + +\end_inset + + +\end_layout + +\begin_layout Remark +Vsi trije izreki se ukvarjajo le s fiksnimi mejami, + vendar nam v izreku +\begin_inset CommandInset ref +LatexCommand ref +reference "thm:zveznost" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + + in +\begin_inset CommandInset ref +LatexCommand ref +reference "thm:integrabilnost" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + + ta izjava pokriva tudi premične meje; + če je +\begin_inset Formula $f\left(x,t\right)$ +\end_inset + + zvezna na +\begin_inset Formula $\left[a,b\right]\times\left[c,d\right]$ +\end_inset + + in je +\begin_inset Formula $u\left(x\right),v\left(x\right)\in\left[c,d\right]$ +\end_inset + + za vse +\begin_inset Formula $x\in\left[a,b\right]$ +\end_inset + +. + Če je torej zaloga vrenosti +\begin_inset Formula $u$ +\end_inset + + in +\begin_inset Formula $v$ +\end_inset + + znotraj območja zveznosti, + je edina dodatna zahteva, + da sta +\begin_inset Formula $u$ +\end_inset + + in +\begin_inset Formula $v$ +\end_inset + + zvezni. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Remark +Pri izreku +\begin_inset CommandInset ref +LatexCommand ref +reference "thm:odvedljivost" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + + se malce bolj zaplete (uvesti moramo dodaten pogoj parcialne odvedljivosti). + Več o tem kasneje. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Remark +V izreku +\begin_inset CommandInset ref +LatexCommand ref +reference "thm:integrabilnost" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + + integrabilnost sledi že iz izreka +\begin_inset CommandInset ref +LatexCommand ref +reference "thm:zveznost" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + +, + dodatno pa izveno za menjavo meja. +\end_layout + +\begin_layout Paragraph* +Ilustracija izreka +\begin_inset CommandInset ref +LatexCommand ref +reference "thm:zveznost" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + + +\end_layout + +\begin_layout Enumerate +Naj bo +\begin_inset Formula $F\left(x\right)=\int_{0}^{1}xtdt$ +\end_inset + +. + Integrand +\begin_inset Formula $f\left(x,t\right)=xt$ +\end_inset + + je zvezen na +\begin_inset Formula $\mathbb{R}^{2}$ +\end_inset + +. + Posledično lahko pričakujemo, + da je tudi funkcija +\begin_inset Formula $F\left(x\right)$ +\end_inset + + zvezna +\begin_inset Formula $\forall x\in\mathbb{R}$ +\end_inset + +. + Ker vemo, + da je +\begin_inset Formula $F\left(x\right)=\left.\frac{xt^{2}}{2}\right|_{0}^{1}=\frac{x}{2}$ +\end_inset + +, + je to očitno res. +\end_layout + +\begin_layout Enumerate +Naj bo +\begin_inset Formula $F\left(x\right)=\int_{0}^{1}e^{xt}dt$ +\end_inset + +. + Integrand +\begin_inset Formula $f\left(x,t\right)=e^{xt}$ +\end_inset + + je zvezen na +\begin_inset Formula $\mathbb{R}^{2}$ +\end_inset + +. + Pričakujemo zveznost +\begin_inset Formula $F\left(x\right)$ +\end_inset + + na +\begin_inset Formula $\mathbb{R}$ +\end_inset + +. + Poskusimo preveriti direktno: +\begin_inset Formula +\[ +F\left(x\right)=\int_{0}^{1}e^{xt}dt=\left.\frac{e^{xt}}{x}\right|_{0}^{1}=\frac{e^{x}-1}{x} +\] + +\end_inset + +Problem je v +\begin_inset Formula $x=0$ +\end_inset + +. + +\begin_inset Formula $F\left(0\right)=\int_{0}^{1}e^{0t}dt=\int_{0}^{1}1dt=1$ +\end_inset + +. + Torej je naša +\begin_inset Formula $F$ +\end_inset + + podana s predpisom +\begin_inset Formula +\[ +F\left(x\right)=\begin{cases} +\frac{e^{x}-1}{x} & ;x\not=0\\ +1 & ;x=0 +\end{cases} +\] + +\end_inset + +in to je zvezna funkcija, + kot bi pričakovali, + kajti +\begin_inset Formula +\[ +\lim_{x\to0}\frac{e^{x}-1}{x}\overset{\text{L.H.}}{=}\lim_{x\to0}e^{x}=e^{0}=1. +\] + +\end_inset + + +\end_layout + +\begin_layout Proof +Dokažimo izrek +\begin_inset CommandInset ref +LatexCommand ref +reference "thm:zveznost" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + +. + Dokazati moramo, + da je +\begin_inset Formula $F$ +\end_inset + + zvezna v +\begin_inset Formula $x_{0}\in\left[a,b\right]$ +\end_inset + +, + torej +\begin_inset Formula $\forall\varepsilon>0\exists\delta\left(x_{0},\varepsilon\right)>0\forall x\in D_{F}:\left|x-x_{0}\right|<\delta\Rightarrow\left|F\left(x\right)-F\left(x_{0}\right)\right|<\varepsilon$ +\end_inset + +. + Po predpostavki je +\begin_inset Formula $f$ +\end_inset + + zvezna v +\begin_inset Formula $\left(x_{0},t_{0}\right)\in\left[a,b\right]\times\left[c,d\right]$ +\end_inset + +, + torej +\begin_inset Formula $\forall\varepsilon>0\exists\delta\left(\left(x_{0},t_{0}\right),\varepsilon\right)>0\forall a\in D_{f}:\left|\left|\left(x_{0},t_{0}\right)-a\right|\right|<\delta\Rightarrow\left|f\left(x_{0},t_{0}\right)-f\left(a\right)\right|<\varepsilon$ +\end_inset + +. +\end_layout + +\begin_layout Proof +BSŠ +\begin_inset Formula $\delta$ +\end_inset + + v predpostavki je zvezno odvisna od +\begin_inset Formula $x_{0}$ +\end_inset + + in +\begin_inset Formula $t_{0}$ +\end_inset + +. + Ker nas zanima +\begin_inset Formula $t_{0}\in\left[c,d\right]$ +\end_inset + +, + +\begin_inset Formula $\exists\delta$ +\end_inset + +, + ki je minimalna; + +\begin_inset Formula $\delta\coloneqq\min_{t_{0}\in\left[c,d\right]}\delta\left(x_{0},t_{0}\right)$ +\end_inset + +. + Velja +\begin_inset Formula +\[ +\left|\sqrt{\left(x-x_{0}\right)^{2}-\left(t-t_{0}\right)^{2}}\right|<\delta\left(x_{0},t_{0}\right)\overset{f\text{ zvezna}}{\Longrightarrow}\left|f\left(x,t\right)-f\left(x_{0},t_{0}\right)\right|<\varepsilon. +\] + +\end_inset + +Če torej izberemo +\begin_inset Formula $x,x_{0}\in\left[a,b\right]$ +\end_inset + +, + da je +\begin_inset Formula $\left|x-x_{0}\right|<\delta,$ +\end_inset + + dobimo +\begin_inset Formula +\[ +\left|F\left(x\right)-F\left(x_{0}\right)\right|=\left|\int_{c}^{d}f\left(x,t\right)dt-\int_{c}^{d}f\left(x_{0},t\right)dt\right|\leq\int_{c}^{d}\left|f\left(x,t\right)-f\left(x_{0},f\right)\right|dt\leq\cdots +\] + +\end_inset + + +\begin_inset Formula $t-$ +\end_inset + +ja se ujemata, + torej +\begin_inset Formula $\left|x-x_{0}\right|<\delta\leq\delta\left(x_{0},t_{0}\right)$ +\end_inset + +, + zato +\begin_inset Formula +\[ +\cdots\leq\int_{c}^{d}\varepsilon dt=\varepsilon\left(d-c\right). +\] + +\end_inset + +Če bi začeli z +\begin_inset Formula $\varepsilon'\coloneqq\frac{\varepsilon}{d-c}$ +\end_inset + +, + bi dobili želeno neenakost, + t. + j. + +\begin_inset Formula $\left|x-x_{0}\right|<\delta'\Rightarrow\left|F\left(x\right)-F\left(x_{0}\right)\right|<\varepsilon$ +\end_inset + +. + Dokazali smo: + Če se integrandi spreminjajo zvezno, + se tudi ploščine spreminjajo zvezno. +\end_layout + +\begin_layout Example* +\begin_inset Formula +\[ +F\left(x\right)=\int_{0}^{1}e^{-\left(xt\right)^{2}}dt +\] + +\end_inset + +Znano je, + da +\begin_inset Formula $F$ +\end_inset + + ni elementarna funkcija, + torej +\begin_inset Formula $F$ +\end_inset + + ne moremo izraziti, + a vseeno po zgoraj dokazanem izreku vemo, + da je +\begin_inset Formula $F$ +\end_inset + + zvezna na +\begin_inset Formula $\mathbb{R}$ +\end_inset + +, + ker je integrand +\begin_inset Formula $f\left(x,t\right)=e^{-\left(xt\right)^{2}}$ +\end_inset + + zvezna na +\begin_inset Formula $\mathbb{R}\times\left[0,1\right]$ +\end_inset + +. +\end_layout + +\begin_layout Question* +Kaj pa, + če bi bil parameter v meji? + Oglejmo si funkcijo +\begin_inset Quotes gld +\end_inset + +error function +\begin_inset Quotes grd +\end_inset + +: +\begin_inset Formula +\[ +G\left(x\right)=\int_{0}^{x}e^{-t^{2}}dt=\Erf\left(x\right) +\] + +\end_inset + + +\end_layout + +\begin_layout Question* +Za to funkcijo ne moremo uporabiti izreka, + saj meje niso fiksne, + lahko pa zveznost dokažemo direktno: +\begin_inset Formula +\[ +\left|G\left(x\right)-G\left(x_{0}\right)\right|=\left|\int_{0}^{x}e^{-t^{2}}dt-\int_{0}^{x_{0}}e^{-t^{2}}dt\right|=\left|\int_{x_{0}}^{x}e^{-t^{2}}dt\right|\leq\cdots +\] + +\end_inset + +Premislek pokaže, + da je +\begin_inset Formula $\sup_{t\in\mathbb{R}}e^{-t^{2}}=1$ +\end_inset + +, + torej +\begin_inset Formula +\[ +\cdots\leq\left|\int_{x_{0}}^{x}1dt\right|=\left|x-x_{0}\right|<\varepsilon +\] + +\end_inset + +In za +\begin_inset Formula $\varepsilon=\delta$ +\end_inset + + velja +\begin_inset Formula $\forall\varepsilon>0\exists\delta>0\ni:\left|x-x_{0}\right|<\delta\Rightarrow\left|F\left(x\right)-F\left(x_{0}\right)\right|<\varepsilon$ +\end_inset + +. +\end_layout + +\begin_layout Lemma* +Lagrangev izrek. + Naj bo +\begin_inset Formula $g$ +\end_inset + + zvezna na +\begin_inset Formula $\left[a,b\right]$ +\end_inset + + in odvedljiva na +\begin_inset Formula $\left(a,b\right)$ +\end_inset + +. + Potem +\begin_inset Formula $\exists c\in\left(a,b\right)\ni:g'\left(c\right)=\frac{g\left(b\right)-g\left(a\right)}{b-a}\sim g\left(b\right)-g\left(a\right)=g'\left(c\right)\left(b-a\right)$ +\end_inset + +. + Dokaz na ANA1 +\begin_inset Foot +status open + +\begin_layout Plain Layout +\begin_inset CommandInset href +LatexCommand href +target "http://splet.4a.si./dir/ana1teor.pdf" + +\end_inset + + +\end_layout + +\end_inset + +. +\end_layout + +\begin_layout Proof +Dokaz izreka +\begin_inset CommandInset ref +LatexCommand ref +reference "thm:odvedljivost" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + +. + V našem primeru izberemo +\begin_inset Formula $\xi\left(t\right)$ +\end_inset + + med +\begin_inset Formula $x$ +\end_inset + + in +\begin_inset Formula $x_{0}$ +\end_inset + +, + da pri fiksnem +\begin_inset Formula $t\in\left[x,x_{0}\right]$ +\end_inset + + velja, + da je +\begin_inset Formula $f\left(x,t\right)-f\left(x_{0},t\right)=f_{x}\left(\xi,t\right)\left(x-x_{0}\right)$ +\end_inset + +. +\end_layout + +\begin_layout Proof +Izračunajmo +\begin_inset Formula $F'\left(x_{0}\right)$ +\end_inset + + po definiciji. + +\begin_inset Formula +\[ +F'\left(x_{0}\right)=\lim_{x\to x_{0}}\frac{F\left(x\right)-F\left(x_{0}\right)}{x-x_{0}}=\lim_{x\to x_{0}}\frac{1}{x-x_{0}}\left(\int_{c}^{d}f\left(x,t\right)dt-\int_{c}^{d}f\left(x_{0},t\right)dt\right)= +\] + +\end_inset + + +\begin_inset Formula +\[ +=\lim_{x\to x_{0}}\frac{1}{x-x_{0}}\int_{c}^{d}\left(f\left(x,t\right)-f\left(x_{0},t\right)\right)dt\overset{\text{Lagrange}}{=}\lim_{x\to x_{0}}\cancel{\frac{1}{x-x_{0}}}\int_{c}^{d}f_{x}\left(\xi,t\right)\cancel{\left(x-x_{0}\right)}dt= +\] + +\end_inset + + +\begin_inset Formula +\[ +=\lim_{x\to x_{0}}\int_{c}^{d}f_{x}\left(\xi,t\right)dt\overset{\text{zveznost na kompaktu}}{=}\int_{c}^{d}\lim_{x\to x_{0}}f_{x}\left(\xi,t\right)dt\overset{f_{x}\text{ zvezna}}{=}\int_{c}^{d}f_{x}\left(\lim_{x\to x_{0}}\xi,t\right)dt\overset{\text{izbira \ensuremath{\xi}}}{=}\int_{c}^{d}f\left(x_{0},t\right)dt +\] + +\end_inset + +Sklep: + +\begin_inset Formula $F'\left(x_{0}\right)=\int_{c}^{d}f_{x}\left(x_{0},t\right)dt$ +\end_inset + +. +\end_layout + +\begin_layout Example +\begin_inset Formula +\[ +F\left(x\right)=\int_{0}^{1}txdt=\frac{x}{2}. +\] + +\end_inset + + +\begin_inset Formula $F'\left(x\right)\overset{\text{direktno}}{=}\frac{1}{2}$ +\end_inset + +, + +\begin_inset Formula $F\left(x\right)\overset{\text{izrek}}{=}\int_{0}^{1}\frac{\partial tx}{\partial x}dt=\int_{0}^{1}tdt=\left.\frac{t^{2}}{2}\right|_{0}^{1}=\frac{1}{2}$ +\end_inset + +. + Izrek smo lahko uporabili, + ker je +\begin_inset Formula $xt$ +\end_inset + + zvezna na +\begin_inset Formula $\mathbb{R}\times\left[0,1\right]$ +\end_inset + + in zvezno parcialno odvedljiva po +\begin_inset Formula $x$ +\end_inset + + na tem območju. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Example +\begin_inset Formula +\[ +F\left(x\right)=\int_{0}^{1}e^{xt}dt\overset{\text{višje}}{=}\begin{cases} +\frac{e^{x}-1}{x} & ;x\not=0\\ +1 & ;x=0 +\end{cases}. +\] + +\end_inset + +Tudi +\begin_inset Formula $f\left(x,t\right)=e^{xt}$ +\end_inset + + je zvezna in zvezno parcialno odvedljiva po +\begin_inset Formula $x$ +\end_inset + + na +\begin_inset Formula $\mathbb{R}\times\left[0,1\right]$ +\end_inset + +; + lahko uporabimo izrek. + Preverimo, + da dobimo enak odvod kot direktno. + Naj bo +\begin_inset Formula $x\not=0$ +\end_inset + +. + +\begin_inset Formula +\[ +F'\left(x\right)\overset{\text{direktno}}{=}\left(\frac{e^{x}-1}{x}\right)'=\frac{e^{x}-1-xe^{x}}{x^{2}} +\] + +\end_inset + + +\begin_inset Formula +\[ +F'\left(x\right)\overset{\text{izrek}}{=}\int_{0}^{1}\frac{\partial}{\partial x}e^{xt}dt=\int_{0}^{1}te^{xt}dt=\cdots +\] + +\end_inset + +per partes: + +\begin_inset Formula $u=t$ +\end_inset + +, + +\begin_inset Formula $du=dt$ +\end_inset + +, + +\begin_inset Formula $v=\frac{e^{xt}}{x}$ +\end_inset + + +\begin_inset Formula +\[ +\cdots=t\left.\frac{e^{xt}}{x}\right|_{t=0}^{t=1}-\int_{0}^{1}\frac{e^{xt}}{x}dt=\frac{e^{x}}{x}-0-\left.\frac{e^{xt}}{x^{2}}\right|_{t=0}^{t=1}=\frac{e^{x}}{x}+\frac{e^{x}}{x^{2}}-\frac{1}{x^{2}}=\frac{e^{x}-1}{x} +\] + +\end_inset + + +\end_layout + +\begin_layout Theorem* +Izboljšana različica izreka +\begin_inset CommandInset ref +LatexCommand ref +reference "thm:odvedljivost" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + +. + Naj bosta +\begin_inset Formula $u,v:\left[a,b\right]\to\left[c,d\right]$ +\end_inset + +. + Naj bo +\begin_inset Formula $f$ +\end_inset + + taka, + kot v izreku +\begin_inset CommandInset ref +LatexCommand ref +reference "thm:odvedljivost" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + +. + Potem je odvedljiva tudi +\begin_inset Formula +\[ +F\left(x\right)=\int_{u\left(x\right)}^{v\left(x\right)}f\left(x,t\right)dt +\] + +\end_inset + + in za njen odvod velja +\begin_inset Formula +\[ +F'\left(x\right)=\int_{u\left(x\right)}^{v\left(x\right)}f_{x}\left(x,t\right)dt+v'\left(x\right)f\left(x,v\left(x\right)\right)-u'\left(x\right)f\left(x,u\left(x\right)\right) +\] + +\end_inset + + +\end_layout + +\begin_layout Standard +Tega izreka ne bomo dokazali. +\end_layout + +\begin_layout Remark* +Ta izrek je posplošitev/izboljšava osnovnega izreka analize: +\begin_inset Formula +\[ +\int_{a}^{x}f\left(t\right)dt\overset{\text{ta izrek}}{=}\int_{a}^{x}\cancelto{0}{f_{x}\left(t\right)}dt+\cancelto{1}{\left(x\right)'}f\left(x\right)-\cancelto{0}{\left(a\right)'}f\left(a\right)=f\left(x\right) +\] + +\end_inset + + +\end_layout + +\begin_layout Example* +Nekaj primerov. +\end_layout + +\begin_layout Enumerate +\begin_inset Formula +\[ +F\left(x\right)=\int_{0}^{x}tdt=\frac{x^{2}}{2} +\] + +\end_inset + + +\begin_inset Formula $F'\left(x\right)\overset{\text{direktno}}{=}x$ +\end_inset + +, + +\begin_inset Formula $F'\left(x\right)\overset{\text{izrek}}{=}\int_{0}^{x}\cancelto{0}{\frac{\partial t}{\partial x}}dt+\left(x\right)'x-\left(0'\right)\cdot0=x$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +\begin_inset Formula +\[ +\Erf\left(x\right)=\int_{0}^{x}e^{-t^{2}}dt +\] + +\end_inset + +Direktno ne znamo, + vemo pa, + da je po izreku odvod enak +\begin_inset Formula +\[ +F'\left(x\right)=\int_{0}^{x}\cancelto{0}{\frac{\partial e^{-t^{2}}}{\partial x}}dt-\cancelto{1}{\left(x\right)'}e^{-t^{2}}-\cancelto{0}{\left(0\right)'}e^{0}=e^{-x^{2}} +\] + +\end_inset + +To je primer neelementarne funkcije z elementarnim odvodom. +\end_layout + +\begin_layout Enumerate +\begin_inset Formula +\[ +F\left(x\right)=\int_{x^{2}}^{x}\frac{\sin\left(xt\right)}{t}dt +\] + +\end_inset + +je neelementarna, + toda +\begin_inset Formula +\[ +F'\left(x\right)=\int_{x^{2}}^{x}\frac{\partial}{\partial x}\frac{\sin\left(xt\right)}{t}dt+\left(x\right)'\frac{\sin x^{2}}{x}-2\left(x^{2}\right)'\frac{\sin x^{3}}{x^{2}}=\int_{x^{2}}^{x}\frac{\cos\left(xt\right)\cancel{t}}{\cancel{t}}dt+\frac{\sin x^{2}}{x}-2\frac{\cancel{x}\sin x^{3}}{x^{\cancel{2}}}= +\] + +\end_inset + + +\begin_inset Formula +\[ +=\left.\frac{\sin\left(xt\right)}{x}\right|_{t=x^{2}}^{t=x}+\frac{\sin x^{2}}{x}-\frac{\sin x^{3}}{x}=2\frac{\sin x^{2}}{x}-3\frac{\sin x^{3}}{x} +\] + +\end_inset + + +\end_layout + +\begin_layout Proof +Dokaz izreka +\begin_inset CommandInset ref +LatexCommand ref +reference "thm:integrabilnost" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + +. + Iz izreka +\begin_inset CommandInset ref +LatexCommand ref +reference "thm:zveznost" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + + vemo, + da je +\begin_inset Formula $F$ +\end_inset + + zvezna na +\begin_inset Formula $\left[a,b\right]$ +\end_inset + + in posledično tudi integrabilna. + Definirajmo dve zvezni funkciji +\begin_inset Formula $G\left(x\right)=\int_{a}^{x}F\left(s\right)ds$ +\end_inset + + in +\begin_inset Formula $H\left(x\right)=\int_{c}^{d}\left(\int_{a}^{x}f\left(s,t\right)ds\right)dt$ +\end_inset + +. + Želimo dokazati, + da je +\begin_inset Formula $G\left(b\right)=H\left(b\right)$ +\end_inset + +. + Strategija: + dokažemo enakost odvodov in konstantno odstopanje. \end_layout \end_body diff --git "a/\305\241ola/aps1/dn/.gitignore" "b/\305\241ola/aps1/dn/.gitignore" new file mode 100644 index 0000000..7986c25 --- /dev/null +++ "b/\305\241ola/aps1/dn/.gitignore" @@ -0,0 +1,7 @@ +*.zip +coverage_* +rešitev +resitev +test*.in +test*.res +test*.diff diff --git "a/\305\241ola/aps1/dn/autocomplete/re\305\241itev.cpp" "b/\305\241ola/aps1/dn/autocomplete/re\305\241itev.cpp" index 0a5f42c..f0c27f2 100644 --- "a/\305\241ola/aps1/dn/autocomplete/re\305\241itev.cpp" +++ "b/\305\241ola/aps1/dn/autocomplete/re\305\241itev.cpp" @@ -3,26 +3,31 @@ #include #include #include +bool debug = false; struct beseda { char * niz; long pomem; + long int idx; }; static int compar_words (const void * aa, const void * bb) { const char * a = ((const struct beseda *) aa)->niz; const char * b = ((const struct beseda *) bb)->niz; - fprintf(stderr, "compar_words: %s, %s\n", a, b); + if (debug) + fprintf(stderr, "compar_words: %s, %s\n", a, b); for (; *a && *b && *a == *b; a++, b++); if (*a < *b) return -1; return *a > *b; } -static int intlog(long n) { +static int intlog (long n) { int log = 1; for (int dolžina = 1; dolžina < n; dolžina *= 2) log++; return log; } int main () { + if (getenv("DEBUG")) + debug = true; long n; if (scanf("%ld", &n) == EOF) { perror("scanf n"); @@ -34,15 +39,17 @@ int main () { return 1; } for (long i = 0; i < n; i++) { + s[i].idx = i+1; if (scanf("%ms %ld", &(s[i].niz), &(s[i].pomem)) == EOF) { perror("scanf"); return 1; } } qsort(s, n, sizeof *s, compar_words); - for (long i = 0; i < n; i++) { - fprintf(stderr, "s[%ld].niz = \"%s\"; s[%ld].pomem = %ld;\n", i, s[i].niz, i, s[i].pomem); - } + if (debug) + for (long i = 0; i < n; i++) { + fprintf(stderr, "s[%ld].niz = \"%s\"; s[%ld].pomem = %ld;\n", i, s[i].niz, i, s[i].pomem); + } int log = intlog(n); // fprintf(stderr, "log: %d\n", log); long * max = (long *) malloc((n*log)*sizeof *max); @@ -70,74 +77,103 @@ int main () { } long * o = (long *) malloc(m*sizeof *o); for (long i = 0; i < m; i++) { - char buf[20000]; - char bu2[20000]; + char buf[200000]; + char bu2[200000]; struct beseda prefix = { .niz = buf, - .pomem = 0 + .pomem = 0, + .idx = 0 }; struct beseda nextprefix = { .niz = bu2, - .pomem = 0 + .pomem = 0, + .idx = 0 }; if (scanf("%s", buf) == EOF) { perror("scanf buf"); return 1; } - fprintf(stderr, "krneki: %s\n", buf); + if (debug) + fprintf(stderr, "krneki: %s\n", buf); strcpy(bu2, buf); nextprefix.niz[strlen(nextprefix.niz)-1]++; long l = 0, d = n; - while (l < d) { - long m = (l+d)/2; - switch (compar_words(&prefix, s+m)) { - case -1: - d = m-1; - break; - case 1: - l = m+1; - break; - case 0: - l = d = m; - break; - default: - assert(false); + if (compar_words(&prefix, s+n-1) > 0) + l = d = n; + else if (compar_words(&prefix, s) < 0) + l = d = 0; + else { + while (l < d) { + long m = (l+d)/2; + switch (compar_words(&prefix, s+m)) { + case -1: + d = m-1; + break; + case 1: + l = m+1; + break; + case 0: + l = d = m; + break; + default: + assert(false); + } } + if (strncmp(s[l].niz, prefix.niz, strlen(prefix.niz)) != 0) + l++; + assert(l<=n); } long start = l; - fprintf(stderr, "found start = %ld;\n", start); + if (debug) + fprintf(stderr, "found start = %ld;\n", start); l = 0, d = n; - while (l < d) { - long m = (l+d)/2; - switch (compar_words(&nextprefix, s+m)) { - case -1: - d = m-1; - break; - case 1: - l = m+1; - break; - case 0: - l = d = m; - break; - default: - assert(false); + if (compar_words(&nextprefix, s+n-1) > 0) + l = d = n; + else if (compar_words(&nextprefix, s) < 0) + l = d = 0; + else { + while (l < d) { + long m = (l+d)/2; + switch (compar_words(&nextprefix, s+m)) { + case -1: + d = m-1; + break; + case 1: + l = m+1; + break; + case 0: + l = d = m; + break; + default: + assert(false); + } + } + if (compar_words(&nextprefix, s+l) > 0) { + if (debug) + fprintf(stderr, "l++;\n"); + l++; } } long end = l; - fprintf(stderr, "found end = %ld;\n", end); - int winsizelog = intlog(end-start)-1; - o[i] = 0; - if (winsizelog) - o[i] = s[max[winsizelog*n+(end-(1 << (winsizelog-1)))]].pomem > s[max[winsizelog*n+start]].pomem ? max[winsizelog*n+start] : max[winsizelog*n+(end-(1 << (winsizelog-1)))]; - fprintf(stderr, "o[%ld] = %ld;\n", i, o[i]); + if (debug) + fprintf(stderr, "found end = %ld;\n", end); + if (end-start == 1) { + o[i] = start; + continue; + } + long winsizelog = intlog(end-start)-1; + o[i] = -1; + if (winsizelog) { + if (debug) + fprintf(stderr, "winsizelog: %ld, (1 << (winsizelog-1)): %ld, max[(winsizelog-1)*n+start]: %ld, max[(winsizelog-1)*n+(end-(1 << (winsizelog-1)))]: %ld\n", winsizelog, (1L << (winsizelog-1)), max[(winsizelog-1)*n+start], max[(winsizelog-1)*n+(end-(1 << (winsizelog-1)))]); + o[i] = s[max[(winsizelog-1)*n+(end-(1 << (winsizelog-1)))]].pomem > s[max[(winsizelog-1)*n+start]].pomem ? max[(winsizelog-1)*n+(end-(1 << (winsizelog-1)))] : max[(winsizelog-1)*n+start]; + } if (debug) + fprintf(stderr, "o[%ld] = %ld;\n", i, o[i]); } - bool devica = true; for (long i = 0; i < m; i++) { - if (devica) - devica = false; + if (o[i] >= 0) + printf("%ld\n", s[o[i]].idx); else - putchar(' '); - printf("%ld", o[i]); + printf("0\n"); } - putchar('\n'); } diff --git "a/\305\241ola/aps1/dn/druga/re\305\241itev.cpp" "b/\305\241ola/aps1/dn/druga/re\305\241itev.cpp" new file mode 100644 index 0000000..f9b7bf9 --- /dev/null +++ "b/\305\241ola/aps1/dn/druga/re\305\241itev.cpp" @@ -0,0 +1,75 @@ +// opomba: štiri vrstice kode, označene s komentarjem XXX, so bile dodane po prvi neuspeli oddaji. njihov doprinos je samoumeven. +#include +#include +#include +#include +using namespace std; +int main (void) { + int n, m; + cin >> n >> m; + vector>> sosedje; // sosedje[vozlišče] = [(vozlišče, utež),...] + sosedje.resize(n); + for (int i = 0; i < m; i++) { + int a, b, d; + cin >> a >> b >> d; + sosedje[a].push_back(make_pair(b, d)); + sosedje[b].push_back(make_pair(a, d)); + } + priority_queue> vrsta; // (-dolžina, vozlišče) + vector minimalna_dolžina; // minimalna_dolžina[vozlišče] + vector vir; // od kod smo prišli v to vozlišče + minimalna_dolžina.resize(n); + vir.resize(n); + for (int i = 0; i < n; i++) { + minimalna_dolžina[i] = numeric_limits::max(); + vir[i] = 0; + } + vrsta.push(make_pair(0, 0)); + while (!vrsta.empty()) { + pair vrhnja_trojka = vrsta.top(); + vrsta.pop(); + if (-vrhnja_trojka.first > minimalna_dolžina[vrhnja_trojka.second]) // XXX + continue; // XXX + for (auto sosed : sosedje[vrhnja_trojka.second]) { + int krajša_dolžina = -vrhnja_trojka.first+sosed.second; + if (minimalna_dolžina[sosed.first] > krajša_dolžina) { + minimalna_dolžina[sosed.first] = krajša_dolžina; + vir[sosed.first] = vrhnja_trojka.second; + vrsta.push(make_pair(-krajša_dolžina, sosed.first)); + } + } + } + if (minimalna_dolžina[n-1] == numeric_limits::max()) { + cout << -1 << endl; + return 0; + } + int druga = numeric_limits::max(); + for (int povezava = n-1; povezava; povezava = vir[povezava]) { // povezava je v bistvu {povezava, vir[povezava]}, dokler povezava != 0 (izhodiščno vozlišče) + for (int i = 0; i < n; i++) + minimalna_dolžina[i] = numeric_limits::max(); + vrsta.push(make_pair(0, 0)); + while (!vrsta.empty()) { + pair vrhnja_trojka = vrsta.top(); + vrsta.pop(); + if (-vrhnja_trojka.first > minimalna_dolžina[vrhnja_trojka.second]) // XXX + continue; // XXX + for (auto sosed : sosedje[vrhnja_trojka.second]) { + if ((vrhnja_trojka.second == povezava && sosed.first == vir[povezava]) || (vrhnja_trojka.second == vir[povezava] && sosed.first == povezava)) + continue; + int krajša_dolžina = -vrhnja_trojka.first+sosed.second; + if (minimalna_dolžina[sosed.first] > krajša_dolžina) { + minimalna_dolžina[sosed.first] = krajša_dolžina; + vrsta.push(make_pair(-krajša_dolžina, sosed.first)); + } + } + } + if (minimalna_dolžina[n-1] < druga) + druga = minimalna_dolžina[n-1]; + } + if (druga == numeric_limits::max()) { + cout << -1 << endl; + return 0; + } + cout << druga << endl; + return 0; +} diff --git "a/\305\241ola/aps1/dn/druga/test.cpp" "b/\305\241ola/aps1/dn/druga/test.cpp" new file mode 100644 index 0000000..91f79b6 --- /dev/null +++ "b/\305\241ola/aps1/dn/druga/test.cpp" @@ -0,0 +1,10 @@ +#include +#include +using namespace std; +int main (void) { + priority_queue, greater> q; + q.push(2); + q.push(1); + cout << q.top(); + return 0; +} diff --git "a/\305\241ola/aps1/dn/funkcije/nova.cpp" "b/\305\241ola/aps1/dn/funkcije/nova.cpp" new file mode 100644 index 0000000..fc8f196 --- /dev/null +++ "b/\305\241ola/aps1/dn/funkcije/nova.cpp" @@ -0,0 +1,52 @@ +#include +#include +#include +#include +#include +long long fja (long x, long double a) { + return x*powl(logl(x)/logl(2), a); +} +long long inverz (long long y, long long a, long long b, long double potenca) { + if (y > f(b, potenca)) + return LLONG_MAX; + if (y < f(a, potenca)) + return LLONG_MIN; + if (a == b) + return a; + long long pivot = (a+b)/2; + if (y > fja(pivot, potenca)) + return inverz(y, pivot+1, b, potenca); + return inverz(y, a, pivot-1, potenca); +} +long long manjših_od (long long y, const long * a, const long * b, int n) { + long long r = 0; + for (int i = 0; i < N; i++) { + long long x = inverz(y, a[i], b[i], (long double) (i+1)/n); + if (x == LLONG_MAX) + r += b[i]-a[i]+1; + else if (x != LLONG_MIN) + r += x-a[i]+1; + } + return r; +} +int main (void) { + int n + long long k; + scanf("%d %lld\n", &n, &k); + long * a = (long *) malloc(n*sizeof*a); + long * b = (long *) malloc(n*sizeof*b); + free(a); + free(b); + long long l = 0; + long long d = 0; + for (int i = 0; i < n; i++) { + scanf("%ld %ld\n", a+i, b+i); + if (fja(b[i], (long double) (i+1) / n) > d) + d = fja(b[i], (long double) (i+1) / n); + } + while (1) { + long long pivot = (l+d)/2; + long long levo = manjših_od(pivot, a, b, n); + if (levo == k) + } +} diff --git "a/\305\241ola/aps1/dn/funkcije/re\305\241itev.cpp" "b/\305\241ola/aps1/dn/funkcije/re\305\241itev.cpp" new file mode 100644 index 0000000..ac669b7 --- /dev/null +++ "b/\305\241ola/aps1/dn/funkcije/re\305\241itev.cpp" @@ -0,0 +1,105 @@ +// Pomembno obvestilo za ocenjevalca: To domačo nalogo sem rešil, ko sem študiral v 1. letniku FRI in nisem poznal pravil predmeta APS1 glede plagiatorstva in javne objave domačih nalog. Svojo sicer ne povsem pravilno rešitev sem namreč takrat javno objavil. Upam, da me ne boste kaznovali, če se zgodi, da bo še kdo oddal podobno rešitev, ker je na spletu našel mojo javno objavljeno idejo rešitve izpred enega leta. +#include +#include +#include +#include +#define LD long double +LD inverz (int smer, LD y, void * ctxt, LD (* f)(LD, void *), LD a, LD b, LD epsilon) { // za strogo NARAŠČAJOČE funkcije je smer 1, za strogo PADAJOČE je smer -1. iščemo x za funkcijsko vrednost y na intervalu (a,b). ustrezen x je tak, da v epsilonski okolici dejanskega f^-1(y). + if (smer == 1) { + if (y > f(b, ctxt)) + return INFINITY; + if (y < f(a, ctxt)) + return -INFINITY; + } else { + if (y > f(a, ctxt)) + return -INFINITY; + if (y < f(b, ctxt)) + return INFINITY; + } + LD x = (a+b)/2; + if (b-a < epsilon) + return x; + LD v = f(x, ctxt); + if (y > v) { + if (smer == 1) + return inverz(smer, y, ctxt, f, x, b, epsilon); + return inverz(smer, y, ctxt, f, a, x, epsilon); + } + if (smer == 1) + return inverz(smer, y, ctxt, f, a, x, epsilon); + return inverz(smer, y, ctxt, f, x, b, epsilon); +} +LD fja (LD x, void * atype) { + LD a = *((LD *) atype); + return x*powl(logl(x)/logl(2), a); +} +int levo_od (LD y, const long long * a, const long long * b, LD * inverzi, int N) { + int r = 0; + for (int i = 0; i < N; i++) { + LD potenca = ((LD) i+1)/N; + inverzi[i] = inverz(1, y, &potenca, fja, a[i], b[i], 0.01); + fprintf(stderr, "\tlevo_od: %d\t%Lf\n", i, inverzi[i]); + if (inverzi[i] == INFINITY) + r += b[i]-a[i]+1; + else if (inverzi[i] == -INFINITY) + ; + else + r += ceill(inverzi[i])-a[i]; + } + return r; +} +int main (void) { + char buf[512]; + fgets(buf, sizeof buf, stdin); + char * c; + int N = strtol(buf, &c, 10); + long long k = strtol(++c, NULL, 10); + long long * a = (long long *) malloc(N*sizeof *a); + long long * b = (long long *) malloc(N*sizeof *b); + LD * inverzi = (LD *) malloc(N*sizeof *inverzi); + assert(a && b && inverzi); + LD l = 0; + LD d = 0; + for (int i = 0; i < N; i++) { + fgets(buf, sizeof buf, stdin); + a[i] = strtol(buf, &c, 10); + b[i] = strtol(++c, NULL, 10); + LD potenca = ((LD) i+1)/N; + if (fja(b[i], &potenca) > d) { + fprintf(stderr, "new max=%Lf for d at i=%d\n", fja(b[i], &potenca), i); + d = fja(b[i], &potenca); + } + } + /// debug vvvvv + LD potenca = ((LD) 2/4); + fprintf(stderr, "DEBUG: %Lf\n", fja(1000000000, &potenca)); + /// debug ^^^^^ + fprintf(stderr, "l=%Lf, d=%Lf, k=%lld, N=%d\n", l, d, k, N); + while (1) { + LD pivot = (l+d)/2; + long long levo = levo_od(pivot, a, b, inverzi, N); + fprintf(stderr, "pivot = %Lf\tlevo = %lld\tl=%Lf\td=%Lf\n", pivot, levo, l, d); + if (levo == k) { + fprintf(stderr, "NAŠEL FUNKCIJSKO VREDNOST pri K, ki je %Lf.\n", pivot); + LD best = NAN; + for (int i = 0; i < N; i++) { + LD potenca = ((LD) i+1)/N; + LD v = floorl(fja(floorl(inverzi[i]), &potenca)); + if (v > pivot) + continue; + if (isnan(best) || pivot-v < pivot-best) + best = v; + fprintf(stderr, "bestsearch: i=%d, v=%Lf\n", i, v); + } + printf("%lld\n", (long long) best); + break; + } + if (levo < k) + l = pivot; + else + d = pivot; + } + free(a); + free(b); + free(inverzi); +} diff --git "a/\305\241ola/aps1/dn/neboti\304\215niki/in.txt" "b/\305\241ola/aps1/dn/neboti\304\215niki/in.txt" new file mode 100644 index 0000000..0720d3e --- /dev/null +++ "b/\305\241ola/aps1/dn/neboti\304\215niki/in.txt" @@ -0,0 +1,6 @@ +5 +7 +4 +2 +4 +5 diff --git "a/\305\241ola/aps1/dn/neboti\304\215niki/nova.cpp" "b/\305\241ola/aps1/dn/neboti\304\215niki/nova.cpp" new file mode 100644 index 0000000..fcd5781 --- /dev/null +++ "b/\305\241ola/aps1/dn/neboti\304\215niki/nova.cpp" @@ -0,0 +1,28 @@ +#include +#include +long vidi (long n, long * h, long * s) { + long r = 0; + long * top = s; + for (long i = 0; i < n; i++) { + while (top > s && h[top[-1]] <= h[i]) + top--; + if (top == s) + r += i; + else + r += i -top[-1] -1; + *(top++) = i; + } + return r; +} +int main (void) { + long n; + scanf("%ld", &n); + long * h = (long *) malloc(n*sizeof *h); + long * h_reversed = (long *) malloc(n*sizeof *h_reversed); + long * stack = (long *) malloc(n*sizeof *stack); + for (long i = 0; i < n; i++) { + scanf("%ld", h+i); + h_reversed[n-i-1] = h[i]; + } + printf("%ld\n", vidi(n, h, stack) + vidi(n, h_reversed, stack)); +} diff --git "a/\305\241ola/aps1/dn/neboti\304\215niki/resitev.cpp" "b/\305\241ola/aps1/dn/neboti\304\215niki/resitev.cpp" new file mode 100644 index 0000000..f7eb198 --- /dev/null +++ "b/\305\241ola/aps1/dn/neboti\304\215niki/resitev.cpp" @@ -0,0 +1,19 @@ +#include +#include +long * jebeš_c_idiote_zakaj_qsort_r_ni_standarden; +int compar_long (const void * a, const void * b) { + if (jebeš_c_idiote_zakaj_qsort_r_ni_standarden[*(long *) a] < jebeš_c_idiote_zakaj_qsort_r_ni_standarden[*(long *) b]) + return -1; + return jebeš_c_idiote_zakaj_qsort_r_ni_standarden[*(long *) a] > jebeš_c_idiote_zakaj_qsort_r_ni_standarden[*(long *) b]; +} +int main (void) { + long N; + scanf("%d", N); + long * h = (long *) malloc(N*sizeof *h); + long * p = (long *) malloc(N*sizeof *h); + jebeš_c_idiote_zakaj_qsort_r_ni_standarden = h; + for (long i = 0; i < N; i++) + scanf("%d", h[(p[i] = i)]); + qsort(h, N, sizeof *h, compar); + +} diff --git "a/\305\241ola/aps1/dn/osvetlitev/geninput.py" "b/\305\241ola/aps1/dn/osvetlitev/geninput.py" new file mode 100755 index 0000000..d2b95bb --- /dev/null +++ "b/\305\241ola/aps1/dn/osvetlitev/geninput.py" @@ -0,0 +1,13 @@ +#!/usr/bin/python3 +import sys +import random +r = random.Random() +if len(sys.argv) > 1: + r.seed(sys.argv[1]) +M = r.randint(1, 1000000000) +print(M) +N = r.randint(1, 10000) +print(N) +for i in range(N): + print(r.randint(0, M), end=" ") + print(r.randint(0, 1000000000)) diff --git "a/\305\241ola/aps1/dn/otoki/nova.cpp" "b/\305\241ola/aps1/dn/otoki/nova.cpp" new file mode 100644 index 0000000..ba88a05 --- /dev/null +++ "b/\305\241ola/aps1/dn/otoki/nova.cpp" @@ -0,0 +1,82 @@ +#include +#include +#include +using namespace std; +int main (void) { + int v, s; + cin >> v >> s; + vector p; + p.resize(v*s); + priority_queue> q; + int m = 0; + for (int i = 0; i < v; i++) + for (int j = 0; j < s; j++) { + p[i*s+j] = -1; + int r; + cin >> r; + if (!r) + continue; + q.push(make_pair(r, i*s+j)); + if (r > m) + m = r; + } + int otokov = 0; + vector o; + o.resize(m+1); + int višina = m; + // cerr << "višina: " << višina << endl; + o[m] = 0; + while (!q.empty()) { + auto vrh = q.top(); + q.pop(); + // cerr << "popped: " << vrh.first << " " << vrh.second << endl; + if (višina != vrh.first) { + for (int i = višina-1; i >= vrh.first; i--) + o[i] = otokov; + višina = vrh.first; + } + vector sosedje; + if (vrh.second % s != s-1 && p[vrh.second+1] != -1) + sosedje.push_back(vrh.second+1); + if (vrh.second % s != 0 && p[vrh.second-1] != -1) + sosedje.push_back(vrh.second-1); + if (vrh.second >= s && p[vrh.second-s] != -1) + sosedje.push_back(vrh.second-s); + if (vrh.second+s < v*s && p[vrh.second+s] != -1) + sosedje.push_back(vrh.second+s); + if (!sosedje.size()) { + p[vrh.second] = -2; + otokov++; + continue; + } + int maxglobina = -1; + int maxglobinapredstavnik; + for (unsigned i = 0; i < sosedje.size(); i++) { + int globinadrevesa = 0; + int predstavnik = sosedje[i]; + while (p[predstavnik] >= 0) { + predstavnik = p[predstavnik]; + globinadrevesa++; + } + if (globinadrevesa > maxglobina) { + maxglobina = globinadrevesa; + maxglobinapredstavnik = predstavnik; + } + } + p[vrh.second] = maxglobinapredstavnik; + for (unsigned i = 0; i < sosedje.size(); i++) { + int predstavnik = sosedje[i]; + while (p[predstavnik] >= 0) + predstavnik = p[predstavnik]; + if (predstavnik != maxglobinapredstavnik) { + p[predstavnik] = maxglobinapredstavnik; + otokov--; + } + } + } + for (int i = višina-1; i >= 0; i--) + o[i] = otokov; + for (int i = 0; i <= m; i++) + cout << o[i] << endl; + return 0; +} diff --git "a/\305\241ola/aps1/dn/otoki/re\305\241itev.cpp" "b/\305\241ola/aps1/dn/otoki/re\305\241itev.cpp" new file mode 100644 index 0000000..ba88a05 --- /dev/null +++ "b/\305\241ola/aps1/dn/otoki/re\305\241itev.cpp" @@ -0,0 +1,82 @@ +#include +#include +#include +using namespace std; +int main (void) { + int v, s; + cin >> v >> s; + vector p; + p.resize(v*s); + priority_queue> q; + int m = 0; + for (int i = 0; i < v; i++) + for (int j = 0; j < s; j++) { + p[i*s+j] = -1; + int r; + cin >> r; + if (!r) + continue; + q.push(make_pair(r, i*s+j)); + if (r > m) + m = r; + } + int otokov = 0; + vector o; + o.resize(m+1); + int višina = m; + // cerr << "višina: " << višina << endl; + o[m] = 0; + while (!q.empty()) { + auto vrh = q.top(); + q.pop(); + // cerr << "popped: " << vrh.first << " " << vrh.second << endl; + if (višina != vrh.first) { + for (int i = višina-1; i >= vrh.first; i--) + o[i] = otokov; + višina = vrh.first; + } + vector sosedje; + if (vrh.second % s != s-1 && p[vrh.second+1] != -1) + sosedje.push_back(vrh.second+1); + if (vrh.second % s != 0 && p[vrh.second-1] != -1) + sosedje.push_back(vrh.second-1); + if (vrh.second >= s && p[vrh.second-s] != -1) + sosedje.push_back(vrh.second-s); + if (vrh.second+s < v*s && p[vrh.second+s] != -1) + sosedje.push_back(vrh.second+s); + if (!sosedje.size()) { + p[vrh.second] = -2; + otokov++; + continue; + } + int maxglobina = -1; + int maxglobinapredstavnik; + for (unsigned i = 0; i < sosedje.size(); i++) { + int globinadrevesa = 0; + int predstavnik = sosedje[i]; + while (p[predstavnik] >= 0) { + predstavnik = p[predstavnik]; + globinadrevesa++; + } + if (globinadrevesa > maxglobina) { + maxglobina = globinadrevesa; + maxglobinapredstavnik = predstavnik; + } + } + p[vrh.second] = maxglobinapredstavnik; + for (unsigned i = 0; i < sosedje.size(); i++) { + int predstavnik = sosedje[i]; + while (p[predstavnik] >= 0) + predstavnik = p[predstavnik]; + if (predstavnik != maxglobinapredstavnik) { + p[predstavnik] = maxglobinapredstavnik; + otokov--; + } + } + } + for (int i = višina-1; i >= 0; i--) + o[i] = otokov; + for (int i = 0; i <= m; i++) + cout << o[i] << endl; + return 0; +} diff --git "a/\305\241ola/aps1/dn/razporeditev/re\305\241itev.cpp" "b/\305\241ola/aps1/dn/razporeditev/re\305\241itev.cpp" new file mode 100644 index 0000000..a555440 --- /dev/null +++ "b/\305\241ola/aps1/dn/razporeditev/re\305\241itev.cpp" @@ -0,0 +1,63 @@ +#include +#include +#include +#include +struct otrok { + bool skupina; + bool določeno; + struct otrok ** povezave; + long povezave_sizeof; + long povezave_length; +}; +int main (void) { + long n, m; // št. otrok in št. klepetavih parov + scanf("%ld %ld\n", &n, &m); + struct otrok * otroci = (struct otrok *) calloc(n, sizeof *otroci); + assert(otroci); + for (long i = 0; i < n; i++) + assert((otroci[i].povezave = (struct otrok **) malloc((otroci[i].povezave_sizeof = 1)*sizeof *(otroci[i].povezave)))); + for (long i = 0; i < m; i++) { + int a, b; + scanf("%d %d\n", &a, &b); + a--; b--; // kaj ko bi začeli šteti z 0? ZAKAJ PA NE ZAČNEMO ŠTETI Z -1 ?=!?!?! + if (otroci[a].povezave_sizeof <= otroci[a].povezave_length) + assert((otroci[a].povezave = (struct otrok **) reallocarray(otroci[a].povezave, (otroci[a].povezave_sizeof *= 2), sizeof *(otroci[a].povezave)))); + if (otroci[b].povezave_sizeof <= otroci[b].povezave_length) + assert((otroci[b].povezave = (struct otrok **) reallocarray(otroci[b].povezave, (otroci[b].povezave_sizeof *= 2), sizeof *(otroci[b].povezave)))); + otroci[a].povezave[otroci[a].povezave_length++] = otroci+b; + otroci[b].povezave[otroci[b].povezave_length++] = otroci+a; + } + struct otrok ** za_obdelati = (struct otrok **) malloc(n*sizeof*za_obdelati); + assert(za_obdelati); + long za_obdelati_length = 0; + for (long i = 0; i < n; i++) { + if (!otroci[i].določeno) { // prvi v komponenti dobi nižjo skupino + otroci[i].skupina = 0; + otroci[i].določeno = true; + za_obdelati[za_obdelati_length++] = otroci+i; + } + while (za_obdelati_length) { + struct otrok * obdelujem = za_obdelati[--za_obdelati_length]; + for (long j = 0; j < obdelujem->povezave_length; j++) { + if (obdelujem->povezave[j]->določeno) { + if (obdelujem->povezave[j]->skupina == obdelujem->skupina) { + printf("-1\n"); + goto e; + } + continue; + } + obdelujem->povezave[j]->skupina = !obdelujem->skupina; + obdelujem->povezave[j]->določeno = true; + za_obdelati[za_obdelati_length++] = obdelujem->povezave[j]; + } + } + } + for (long i = 0; i < n; i++) + printf("%ld\n", ((long) (otroci[i].skupina)) + 1); +e: + for (long i = 0; i < n; i++) + free(otroci[i].povezave); // make asan happy + free(za_obdelati); + free(otroci); + return 0; +} diff --git "a/\305\241ola/aps1/dn/vre\304\215a/re\305\241itev.cpp" "b/\305\241ola/aps1/dn/vre\304\215a/re\305\241itev.cpp" new file mode 100644 index 0000000..8590737 --- /dev/null +++ "b/\305\241ola/aps1/dn/vre\304\215a/re\305\241itev.cpp" @@ -0,0 +1,61 @@ +#include +#include +#include +#include +static bool debug; +static long long delna_vsota (long * vreča, long bis, int exp) { + long long r = 0; + long last = 0; + for (long i = 0; i <= exp; i++) { + if (last + (1 << (exp-i)) <= bis) { + long idx = (1 << i)-1 + ((last) >> (exp-i)); + r += vreča[idx]; + if (debug) + fprintf(stderr, "i=%ld\tlast=%ld\tidx=%ld\tr=%lld\n", i, last, idx, r); + last += (1 << (exp-i)); + } + } + if (debug) + fprintf(stderr, "delna vsota prvih %ld je %lld\n", bis, r); + return r; +} +static void print_vreča (long * vreča, int exp) { + for (int i = 0; i <= exp; i++) { + for (int j = 0; j < (1 << i); j++) + fprintf(stderr, "% *ld", 2*(1 << (exp-i)), vreča[(1 << i)-1+j]); + fprintf(stderr, "\n"); + } +} +int main (void) { + long n; + debug = getenv("DEBUG"); + int exp = atoi(getenv("EXP") ? getenv("EXP") : "20"); // [0, 2**exp] so možna števila v vreči + scanf("%ld", &n); + long * vreča = (long *) calloc(1L << (exp+1), sizeof *vreča); + long long r = 0; + for (long i = 0; i < n; i++) { + if (debug) + print_vreča(vreča, exp); + long s, x; + scanf("%ld %ld", &s, &x); + if (s <= 0) { // dodamo x v vrečo za s < 0, odstranimo za s == 0 + if (debug) + fprintf(stderr, "%s %ld\n", s ? "vstavljam" : "odstranjujem", x); + if (!s && !vreča[(1 << exp)-1+x]) { + if (debug) + fprintf(stderr, "preskakujem odstranjevanje, saj števila ni v vreči\n"); + continue; + } + for (long i = 0; i <= exp; i++) + vreča[(1 << i)-1+(x >> (exp-i))] += s ? 1 : -1; + } else { // poizvedba na intervalu + long a = MIN(s, x); + long b = MAX(s, x); + long long odgovor = delna_vsota(vreča, b+1, exp)-delna_vsota(vreča, a, exp); + if (debug) + fprintf(stderr, "odgovor na poizvedbo [%ld, %ld]: %lld\n", a, b, odgovor); + r += odgovor; + } + } + printf("%lld\n", r); +} diff --git "a/\305\241ola/aps1/dn/vzorec/re\305\241itev.cpp" "b/\305\241ola/aps1/dn/vzorec/re\305\241itev.cpp" new file mode 100644 index 0000000..63c8f6a --- /dev/null +++ "b/\305\241ola/aps1/dn/vzorec/re\305\241itev.cpp" @@ -0,0 +1,94 @@ +#include +#include +#include +#include +#include +#include +int main () { + char vzorec[2048]; + int dpa[2048]; + int dpb[2048]; + int * dp = dpa; + int * odp = dpb; + int n, r, vzl; + int debug = getenv("DEBUG") ? 1 : 0; + scanf("%d\n", &n); + for (int i = 0; i < n; i++) { + char * w = vzorec; + *w++ = '*'; + char prvi = 0; + while ((*w++ = getchar()) != ' ') { + if (!prvi) + prvi = w[-1]; + if (w[-1] == '*' && w[-2] == '*') + w--; + if (w-vzorec > 2001) { + if (debug) + fprintf(stderr, "vzorec je daljši od 2001\n"); + printf("-1\n"); + while (getchar() != '\n'); + goto end; + } + }; + *--w = '\0'; + vzl = strlen(vzorec); + if (debug) { + fprintf(stderr, " "); + for (int j = 0; j < vzl; j++) + fprintf(stderr, " %c", vzorec[j]); + fprintf(stderr, "\n"); + } + if (vzorec[0] == '*' && vzl == 1) { + printf("0 0\n"); + r = 'x'; + goto slurp; + } + dp = dpa; + odp = dpb; + for (int j = 0; j < vzl; j++) + dpb[j] = j ? 0 : 1; + r = getchar(); + for (int j = 0; r != '\n'; r = getchar(), j++) { + memset(dp, 0, vzl*sizeof *dp); + if (prvi == '*') + dp[0] = j+2; + else + dp[0] = 1; + for (int k = 1; k < vzl; k++) { + if (k && (vzorec[k] == '?' || vzorec[k] == r)) + if (odp[k-1]) + dp[k] = odp[k-1]+1; + if (vzorec[k] == '*') { + dp[k] = k ? dp[k-1] : 0; + if (odp[k]) { + if (!dp[k]) + dp[k] = odp[k]+1; + else + dp[k] = MAX(odp[k]+1, dp[k]); + } + } + } + if (debug) { + fprintf(stderr, "%c: ", r); + for (int k = 0; k < vzl; k++) + fprintf(stderr, "% 3d", dp[k]); + fprintf(stderr, "\n"); + } + if (dp[vzl-1]) { + printf("%d %d\n", j-dp[vzl-1]+2, j); + goto slurp; + } + if (dp == dpa) { + dp = dpb; + odp = dpa; + } else { + dp = dpa; + odp = dpb; + } + } + printf("-1\n"); +slurp: + while (r != '\n' && getchar() != '\n'); +end:; + } +} diff --git "a/\305\241ola/aps1/dn/vzorec/stara.cpp" "b/\305\241ola/aps1/dn/vzorec/stara.cpp" new file mode 100644 index 0000000..829e72d --- /dev/null +++ "b/\305\241ola/aps1/dn/vzorec/stara.cpp" @@ -0,0 +1,76 @@ +#include +#include +#include +#include +#include +#include +int main () { + char * vzorec = (char *) malloc(4096L*4096); + assert(vzorec); + char ** stanja = (char **) malloc(4096L*4096*sizeof *stanja); + assert(stanja); + int * začetki = (int *) malloc(4096L*4096*sizeof *začetki); + assert(začetki); + int stanja_length; + int n; + int prebranih; + int debug = getenv("DEBUG") ? 1 : 0; + scanf("%d\n", &n); + for (int i = 0; i < n; i++) { + char * w = vzorec; + while ((*w++ = getchar()) != ' ') { + if (w != vzorec+1 && w[-1] == '*' && w[-2] == '*') + w--; + if (w-vzorec > 2001) { + if (debug) + fprintf(stderr, "vzorec je daljši od 2001\n"); + printf("-1\n"); + while (getchar() != '\n'); + goto end; + } + }; + *--w = '\0'; + stanja_length = 0; + prebranih = 0; + if (debug) + fprintf(stderr, "vzorec: %s\n", vzorec); + while (1) { + char r = getchar(); + prebranih++; + stanja[stanja_length] = vzorec; + začetki[stanja_length++] = prebranih-1; + for (int j = 0; j < stanja_length; j++) { + if (debug) + fprintf(stderr, "prebranih=%d, j=%d, *stanja[j]=%c (0x%x), r=%c\n", prebranih, j, *stanja[j], *stanja[j], r); + if (*stanja[j] == '*') { + stanja[stanja_length] = stanja[j]+1; + začetki[stanja_length++] = začetki[j]; + } else if (*stanja[j] == '?') { + stanja[j]++; + } else if (*stanja[j] == '\0') { + printf("%d %d\n", začetki[j], MAX(0, prebranih-2)); + while (r != '\n' && getchar() != '\n'); + goto end; + } else if (*stanja[j] == r) { + stanja[j]++; + } else { + if (j == stanja_length-1) { + stanja_length--; + break; + } + stanja[j] = stanja[--stanja_length]; + začetki[j] = začetki[stanja_length]; + j--; // obdelaj sedaj to stanje ki smo ga prestavili + continue; + } + } + if (r == '\n') { + if (debug) + fprintf(stderr, "prišel do konca vhodnega niza\n"); + printf("-1\n"); + goto end; + } + } +end:; + } +} -- cgit v1.2.3