Spísané skúšky - Holan/Pergel/Topfer 200X - 2017

Pokračování základního kursu programování pro studenty 1. ročníku bakalářského studia informatiky a učitelství informatiky. Výuka bezprostředně navazuje na předmět PRG030 Programování I výkladem dalších algoritmů a jejich programové realizace, postupů a technik užívaných při tvorbě programů. Posluchači se seznámi se základy objektového programování a práce v současných vývojových prostředích. Předpokládají se vstupní znalosti v rozsahu předmětu PRG030 Programování I.
Uživatelský avatar
SaNuel
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 11. 10. 2018 14:52
Typ studia: Informatika Bc.

Spísané skúšky - Holan/Pergel/Topfer 200X - 2017

Příspěvek od SaNuel »

Zdravím všetci. V súboroch som si našiel starý texťák, v ktorom som prepísal všetky úlohy ako programy, tak nejaké hinty na ústnu časť, kde sú popridávané nejaké postrehy a nakoniec linky na prípadné poskytnuté odpovede tu na fóre.
Nevem či je tam všetko, neviem či je to správne, ale možno to dakomu pomôže:

Program
(-q sú otázky bez riešení)

ČIAROVÉ KÓDY (2018)
Naprogramujte čítačku čiarových kódov.
Kód má svetlé pásmo, štart sektor, 1-10 sektorov so zakódovanými čísalami, stop sektor a svetlé pásmo.
Sektory s číslami vyzerajú ako 5 čiar, z ktorých 2 sú úzke a 2 široké.
Štart sektor má 3 čiary, prvé 2 široké.
Stop sektor má 3 čiary, posledná je úzka.
Madzi každou čiarou je medzera, pred a za kódom svetlé pásmo.
Širšia čiara je trojnásobne širšia ako úzka. Medzera nenesie informáciu a je úzka ako úzka čiara.
Svetlé pásmo je aspoň 10-krát širšie ako úzka čiara.
Výška kódu je aspoň pätina jeho celkovej dĺžky.
Podiel svetlosti čiar a medzier je menší ako 0,7.
Kód môže byť natočený ľubovoľne, môže byť parciálne porušený, môže byť ľubovoľne veľký (50x10-7800x5000px)
Vstup:
Bitmapa 10 000 x 10 000 v RGB, ktorá obsahuje najviac 1 čiarový kód.
Výstup:
Rozkódované číslo
Odkaz:
http://forum.matfyz.info/viewtopic.php?f=247&t=11705
POMSTA POŠTMAJSTRA TONKA (2018)
Poštmajster Tonko sa chce pomstiť svojm zamestnávateľovi - Českej Pošte s.p., a na svojej poslednej smene pre dôchodkom chce postaviť čo najvyššiu vežu z krabíc, ktorú následne demonštratívne zapáli.
Obmedzenia:
Pri skladaní krabíc musí byť podstava dolnej krabice >= podstave hornej kraice (teda 2x2 nemôžeme postaviť na 1x2, ale môžeme dať 2 2x2 krabice na seba).
Skladať krabice na seba možno len v poradí, ako prichádzajú na vstupe ( teda pre vstup 2x2 a 3x3 má veža max. výšku 3).
Tonko si pamätá, v akom poradí pôjdu krabice (ponevadž ich sám skladal na pás), teda si môže naplánovať, ktoré krabice použije a ktoré nechá na páse.
Krabice tak označené možno otáčať okolo zvislej osi, no vždy len o 90 stupňov, teda steny krabíc veže sú na seba rovnobežné.
RAM rádovo stovky MB
Vstup:
Postupnosť krabíc s rôznymi rozmermi a údaj, či môžeme krabicu otáčať (len okolo zvislej osi, teda nie prevracať).
Výstup:
Maximálna výška veže z krabíc zo vstupu.
Odkaz:
http://forum.matfyz.info/viewtopic.php?f=247&t=11685
ELEKTROMOBIL
Je zadaný neorientovaný, ohodnotený graf mesta s N vrcholmi. Ohodnotenie hrán zodpovedá počtu minút, ktoré treba na presun medzi vrcholmi hrany. Máme elktromobil, ktorý je na začiatku vo vrchole V, má kapacitu nabitia C a je aktuálne nabitý na B. Jedna "jednotka nabitia" nám vystačí na 1 minútu cesty, takže ak chceme prejsť po hrane s hodnotou 8, musíme mať v nádrži aspoň 8 jednotiek nabitia. Niektoré mestá slúžia ako čerpacie stanice, v ktorých sa instantne nabije elektromobil na jeho maximálnu kapacitu. Takýchto miest je T.
Úloha:
Je zadaných S miest - showroomov. Máme nájsť najkratší sled (hrany sa môžu opakovať) taký, ktorý začne vo vrchole V a navštívi v ľubovoľnom poradí všetky vrchol zo S. Nemáme zaručené, že takýto sled existuje.
Vstup:
Hrany (mesto1, mesto2, cena)
Počiatočný vrchol (V, C, B), teda (počiatočné mesto, kapacita, nabitie)
Stanice
Showroomy
Výstup:
Ak existuje sled, výpis (čas, mesto)
Riešenia:
http://forum.matfyz.info/viewtopic.php?f=247&t=11387

