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)