Na tomto mieste by sme vám radi povedali niekoľko slov o tom, ako si predstavujeme popis ideálneho riešenia. Ako má vyzerať odovzdaný program sa môžete dočítať na samostatnej stránke.
Nechceme, aby ste nám zbytočne popisovali manipuláciu so vstupom a výstupom. Samozrejme, zakazovať vám to nebudeme, ale bodíky navyše za to nedostanete a ešte môžete znechutiť opravovateľa, ktorý musí čítať množstvo textu nesúvisiaceho s riešením samotnej úlohy. Vo svojom riešení sa nemusíte zaoberať kontrolovaním správnosti vstupných údajov.
Pod pojmom popis algoritmu nerozumieme preloženie programu z Pascalu, prípadne C-čka do slovenčiny. Popis by mal zhruba obsahovať:
- Popis myšlienky, na ktorej je založený algoritmus (bez detailov ako sú názvy premenných, procedúr...). Z popisu by malo byť jasné, ako úlohu riešime.
- Popis dátových štruktúr. Čo si vlastne chceme počas výpočtu pamätať a aké štruktúry sú na to vhodné.
- Popis algoritmu. Tu môžeme využívať už popísané dátové štruktúry a spomenúť dôležité procedúry a funkcie, ako aj najdôležitejšie premenné.
- Zdôvodnenie správnosti. Nemusí to byť formálne presný ani detailný dôkaz, avšak mal by obsahovať argumenty zdôvodňujúce každý dôležitý aspekt programu, ktorý nie je na prvý pohľad zrejmý. Sem zaradíme aj dôkaz konečnosti v tých prípadoch, keď nie je zrejmé, že sa program (resp. niektorá operácia, ktorú vykonáva) nezacyklí.
- Na koniec príde odhad časovej a pamäťovej zložitosti programu.
Takáto štruktúra popisu nie je univerzálna. Niektoré časti možno vynechať, niektoré zlúčiť, prípadne nejaké pridať. Poradie by však malo byť zhruba zachované.
Jedna dobrá rada: Riešenie si po sebe aspoň raz prečítajte. Uistíte sa tak, že ste napísali presne to, čo ste chceli a že text je zrozumiteľný a čitateľný. Navyše sa vďaka tomu viete vyhúť chybám.
Niekoľko slov o odhade zložitosti
Pod odhadom časovej zložitosti rozumieme odhad času, ktorý bude program trvať, v závislosti od vstupných premenných. Tento čas je priamo úmerný počtu elementárnych operácií, ktoré program vykonáva - priradenie jednoduchej premennej, porovnanie jednoduchých premenných, aritmetické operácie, atď. Väčšinou sa zaujímame o to, ako dlho beží program v priemernom, alebo najhoršom prípade (čiže si všímame priemerný, alebo maximálny čas vykonávania programu). Analogicky odhad pamäťovej zložitosti je odhad veľkosti použitej pamäti v bajtoch v závislosti od vstupných premenných.
Väčšinou nás nezaujímajú presné hodnoty (niekto má rýchlejší počítač, na niektorých počítačoch má integer 2 a na iných 4 bajty a pod.), preto používame tzv. \(O\)-notáciu. Hovoríme, že funkcia \(f(n)\) (napr. čas behu programu v milisekundách v závislosti od veľkosti vstupu \(n\)) je \(O(g(n))\) (\(g(n)\) je tiež funkcia), ak existuje taká konštanta \(c\), že pre všetky dostatočne veľké \(n~(n>n_0)\) je \(f(n) \leq c \cdot g(n)\).
Napríklad, ak program pre vstup veľkosti \(n\) nebeží nikdy viac ako \(T(n)=\frac{1}{2}n^3 + 5n\log(n) + 83\) mikrosekúnd, môžeme povedať, že má časovú zložitosť \(O(n^3)\). Ak program potrebuje najviac \(M(n) = 3n\log_2(n) + 150n + 15\) bajtov pamäti, povieme, že má pamäťovú zložitosť \(O(n\log(n))\). (Poznamenávame, že ak je nejaká funkcia \(O(n^2)\), tak je aj \(O(n^3)\)) atď. Vždy sa však snažíme nájsť čo najmenšie horné ohraničenie, t.j. funkciu, ktorá čo najpomalšie rastie.)
Ukážky
A ešte jedno upozornenie pre vás -- riešiteľov: uvedením nepostačujúceho popisu prípadne jeho vynechaním riskujete, že opravovateľ vaše riešenie napriek snahe nepochopí a nedostanete žiadne body.
Na doplnenie horeuvedných (pre niekoho možno príliš nekonkrétnych) rečí o tom, ako si predstavujeme ideálne riešenie, pripájame dva kompletné príklady z KSP aj s ich vzorovými riešeniami. Na týchto vzorových riešeniach jasne vidno, čo chápeme pod slovami popis, program a odhad časovej zložitosti. Nech vám teda tieto vzorové riešenia slúžia ako svetlý vzor pre písanie vlastných riešení :-) (P.S. K popisu. Ak si niekto myslí, že popis je nepodstatný, skúste si vytlačiť len listing druhého programu a zistiť, čo tým autor myslel.)
Vzorový príklad #1
Tento príklad je z KSP-Z 19. ročník, 1. kolo, 4. Zhrdzavené potrubie
Zadanie
"Zase ďalšia diera!", v duchu si povedal Zápla, dvorný opravár Zimbabwejského kráľovstva. Za tých - 1, 2, 3,... no proste veľa - rokov svojej služby videl už mnoho hrdzavých potrubí. Zvyčajne bola diera len jedna, a preto nebol problém, čo s ňou - jednoducho ju Zápla zaplátal záplatou. Z ničoho nič ho dnes ráno zavolali k veľkej havárii na hlavnom vodovodnom potrubí, ktoré dopravuje vodu z jazera Kariba (16° 53' S, 28° 1' E) do hlavného mesta, Harare (17° 50' S, 31° 3' E). Z asi dvadsiatich miest potrubia striekala voda cez prehrdzavené steny hrubej rúry. Záplaty na také veľké potrubie sú drahé (záplaty sa dnes už nevyrábajú zo železa, ktoré ľahko a rýchlo hrdzavie, ale z prefíkanej umelej hmoty, ktorá určite prežije celé pôvodné potrubie), a preto si Zápla musí dobre rozmyslieť, ako ich na diery poukladať.
Úloha
Záplaty sú už z továrne narezané na metrové kúsky a nedajú sa už na mieste rezať na menšie. Zhrdzavený kúsok potrubia, teda diera, je zanedbateľne malá; ak položíme záplatu jej krajom na dieru, bude táto diera zaplátaná. Záplat môžeme dať aj viac na seba.(záplaty z prefíkanej umelej hmoty sú dostatočne tenké, takže to nebude ničomu vadiť) Zhrdzavené miesta (nech je ich \(n\)) sú určené ich polohou na potrubí, a keďže sú veľmi malé, budeme ich uvažovať len ako body na priamke a ich poloha bude udaná vzdialenosťou od začiatku potrubia (v metroch); môžete predpokladať, že pozície všetkých dier sú na vstupe utriedené podľa vzdialenosti od začiatku potrubia.
Zápla je už mierne nervózny, voda stále strieka a on vás žiada o radu, ako má záplaty na potrubie dávať, aby ich musel čo najmenej použiť.
Formát vstupu
Na prvom riadku je číslo \(n\) - počet dier. Na druhom riadku je \(n\) čísel - pozície dier.
Formát vstupu
Pre každú použitú záplatu vypíšte jeden riadok, obsahujúci jedno číslo - pozíciu začiatku záplaty.
Vstup
3
1 3 3.5
Výstup
0.5
2.75Vzorové riešenie
Kvôli ľahšiemu vyjadrovaniu si predstavme, že potrubie ide zľava doprava. Ľahko si všimneme, že najľavejšiu záplatu môžeme položiť od najľavejšej diery. Viac vpravo najľavejšiu záplatu dať nemôžeme, inak by sme nezakryli najľavejšiu dieru. Ak by zase ležala viac vľavo, tak posunutím doprava do vyššie spomenutej polohy nič nestratíme.
Teraz už vieme, kam môžeme dať našu najľavejšiu záplatu. Tá zakryje nejaké diery. Podobnou argumentáciou zdôvodníme, že druhú najľavejšiu záplatu môžeme dať od najľavejšej nezakrytej diery. Podobne s ďalšími záplatami.
Náš postup si možno predstaviť takto: Predstavme si, že sa postavíme na začiatok potrubia a pochodujeme po ňom smerom doprava. Ak zbadáme dieru, tak od nej dáme záplatu. Ignorujeme diery, ktoré sú od poslednej položenej záplaty vzdialené do jedného metra, pretože sú zaplátané našou záplatou. Toto robíme, až kým neprídeme na koniec potrubia.
Program potom bude vyzerať jednoducho. Budeme postupne načítavať diery. Keďže sú utriedené, tak ich načítavame presne v tom poradí, ako by sme ich pri našom pochode zbadali. Pamätáme si, odkiaľ sme položili poslednú záplatu. Pri načítaní ďalšej diery len zistíme, či je poslednou záplatou zakrytá, vtedy neurobíme nič. Ak nie je zakrytá, tak položíme novú záplatu t.j. vypíšeme jej pozíciu a zapamätáme si ju ako polohu novej poslednej záplaty.
Tento algoritmus urobí nanajvýš niekoľko málo operácií pre každú z dier, preto povieme, že jeho časová zložitosť je lineárna od počtu dier. (Niekedy sa jednoducho povie, že časová zložitosť je lineárna a šikovný čitateľ si má domyslieť vzhľadom na aký paramenter.) Matematici tento fakt povedia takto: Časová zložitosť je \(O(n)\)).
Podobne je to s pamäťovou zložitosťou. Program si pamätá len niekoľko málo čísel, preto povieme, že pamäťová zložitosť je konštantná. (Niekto by opäť mohol povedať konštatná od počtu dier). Konštanta má ale tú výhodu, že je konštantná od ľubovoľného parametra.) Pododne ako predtým matematik povie toto: Pamäťová zložitosť je \(O(1)\).
#include<iostream>
using namespace std;
int main() {
int N;
cin >> N;
// Lavy koniec zaplaty, na zaciatku nieco hrozne vlavo.
double zaplata = -999999;
for (int i = 0; i<N; ++i) {
// Pozicia diery.
double diera;
cin >> diera;
if (diera > zaplata+1) { // Ak povodna zaplata uz nedociahne ...
zaplata = diera; // ...dame novu zaplatu...
cout << zaplata << endl; // ...a vypiseme ju.
}
}
return 0;
}N = int(input())
# Lavy koniec zaplaty, na zaciatku nieco hrozne vlavo.
zaplata = -999999.0
for i in range(N):
# Pozicia diery.
diera = float(input())
if diera > zaplata+1: # Ak povodna zaplata uz nedociahne ...
zaplata = diera # ...dame novu zaplatu...
print(zaplata) # ...a vypiseme ju.Program Zhrdzavene_potrubie;
var N,i:integer;
diera,zaplata:real; { pozicia diery, lavy koniec zaplaty }
begin
read(N);
zaplata:=-999999; { nieco hrozne vlavo }
for i:=1 to N do
begin
read(diera);
if diera>zaplata+1 then { Ak povodna zaplata uz nedociahne... }
begin
zaplata:=diera; { ...dame novu zaplatu...}
writeln(zaplata); { ...a vypiseme ju. }
end;
end;
end.Vzorový príklad #2
Tento príklad je z KSP-Z 13. ročníka (áno aj vtedy bolo KSP a malo príklady), 1. kolo, 4. O valcočlovekovi II.
Zadanie
Valcočlovek je taký človek, ktorého tvar sa približuje tvaru valca s určitou výškou a polomerom. Výskyt ľudí takéhoto tvaru je veľmi vysoký napríklad medzi pracovníkmi francúzskych vínnych pivníc (čím viac vína pracovník skonzumuje, tým je širší). Francúzske vínne pivnice sú veľké podzemné sály tvaru obdĺžnika podopierané tenkými stĺpmi. Strany obdĺžnika sú orientované v smere svetových strán. Často sa stáva, že valcočlovek sa zasekne medzi stĺpy a vínna pivnica sa stane nepoužívateľnou (zaseknutý valcočlovek zle vplýva na kvalitu vína). Preto si valcočlovek musí vždy dobre rozmyslieť, cez ktorú pivnicu môže ísť.
Úloha
Napíšte program, ktorý načíta rozmery pivnice \(m, n\), počet stĺpov \(p\) a polomer valcočloveka \(r\). Potom načíta súradnice stĺpov ( \([0.00,0.00]\) je severozápadný roh pivnice, \([m,n]\) juhovýchodný ) a napíše, či môže tento valcočlovek prejsť pivnicou od západnej steny po východnú.
Formát vstupu
Na prvom riadku sú čísla \(m\), \(n\), \(p\) a \(r\). Potom nasleduje \(p\) riadkov, na každom sú 2 čísla - súradnice stĺpov.
Formát výstupu
Vypíšte jeden riadok obsahujúci vetu "Valcoclovek II neprejde pivnicou." alebo "Valcoclovek II prejde pivnicou."
Vzorové riešenie
Riešenia možno rozdeliť v zásade na tieto skupiny:
-
Pokúšame sa zistiť, či existuje cesta zo západu na východ. Tu sa vyskytlo niekoľko modifikácií. Buď ste si predstavili pivnicu v podstate ako grafickú obrazovku, okolo stĺpov ste vyfarbili kruhy a pokúšali sa vyfarbiť pivnicu od západu k východu, alebo ste rekurzívne prehľadávali pivnicu s nejakým krokom (o 1 hore, dole, vpravo, vľavo). Tieto riešenia sú veľmi nepresné a neefektívne. Dali sa za ne získať maximálne 2 body.
-
Pokúšame sa zistiť, či nejaké stĺpy tvoria taký rad, že každé dva susedné sú od seba vzdialené o menej ako priemer Valcočloveka a prvý je od severnej a posledný od južnej vzdialený tiež o menej ako priemer Valcočloveka. Tu sa vyskytlo niekoľko prístupov. Rekurzie s exponenciálnou zložitosťou mohli získať maximálne 4 body, algoritmy s kubickou zložitosťou 5 bodov a s kvadratickou zložitosťou maximálne 10 bodov. Vyskytlo sa niekoľko typov kvadratických riešení, všetky sú ale v podstate modifikáciou uvedeného vzorového riešenia.
1 bod sme strhávali pri nekontrolovaní podmienky \(2r < n\). Ďalší bod bolo možné stratiť v prípade neuvedenia popisu algoritmu a ešte jeden v prípade absencie príkladov vstupu a výstupu programu alebo odhadu zložitosti algoritmu.
Ak sa na pivnicu pozrieme zhora, stĺpy si môžeme predstaviť ako body a Valcočloveka ako kružnicu. Je zrejmé, že medzi dvoma stĺpmi ktoré sú bližšie ako priemer Valcočloveka sa on neprepchá. Spojme teda každú takúto dvojicu hranou. Navyše si predstavme severnú a južnú stenu ako špeciálne stĺpy (jeden označme \(0\) a druhý \(p+1\)). Stena bude spojená hranou s iným stĺpom, ak je k nemu bližšie ako priemer Valcočloveka. Úlohu teraz možno previesť na grafovú. Je zrejmé, že ak existuje cesta z vrcholu \(0\) na vrchol \(p+1\), tak Valcočlovek pivnicou neprejde (ak by prešiel, musel by niekde križovať lomenú čiaru od severnej steny k južnej, čo je spor s predpokladom, že cez vyznačené hrany sa nedá ísť). Na druhej strane ak takéto prepojenie neexistuje, Valcočlovek dokáže prejsť (toto možno ľahko nahliadnuť, ak si predstavíme Valcočloveka, ktorý pôjde tak, že po ľavej ruke bude mať vždy nejakú hranu alebo severnú stenu - bude kopírovať terén. Určite prejde na druhú stranu, keďže nikde sa netiahnu hrany od severu na juh).
Zisťovanie existencie cesty medzi vrcholmi \(0\) a \(p+1\) spravíme nasledovne: Začneme vo vrchole \(0\), ktorý označíme a uložíme do fronty (Fronta je dátová štruktúra, kde prvky ukladáme na koniec fronty a zo začiatku ich zase v prípade potreby vyberáme. Môžete si ju predstaviť ako rad na zaplatenie u pokladne v potravinách (ľudia sa postavia na koniec a čakajú, kým ich pokladníčka vpredu ''vyberie''). (pozn.red.)). Potom postupne vyberáme vrcholy z fronty a každý neoznačený vrchol, ktorý je s nimi spojený hranou označíme a uložíme na koniec fronty. Ak uložíme niekedy do fronty vrchol \(p+1\), tak existuje cesta zo severu na juh a Valcočlovek neprejde. Na druhej strane keď vyčerpáme všetky vrcholy fronty a \(p+1\)-vý sa tam nenachádza, Valcočlovek pivnicou prejde.
Časová zložitosť algoritmu je \(O(p^2)\), kde \(p\) je počet stĺpov, pretože každú hranu pozrieme nanajvýš dvakrát (vo fronte budú oba jej prislúchajúce vrcholy) a hrán je maximálne \((p+1)^2\).
Či sú dva stĺpy bližšie ako priemer valca je výhodnejšie testovať podmienkou \((x_1-x_2)^2 +(y_1-y_2)^2 < 4r^2 \) ako \(\sqrt{(x_1-x_2)^2+(y_1-y_2)^2} < 2r\), pretože v prvom prípade netreba odmocňovať. Používať pole na vzdialenosti sa tiež neoplatí, pretože každú vzdialenosť budeme pri správnom algoritme počítať nanajvýš raz (i keď na hranu sa pozrieme dvakrát).
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct bod {
double x;
double y;
};
int m,n,p;
double r,d;
vector<bod> stlpy;
void nacitaj() {
// Nacitame vstup;
cin >> m >> n >> p >> r;
d = 2*r;
// Spravime ho o jedno vacsi. A nepouzijeme miesto 0.
// Aby sme mohli specialne stlpy mat 0 a p+1.
stlpy.resize(p+1);
for (int i = 1; i<=p; ++i) {
cin >> stlpy[i].x >> stlpy[i].y;
}
}
double vzd2(int s1, int s2) {
if (s1 == s2) return 0;
if ((s1 == 0 && s2 == p+1) || (s1 == p+1 && s2 == 0)) {
return n*n;
}
if (s1 == 0) {
return stlpy[s2].y * stlpy[s2].y;
}
if (s1 == p+1) {
return (n - stlpy[s2].y) * (n - stlpy[s2].y);
}
if (s2 == 0) {
return stlpy[s1].y * stlpy[s1].y;
}
if (s2 == p+1) {
return (n - stlpy[s1].y) * (n - stlpy[s1].y);
}
return (stlpy[s1].y - stlpy[s2].y)*(stlpy[s1].y - stlpy[s2].y) +
(stlpy[s1].x - stlpy[s2].x)*(stlpy[s1].x - stlpy[s2].x);
}
bool prejdi() {
queue<int> fronta;
vector<bool> bol(p+2, false);
fronta.push(0);
bol[0] = true;
while (!fronta.empty() && !bol[p+1]) {
int stlp = fronta.front();
fronta.pop();
// Vyber z fronty vrchol a skontroluj neprekontrolovane stlpy,
// ktore su k nemu blizsie ako 2 * r - pridaj ich do fronty.
for (int i = 1; i<=p+1; ++i) {
if (!bol[i] && vzd2(stlp, i) < d*d) {
fronta.push(i);
bol[i] = true;
}
}
}
return bol[p+1];
}
int main() {
nacitaj();
// Sirka valcocloveka II je vacsia ako pivnica alebo sa da
// prejst od severu k juhu po blizkych stlpoch.
if (n < d || prejdi()) {
cout << "Valcoclovek II neprejde pivnicou." << endl;
} else {
cout << "Valcoclovek II prejde pivnicou." << endl;
}
return 0;
}from heapq import heappop, heappush
m,n,p,r = input().split()
m,n,p,r = int(m), int(n), int(p), float(r)
d = 2*r
# Spravime ho o jedno vacsi. A nepouzijeme miesto 0.
# Aby sme mohli specialne stlpy mat 0 a p+1.
stlpy = [(-1,-1)]
for i in range(p):
x,y = map(float, input().split())
stlpy.append((x,y))
def vzd2(s1, s2):
if s1 == s2: return 0
if (s1 == 0 and s2 == p+1) or (s1 == p+1 and s2 == 0):
return n*n
if s1 == 0:
return stlpy[s2][1]**2
if s1 == p+1:
return (n - stlpy[s2][1])**2
if s2 == 0:
return stlpy[s1][1]**2
if s2 == p+1:
return (n - stlpy[s1][1])**2
return (stlpy[s1][1] - stlpy[s2][1])**2 + (stlpy[s1][0] - stlpy[s2][0])**2
def prejdi():
bol = [False for i in range(p+2)]
bol[0] = True
fronta = [0]
while len(fronta) > 0 and not bol[p+1]:
stlp = fronta[0]
heappop(fronta)
# Vyber z fronty vrchol a skontroluj neprekontrolovane stlpy,
# ktore su k nemu blizsie ako 2 * r - pridaj ich do fronty.
for i in range(1,p+2):
if not bol[i] and vzd2(stlp, i) < d*d:
heappush(fronta, i)
bol[i] = True
return bol[p+1]
# Sirka valcocloveka II je vacsia ako pivnica alebo sa da
# prejst od severu k juhu po blizkych stlpoch.
if n<d or prejdi():
print("Valcoclovek II neprejde pivnicou.")
else:
print("Valcoclovek II prejde pivnicou.")Čas poslednej úpravy: 4. apríl 2017 20:52