DENDŽERÓZNE CESTY (2017)
V meste sú ulice ohodnotené dĺžkou a nebezpečnosťou. Úlohou je nájsť čo najbezpečnejšiu cestu medzi dvoma miestami v meste. Nebezpečnosť cesty závisí na nebezpečnosti najnebezpečnejšej ulice po ceste, a ak je viac rovnako nebezpečných ciest, chceme najkratšiu. Je zaručené, že aspoň jedna existuje.
Vstup:
Zoznam ulíc: odkiaľ, kam, bezpečnosť ( <= 2^31, počet prepadnutí), dĺžka
Štart a cieľ cesty
Obmedzenia:
Križovatky <= 1000
Pamäť 1GB
Výstup:
Nebezpečnosť najbezpečnejšej cesty + výpis cesty
Riešenie1:
Zoradiť hrany podľa nebezpečnosti a odoberať najhoršie. Na odobratom grafe kontrolovať súvislosť komponent Štartu a Konca. Následne vrátiť posledné hrany a Dijkstrom nájsť najbezpečnejšiu cestu.
Riešenie2:
Zoradiť si hrany podľa bezpečnosti. Následne binárne hľadať bezpečnosť, od ktorej vyššie odoberiem hrany a skontrolujem súvislosť komponent so Štartom a Koncom. Tak nájsť minimálnu možnú bezpečnosť. Tu treba myslieť na hrany s rovnakou nebezpečnosťou, ktoré následne buď rátať ako jeden prvok v binárnom vyhľadávaní a následne, ak je to kritická nebezpečnosť, nájsť najoptimálnejšiu cestu, alebo ich rozlíšiť už v binárnom vyhľadávaní podľa dĺžky pomocou dvojstupňového comparingu.
Odkazy:
http://forum.matfyz.info/viewtopic.php?f=247&t=11418
PALINDRÓMY (2017)
Máme vstupný reťazec dĺžky n. Úlohou je v polynomiálnom čase nájsť jeho minimálne pokrytie pomocou palindrómov, tz. chceme text rozdeliť na čo najmenej palindrómov.
Napr. "steponnopets" sa dá pokryť jedným palindrómom - sebou samým, "abaaba" sa dá pokryť 2mi palindrómami "aba" alebo jedným "abaaba". Minimum je teda 1.
Jeden znak je vždy palindróm, takže "abcdefgh" je 8 palindrómov dĺžky 1 => horný odhad je n.
Obmedzenia:
Pamäť 4GB
Riešenie1:
(nie optimálne) Najprv si vytvorím tabuľku n*n, kde prvok P(i,j) je true ak úsek i..j tvorí palindróm.
Potom stačí rekurzia:
X[a,b] = minimálny poČet palindrómov pokrývajúcich úsek a,b.
X[a,b] = 1, ak P(a,b) = true, inak je to min cez všetky úsek a,k tvoriace palindróm (zodpovedajúce true - stĺpcom v a-tom riadku P) z výrazu (1+X[k+1,b])
Výsledok je potom uožený v X[1,n]
Teda zložitosť tabuľky P je n^2 (vziať všetky prostriedky a rozvíjať do strán), vyplnenie tabuľky X je n^3 (v každom poli práca času n)
Celkovo n^3
Riešenie2:
Vytvorí sa tabuľka P tak ako v riešení 1. Namiesto true sa určia vzdialenosti 1, ostatné nekonečno. Následne sa na tabuľku pozerá ako na maticu susednosti, a následne napr. Floyd-Marshallom sa hľadá najkratšia cesta z 1 do n.
Odkazy:
http://forum.matfyz.info/viewtopic.php?f=247&t=11370
DÁMA (2015)
Šachovnica 8x8. Každý hráč 12 kameňov, pohybujú sa po diagonálach atď atď... Vziať kamienok súperovi je povinné, na druhom konci šachovnice sa kamienok stáva dámou... Prehráva hráč bez kamienkov alebo bez možných ťahov.
Obmedzenia:
Pamäť neobmedzene
Disk neobmedzene, ale neplytvať (vôbec nie je treba)
Vsup:
Rozloženie šachovnice a kto je na ťahu
Výstup:
Najlepší možný ťah.
Všeobecné riešenie:
Minimax a alfa-beta orezávanie.
Odkazy:
http://forum.matfyz.info/viewtopic.php?f=247&t=10608
http://www.inf.upol.cz/downloads/studiu ... oritmy.pdf
VOĽBY (2012, 2017)
Začína volebná kampaň a vy, ako predseda, musíte obísť čo najviac meetingov, pričom na každom musíte zostať po celú jeho dobu a musíte prísť včas. Koľko najviac meetingov sa môžete zúčastniť a aké to sú? Ak je viac riešení, vypíšte ľubovoľné.
Na vstupe dostanete zoznam miest, popis cestnej siete a zoznam meetingov (detaily nižšie). Máte zaručené, že medzi kaŽdými dvoma mestami vedie cesta, ale nemusí byť priama. Hrany sú neorientované a hodnotené časom prejazdu.
Obmedzenia:
Počet miest N <= 1000
Dĺžka názvu miest <= 30
Najdlhšia cesta medzi dvoma mestami <= 500 minút
Počet meetingov <= 50000
Najdlhšia doba meetingu <= 3.5 dňa
Doba kampane <= 31 dní

