# Zápočet 1. června (rozvrh) <{ForumPost(poster="Xerxes", timestamp=2007-06-01 13:37:47)}> Dnes nás hlídal Ondřej Šerý a zadal následující úlohu: Dostaneme soubor, který má na každém řádku popis nějaké události, konkrétně čas začátku, doba trvání a jméno, například: (...) 14:00 1:30 Písemka z MA 13:45 0:30 Něco 15:00 1:30 Přednáška (...) Všechny časy patří do jediného dne. Řádky jsou seřazené náhodně, jejich počet není omezený a časy se mohou překrývat. Můžeme předpokládat korektní vstup, ale časy nemusely být upravené, tedy místo "09:00 00:05" tam mohlo být třeba "9:0 0:5", a mezer mezi položkami mohlo být víc. Délka jména události omezena být mohla. Dále byl zadaný počet místností a úkolem bylo rozvrhnout události do místností tak, aby se v rámci místnosti nepřekrývaly. Říkal, že rozvržení nemusí být nutně optimální, ať už to znamená cokoliv... Dal nám následující pravidla: - síť byla po stažení testovacích souborů odpojena - literatura a poznámky byly povoleny (ne však opisování zdrojáků) - z C++ byla povolena syntaxe, jeho knihovny (STL) nikoliv (!) Na řešení nám dal 3 hodiny, ale protože jsem odcházel po hodině a půl jako první, nevím, kolik na to bylo doopravdy času a jaká byla úspěšnost. Moje dojmy: Podle mého názoru velmi snadná úložka, pokud člověk ví, jak ji řešit algoritmicky. Já jsem znal řešení problému, jak vybrat co nejvíc nepřekrývajících se událostí, a tak jsem tímto způsobem postupně zaplnil všechny místnosti. Jeden výběr probíhá následovně. Události se seřadí vzestupně podle času začátku. Potom se vezme první, označí se jako vybraná a přeskočí se všechny ty, které začínají dřív, než vybraná končí. Potom se vybere další a tak dále, dokud se neprojde celé pole. Seřazení lze provést pouze jednou na začátku a pak přeskakovat již zařazené události. <{/ForumPost}> <{ForumPost(poster="dmt", timestamp=2007-06-01 13:59:44)}> no ja som odchadzal pred jednou a to tam boli este skoro vsetci takze neviem aka bola nakoniec uspesnost... k algoritmu: udalosti som si zotriedil a potom kazdu udalost dal do prvej volnej miestnosti k odtiaznosti: najhorsie bolo asi nacitat vstup (isiel som jednoducho prasacky po znakoch, kedze tam mohlo byt lubovolne medzier a cisla nemali presny format -- ak to niekto robil lepsie budem rad ak mi to objasnite) k zakazu STL: ZRADA! :evil: <{/ForumPost}> <{ForumPost(poster="Xerxes", timestamp=2007-06-01 14:56:40)}> > najhorsie bolo asi nacitat vstup (isiel som jednoducho prasacky po znakoch, kedze tam mohlo byt lubovolne medzier a cisla nemali presny format -- ak to niekto robil lepsie budem rad ak mi to objasnite) Ano, načítání vstupu jsem řešil také po znacích. Ale napsal jsem si na to funkce *int fgetint(FILE *f)* na načtení integeru a *void fskipspaces(FILE *f)* na přeskočení mezer. A konečně jsem v nich, snad poprvé, využil *ungetc()*... > k zakazu STL: ZRADA! Zákaz STL však v této konkrétní úloze moc bolet nemusel. Pravda, bylo nutné načítat pole o předem neznámé velikosti, ale to je asi tak všechno a dá se to řešit ručně občasným reallocem. No a na třídění máme céčkovský *qsort()*. Tím chci říct, že existuje spousta úloh, u kterých by byl zákaz STL mnohem nepříjemnější. Nicméně pozor na tohoto zadávajícího, vypadal na to, že u zápočtů z céčka STL nepovolí obecně, nejen u takové úlohy. Zaslechl jsem něco o tom, že je to "příliš velká výhoda nad těmi, kdo STL neznají". > no ja som odchadzal pred jednou a to tam boli este skoro vsetci takze neviem aka bola nakoniec uspesnost... Půl hodiny před koncem tam ještě byli skoro všichni? To nevypadá moc dobře... <{/ForumPost}> <{ForumPost(poster="Radooo", timestamp=2007-06-01 15:03:49)}> > dmt wrote:k odtiaznosti: najhorsie bolo asi nacitat vstup (isiel som jednoducho prasacky po znakoch, kedze tam mohlo byt lubovolne medzier a cisla nemali presny format -- ak to niekto robil lepsie budem rad ak mi to objasnite) ja som tam dnes nebol, ale ma napadlo, ze tie casy sa mohli predsa nacitat cez **fscanf** nie? predsa jeden cas musel byt v celku a iba medzi casmi mohli byt viacere medzery, nie? <{/ForumPost}> <{ForumPost(poster="starecml", timestamp=2007-06-01 16:05:36)}> Zustal jsem az do konce. Zadani jsem splnil, hazelo mi to spravne vysledky, ale mel jsem nejakou podivnou narocnost. Dost ho to popudilo, a nechal mi vymyslet, jak by to slo resit jinak - lepe. Neco jsem vymyslel, ale nebyl z toho nejak zvlast nadseny a rekl at se nezlobim, ale ze tohle neuzna... Velice fajn chlapik, ale v porovnani s ostatnimi cvicicimi co jsem tady cetl na foru nepovolil STL. Me osobne by to pomohlo, protoze jsem si na STL dost zvykl a spoustu casu jsem stravil nacitanim toho pitomeho vstupu... Nu coz, treba priste natrefim na cviciciho, ktery STL povoli. Jinak co se tyce uspesnosti: asi po hodine odesel prvni, po 2,5hod. dalsi 2 a dalsich 6 to dodelalo po tech 3 hodinach. Uspesnost tedy vcelku fajnova... Gratuluju tem, co to zvladli, ja jsem to mohl mit taky, kdybych si dal pozor na narocnost... <{/ForumPost}>