Zkouška 6.6.2011

Zadání a řešení (aspoň doufám! :)) podobné tomuto:

http://forum.matfyz.info/viewtopic.php?f=247&t=6839

Akorát formulované hudebně (úloha Pavarotti) :D

Na ústní jdu až zítra, takže na jaké VMT a b-stromy se ptají, musí někdo doplnit.

Tak ja sem napisu plny zneni, treba to nekoho zachrani :)

Jmenovalo se to teda nejspis Pavarotti a za ukol bylo zjistit jestli a kolikrat je mozne sestrihat dlouhy koncert tak, aby po slepeni dal vasi kratsi pisnicku. (useky se nedaly prehazovat)

Vstup:

1. radek obsahoval pisnicku ve tvaru:
   [slabika]-[ton]-[delka] [slabika]-[ton]-[delka] [slabika]-[ton]-[delka] ...

2. radek byl koncert ve stejnem formatu

Vystup:
pocet moznosti sestrihani koncertu, aby poslepovane kousky daly pisnicku

Omezeni:
pisnicka - max 100 000 trojic [slabika]-[ton]-[delka]
program koncertu - hodne dlouhy
vystupni hodnota - vejde se do 2^63
pamet - 2 MB (HDD neomezene)
slabika - 3 a min znaku
delka - 4B int, 1 az 240 000
ton - jeden nebo dva znaky (CDEFG.., C# D#..., Cb..., c1 d1..., c2 d2... tyhle kombinace)
celkem 86 tonu

A pouzit slo jen trojici, ktera presne odpovida te v pisnicce (takze presne stejna slabika, ton, delka).

Jinak problem je asi algoritmicky stejnej jako ten, co posilal kolega vejs ^^

Tak hodne stesti :)

Na ústní jem byla v den zkoušky, pravý sloupeček byl Topfer. Šla jsem úplně poslední, ptal se na vnější třídění a když mi tu otázku vymýšlel, tak řekl, cituji: "Já jsem se dneska ptal snad už úplně na všechno, na co já se vás zeptám?"
V písemce jsem si špatně spočítala kolik bytů zabere jeden prvek a nevešla jsem se do zadaných 2MB protože jsem použila spoják a ne pole. Jinak jsem ji měla dobře. Vnější třídění jsem uměla, ale nějak mi nešlo se pořádně jasně vyjádřit, takže za dva.

Ještě bych u toho doplnil jednu úvahu, která mi prošla a řekl bych, že je docela dobrá (pokud sem teda tradičně neobjevil Ameriku :D):

Když si do pole načtete první řádek...tak to je vlastně posloupnost znaků určité abecedy. A všechny trojice sou pak znaky téhle abecedy. Úvaha je taková, že koncert = hodně hodně velká množina různých znaků a naše písnička tvoří jenom malinkou podmnožinu. Když bude mít 100 000 znaků a koncert řádově moc, tak s docela "dobrou" pravděpodobností se nám stane, že tabulku velikosti 100 000 procházíme zbytečně, protože ten znak vůbec nepotřebujeme.
Takže by nebylo od věci si pro každý znak nejdřív nějak "dostatečně rychle" otestovat, jestli ho vůbec použijeme a vyhnout se tak procházení polem.
Já sem zvolil Dictionary (o kterym si myslim, že je to "hashovaná tabulka"), takže otestovat, jestli tam nějaký znak je máme skoro v konstantním čase.
Výsledná časová složitost v nejhorčim případě sice zůstane stejná, ale když byste si to třeba zkusili naimplementovat, tak zrychlení tam je opravdu velký.
Sice tim slovníkem asi přetečete paměť, ale mega paměti si koupíte. Hodinu života ne :).

Vše samozřejmě bez záruky :D