RAM: 2.5 MB
Program by mal bežať v rozumnom čase (počítajte s CPU zvĺadajúcim 10^9 inštrukcii za ekundu)
Môžete ukladať dáta na HDD. Pre účely úlohy predpokládajte nekonečne veľký úložný priestor.
Formát vstupu:
N
N riadkov s názvami miest
M
M riadkov s cestami (mesto, mesto, čas prejazdu)
P
P riadkov (mesto, minúta, hodina, deň, mesiac, rok)
Formát výstupu:
I (dĺžka najdlhšej meetingovej šnúry)
I riadkov (mesto, minúta, hodina, deň, mesiac, rok)

Cestu je nutné vypísať chornologicky vzostupne podľa času začiatku meetingu
Odkazy:
http://forum.matfyz.info/viewtopic.php?f=247&t=8279
http://forum.matfyz.info/viewtopic.php?f=247&t=11350
LABYRINTH (2010, 2017)
Theseus, Minotaur a Ariadna chcú prejsť labyrintom každý do svojej vysnenej miestnosti a snažia sa ostatným vyhnúť (ani ich nevidieť).
Každá postava prejde za 1 minútu 1 chodbu alebo 1 minútu čaká.
V každej minúte nemôžu byť žiadni 2 v spoločnej, ani 2 susedných miestnostiach.
Obmedzenia:
Počet miestností <= 100
RAM 512 kB (4 MB v inom zadaní)
Vstup:
N - počet miestností
N prechodov medzi miestnosťami (miestnosť, miestnosť)
Začiatočná a koncová miestnosť pre Thesea
-||- pre Minotaura
-||- pre Ariadnu
Výstup:
Najmenší počet minút, za ktorý sa každý dostane do svojej miestnosti bez stretu (a vidu) ostatných, 1 ak neexistuje nekonfliktný súbor ciest.
Odkazy:
http://forum.matfyz.info/viewtopic.php?f=247&t=10950
http://forum.matfyz.info/viewtopic.php?f=247&t=6881

