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.
Zápočet 1. června (rozvrh)
-
- Matfyz(ák|ačka) level I
- Příspěvky: 29
- Registrován: 7. 5. 2006 21:52
- Typ studia: Informatika Mgr.
- Kontaktovat uživatele:
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!
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!
-
- Matfyz(ák|ačka) level I
- Příspěvky: 37
- Registrován: 23. 1. 2007 16:32
- Typ studia: Informatika Bc.
- Bydliště: Zlínský kraj / Kolej 17. listopadu
- Kontaktovat uživatele:
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()...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)
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().k zakazu STL: ZRADA!
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í".
Půl hodiny před koncem tam ještě byli skoro všichni? To nevypadá moc dobře...no ja som odchadzal pred jednou a to tam boli este skoro vsetci takze neviem aka bola nakoniec uspesnost...
-
- Matfyz(ák|ačka) level I
- Příspěvky: 7
- Registrován: 29. 1. 2007 00:13
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
fscanf
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?dmt píše: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)
Whole life is only your imagination...
- starecml
- Matfyz(ák|ačka) level I
- Příspěvky: 24
- Registrován: 25. 9. 2006 18:06
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
hmmm
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...
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...