Zápočet 1. června (rozvrh)

Xerxes
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:

Zápočet 1. června (rozvrh)

Příspěvek od Xerxes »

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.
dmt
Matfyz(ák|ačka) level I
Příspěvky: 29
Registrován: 7. 5. 2006 21:52
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Příspěvek od dmt »

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:
Xerxes
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:

Příspěvek od Xerxes »

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...
Radooo
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

Příspěvek od Radooo »

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)
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?
Whole life is only your imagination...
Uživatelský avatar
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

Příspěvek od starecml »

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...
Odpovědět

Zpět na „2006“