BURZA (2013, 2015, 2016)
Ráno dostanú burzoví makléri zoznam pokynov od klientov, ktoré akcie majú predať, ktoré kúpiť. Na základe týchto pokynov majú pre každý typ cenného papieru (ISIN) určiť kurz (cenu ISINu) pre tento deň, za ktorú sa zobchoduje čo najviac akcii.
Pre každý ISIN nájsť kurz, pri ktorom sa zobchoduje čo najviac akcii. Počet zobchodovaných akcii pre danú cenu a ISIN je minimum z počtu akcii, ktoré sú ľudia za danú cenu ochotní kúpiť, resp. predať. Ak je ideálnych kurzov viac, vypísať strednú hodnotu.
Obmedzenia:
Nevytvárať príliš veľa súborov (max. toľko, koľko ISIN)
Nečítať opakovane a neprepisovať súbory
Nepoužívať disk ako RAM
1 znak = 1 byte
Počet ISIN <= 3 000
Počet pokynov <= 100 000 000
Počet maklérov <= 10 000
Max. kurz = 43 000 000
Počet klientov <= 10 000 000
Min. kurz = 0.01
RAM 1 MB
Disk neobmedzený, ale neplytvať
Vstup:
Textový súbor s pokynmi:
ID makléra - 10 znakov
ID klienta - 10 znakov
ID ISIN - 12 znakov
Názov IDIN - 20 znakov
Typ pokynu - N/P
Limitná cena - (s presnosťou na haliere)
Počet akcii - celé číslo Pascal longint (4B)
Výstup:
Textoý súbor:
ISIN, názov ISIN, kurz, počet akcii, ktoré sa predajú/nakúpia
Odkazy:
http://forum.matfyz.info/viewtopic.php?f=247&t=9668 -q
http://forum.matfyz.info/viewtopic.php?f=247&t=10940
http://forum.matfyz.info/viewtopic.php?f=247&t=5221
http://forum.matfyz.info/viewtopic.php?f=247&t=10543 -q

AUTÍČKA (2011)
Máme križovatku (=šachovnicu) s autami 8x8. Na každom políčku je auto, ktoré ide vľavo, hore alebo je políčko prázdne.
Na každom políčku môže byť max. 1 auto. Každú minútu sa môžu autá pohnúť o jedno políčko.
Nájdite algoritmus, ktorý vypíše, za koľko minút sa križovatka vyprázdni pri optimálnom pohybe áut.
Príklad:
OLO___LUO___OOO___OOO
OUL_>_OLO_>_LOO_>_OOO
OOO___OOO___OOO___OOO
Teda sa vyprázdni za 3 minúty.
Obmedzenia:
Počet áut <= 20
RAM 2.8 MB
Odkazy:
http://forum.matfyz.info/viewtopic.php?f=247&t=7800

LODIČKY (2015)
Na vstupe je súbor v ktorom sú riadky:
Typ lode (názov, rozmery, počet lodí typu)
Potopené lode (názov typu, umiestnenie, rotácia)
Zásah do vody (umiestnenie)
Rozmer hracieho plánu (N x M)
Obmedzenia:
Typy lodí <= 20
Počet lodí <= 20
Rozmery plánu <= 30 x 30
Rozmery lodí <= 10 x 10 (?)
Pamäť neobmedzená, ale rozumne
Disk nepotrebný
Loď sa potopí na 1 zásah.
Lode sa môžu dotýkať hranami.
Výstup:
Zoznam políčok, na ktorých je určite loď.
Zoznam políčok, kde loď určite nie je.
Odkazy:
http://forum.matfyz.info/viewtopic.php?f=247&t=10506

KNIŽNÝ VEĽTRH (2013, 2015)
10 spisovateľov rozdáva ma veľtrhu autogramy.
Veľtrh je Štvorcová sieť 20x20.
O každej osobnosti vieme, kedy prídu, aká bude ich trasa, teda počiatočné políčko a ich pohyb NSWEX (sever,východ,západ,juh,stáť).
Časy pohybov sú konštantné pre všetkých a dané "číslom pohybu".
Autogram dostaneme, ak stojíme v rovnakom čase na rovnakom políčku, ako osobnosť, teda bez ohľadu na počet ľudí na danom políčku.
Každý autogram má nejakú cenu.
Program má naplánovať trasu ako nazbieram autogramy s čo najväčšou celkovou cenou.
Obmedzenia:
Počet osobností 10
Rozmery veľtrhu 20x20
Dĺžka trás osobností <= 100
Počet krokov (čas) 1..5000
RAM 27 MB
Cena autogramu <= MAXINT/10
Vstup:
Textový súbor (po riadkoch):
Krok, kedy osobnosť príde, cena autogramu, počiatočné políčko, trasa
Výstup:
Plán trasy:
Dĺžka trasy, celková cena autogramov, počiatočné políčko, trasa
Priorita riešenia:
1. Cena
2. Najkratšia doba strávená na veľtrhu
Odkazy:
http://forum.matfyz.info/viewtopic.php?f=247&t=4425
http://forum.matfyz.info/viewtopic.php?f=247&t=9640 -q
http://forum.matfyz.info/viewtopic.php?f=247&t=10463
(neriešiť pomocou BFS, ale DFS všetkých možností s orezávaním, inak hrozia havárie)
ČLÁNOK (2014 - Topfer)
Máme súbory. V každom je článok. Chceme zistiť najpopulárnejšie slová v článkoch. Kritérium slova je ale málo. Kritérium je teda najpočetnejší výskyt dvojice slov vo všetkých článkoch.
Komplikácia:
V rámci jednej vety napr "A B A B A B." sa "A B" počíta len raz.
Súbor synonym, kde na každom riadku sú synonymá pre nejaké slovo (teda "pes spí", "psovi spia", "psa spíme" sú rovnaké)
Súbor blacklist, kde na každom riadku je zakázané slovo (prevažne spojky a prasačiny). Slová v blackliste tiež môžu obsahovať synonymá.
Obmedzenia:
Počet súborov <= 1000
Počet slov v súbore <= 10 000
Počet slov celkovo <= 1 000 000
Dĺžka slova <= 20
Počet synonym pre slovo <= 20
Počet slov vo vete <= 30
Počet slov v blackliste <= 10 000
RAM 0,5 MB
Disk neobmedzene
Výstup:
50 najčastejších dvojíc slov.
Odkazy:
http://forum.matfyz.info/viewtopic.php?f=247&t=10074

VÝLET ABSTINENTA (2014)
Z mapy s mestami nájsť cestu k cieľu, ktorá vedie čo najďalej od všetkých krčiem. Ak ich je viac, vypíšte najkratšiu.
Obmedzenia:
Počet miest <= 100 000
Dĺžka cesty <= 1 000 000
Vstup:
Mestá
Cesty medzi mestami (mesto, mesto, dĺžka)
Zoznam miest s krčmami
Počiatočné mesto, cieľové mesto
Odkazy:
http://forum.matfyz.info/viewtopic.php?f=247&t=10057 -q

PLÁN NA ROK
Naplánovať akcie na rok. Každá akcia má vlastnú prioritu <0;1000>. Ak je priorita 1000, akcia musí byť naplánovaná. Ak sa 2 akcie s prioritou 1000 prekrývajú, úloha nemá riešenie. Ak jedna akcia končí v minúte, keď druhá začína, dajú sa stihnúť obe. Akcie (aj s prioritou 1000) sa môžu rôzne prekrývať. (?)
Obmedzenia:
Počet akcii <= 100 000
Trvanie akcie <= 10 000 minút
RAM 2 MB
Disk neobmedzene
Vstup:
Riadky akcii v tvare:
Začiatok, koniec, priorita (kde začiatok a koniec sú v tvare deň, mesiac, hodina, minúta)
Výstup:
Maximálny dosiahnuteľný počet priorít.
Do textového súboru v tvare ako vo vstupe jednotlivé použité akcie.
Odkazy:
http://forum.matfyz.info/viewtopic.php?f=247&t=10037
KONCERTY
Cez prázdniny chete navštíviť koncerty aby ste si vypočuli čo najviac muziky.
Každý deň stihnete max. 1 koncert.
Koncerty sa nachádzajú v rôznych mestách.
Medzi mestami sa dá prejsť v priebehu jedného dňa.
Na koncerte sa vždy hrá niekoľko skladieb daného speváka.
Ohodnotenie koncertu je suma dĺžky všetkých pesničiek.
Za prázdniny môžete prejsť max. 2000 km.
Medzi každými dvoma mestami existuje cesta celočíselnej dĺžky, nie však nutne priama.
Obmedzenia:
Počet pesničiek <= 10 000
Počet dní = 92
Počet spevákov <= 100
Počet miest <= 100
Na jednom koncerte <= 100 pesničiek
RAM 5 MB (možno použiť viac)
Riešenie:
http://forum.matfyz.info/viewtopic.php?f=352&t=1885
http://forum.matfyz.info/viewtopic.php?f=247&t=6743
STAVBA SLOVA
Na vstup dostaneme slovo znakov <= 100 anglickej abecedy (26) a následne zoznam substitučných pravidiel <= 100. Substitúcia je výmena písmena za písmeno alebo písmeno za 2 (a->b, a->bc).
Obmedzenia:
RAM 1 MB
Vstup:
Slovo dĺžky <= 100
Zoznam substitúcii
Výstup:
Množina písmen, z ktorých možno substitúciami dostať dané slovo.
Riešenie:
http://forum.matfyz.info/viewtopic.php?f=247&t=6897
http://forum.matfyz.info/viewtopic.php?f=247&t=8339

KAMEROVÝ SYSTÉM (2011)
Máme mesto M, ktorého mapa je mriežka.
Mesto má 999x999 blokov, teda 1000x1000 križovatiek.
Na každej križovatke je kamera.
Máme k dispozícii záznamy všetkých kamier.
Záznamy sú v tvare:
ID kamery - 9 znakov
Čas
Meno osoby na kamere
Číslo pasu osoby
Obvod pásu osoby
Trvalé bydlisko osoby
Niektorým kamerám idú hodiny o 5 minút napred, nevieme ktorým...
Nevieme kde je ktorá kamera.
Kamera určí totožnosť všetkých ľudí na križovatke.
Obyvatelia mesta prejdú vzdialenosť medzi križovatkami za 5 minút
Obyvateľov je <= 1 000 000
Obyvatelia môžu aj stáť, vždy 5,10,15... minút
Raz za 5 minút sú všetci obyvatelia na nejakej križovatke.

V meste je múzeum a autobusová stanica.
Poznáme ID kamier na stanici a pri múzeu.
Zo stanice odchádza o 18:00 autobus s neobmedzenou kapacitou. Kto bol o 18:00 na stanici, mohol nastúpiť.
Autobus je jediná cesta von z mesta.
Múezum niekto vykradol v čase Č, lupiči s lupom stáli v čase Č pred múzeom.

Úlohou je zistiť, či sa mohlo stať, že lupiči dostli lup von z mesta autobusom na stanici o 18:00.
Môže dôjsť k predaniu lupu na ľubovoľnej križovatke. Trvá 0 času.
Máme k dispozícii záznamy kamier 24 hodín pred vykradnutím múzea až do 19:00 v daný deň.

Obmedzenia:
RAM 3 MB
Disk neobmedzene
Vstup:
Čas Č, záznamy kamier
Výstup:
Áno/Nie/Nemožno určiť
Rišenia:
http://forum.matfyz.info/viewtopic.php?f=247&t=4515
http://forum.matfyz.info/viewtopic.php?f=247&t=7753

PODPOSTUPNOSTI (2007, 2012)
Dostaneme súbor s prvým riadkom <= 255 znakov, ostatné neobmedzene veľké. Úlohou je nájsť podpostupnosti tvaru 1. riadku v ostatných riadkoch.
Výstup:
Počet podpostupností
Príklad:
Vstup:
SOS
ASOGSOSF
Výstup:
4
(_SO_S___
_SO___S_
_S___OS_
____SOS_)
Riešenia:
http://forum.matfyz.info/viewtopic.php?f=247&t=6839
http://forum.matfyz.info/viewtopic.php?f=247&t=7739

STRÁNKA PÁNA V (2010 nie je novšie)
Máte k dispozícii log webového serveru v tvare:
IP adresa užívateľa, čas, načítaná stránka
Stránka sa považuje za aktívnu v čase t z intervalu 4 minút, ak v ňom bolo dokopy >= 1000 načítaní od aktívneho používateľa.
Používateľ je aktívny, ak zobrazil aspoň 512 stránok.
Obmedzenia:
RAM 2 KB
Disk <= 16 použitých neobmedzene dlhých súborov
Výstup:
Čas, čas + 4 min, počet akt. stránok
(PO 00:00:01 - PO 00:05:01 - 5 aktívnych stránok
PO 00:05:01 - PO 00:08:32 - 6 aktívnych stránok)
Riešenie:
Vonkajšie triedenie.
http://forum.matfyz.info/viewtopic.php?f=247&t=6796

OBJEM PÓDIA (2009 nie je novšie)
Máme 2 typy súčiastok, z ktorých môžeme skladať kocky, a z nich následne zložíme pódium:
Nosník (3 typy) - pomenovaný (ID) podľa nejakého rockového CD
K(rátky) - zodpovedá strane kocky, dĺžky 0.5m
D(lhý) - zodpovedá stranovej uhlopriečke kocky
H(odne dlhý) - zodpovedá telesovej uhlopriečke kocky
Spojovací diel - pomenovaný (ID) podľa nejakej rockovej skupiny
Obmedzenia:
Pódium možno zostaviť jednoznačne
RAM 10 KB
Počet dielov <= 1 000 000
Vstup:
Súbor, kde dostaneme na každom riadku 3 údaje:
Typ nosníku, ID nosníku, ID spojovacieho dielu
(K, The Piper at the Gates of Dawn, Pink Floyd)
Výstup:
objem zostaveného pódia
Riešenie:
http://forum.matfyz.info/viewtopic.php?f=247&t=5361

ČOKOLÁDA (2007)
Máme tabuľku čokolády 10x10 políčok. Dĺžka strany políčka je 1. V čokoláde sú oriešky a hrozienka (guľaté, na vstupe súradnice a polomery), počet <= 1000. Napíšte program, ktorý určí, ako najľahšie rozrezať čokoládu na 3 diely. Najľhašie znamená s čo najmenšou prácou, kde rez čokoládou dĺžky jedna je práce 1, orechu dĺžky 1 práce 5 a hrozienka dĺžky 1 práce 1/2. Každá hrana stojí prácu v pomere koľko je tam čokolády, hrozienok a orechov. Rezať sa môže len po hranách, ale možno ľubovoľne meniť smer. Čookoláda má konštantnú výšku,rezanie orechu stredom aj na kraji stojí rovnako veľa práce (nezáleží na výške orechu), jednoducho je to všetko 2D. Rezaním čokolády nesmie v žiadnom kuse vzniknúť diera.
Obmedzenia:
RAM 1 MB
Dostupná funkcia:
DĺžkaTetivy(xstred,ystred,R,y), ktorá vráti dĺžku tetivy orechu alebo hrozienka o polomere R, ktorá pretína hranu na súranici y.
Výstup:
Rezané hrany, práca.
Ústna časť

PERGEL
Dynamické programovanie + použitie
Uzátvorkovanie násobenia matíc
Definícia zložitosti problému, O, theta, omega notácia, dôkaz časovej zložitosti triedenia porovnávaním je theta nlogn - dolný a horný odhad.


HOLAN
Virtuálne metódy, ich implementácia a výhody.
Fungovanie minimaxu a alfa-beta orezávanie.
AVL stromy, invariant, zákldaná myšlienka, operácie (rotácia, dvojitá rotácia, odoberanie prvku pridávanie, odstránenie koreňa...)
Hľadanie mediánu
Stavba haldy v lin. čase
B-stromy
Dynamické programovanie, čo, ako, prečo + príklady


TOPFER
Vnútorné triedenie (najhoršia a priemerná časová zložitosť Quicksortu, ukázať algoritmi s najhorším časom nlogn (Heapsor,Mergesort) a odvodiť pamäťovú zložitosť).
Čo je simulačný kalendár a ako ho reprezentovať (prioritná fronta a halda), čo v ňom je (čas, proces)
Definícia AVL stromu (ako sa AVL líši od BST)
Definícia dokonale vyváženého stromu. Ak máme postupnosť čísel, ako vyrobyť DVS (zotriediť + DeC), prečo sa používa AVL podmienka a nie podmienka dokonale vyváženého stromu (AVL potrebujú na údržbu lin.čas)
Abstraktná trieda, na čo je, či môže obsahovať metódy, ktoré majú telo apod.
Základné princípy (static X abstract X virtual X sealed)

Kód: Vybrat vše

if ( exam.date > critical_date ) {
    this.procrastination.enable();
    Steam.launch("Skyrim");
}
else {
    this.panic.start();
    // TODO: This isn't working...
}
[/size]
Odpovědět

Zpět na „PRG031 Programování II“