Soutez
v programovaniSoutez
v programovani
Na prelomu dubna a kvetna se v prostorach katedry pocitacu FEL CVUT konal uz druhy rocnik souteze v programovani organizovany spolecne spolecnosti ACM a katedrou pocitacu FEL CVUT. Vzhledem k ocekavane vyssi ucasti soutezicich bylo rozhodnuto letosni soutez rozdelit na dve casti. s tim, ze ti nejlepsi z lokalniho kola FEL CVUT postoupi do prazskeho kola, kde se utkaji s vybery ostatnich fakult CVUT a dalsich prazskych vysokych skol.
Jako loni i tento rok byla cela soutez vyhodnocovana automaticky pomoci specialniho programoveho vybaveni vyvijeneho na katedre pocitacu FEL CVUT. Vyhodnocovaci system i soutezici meli k dispozici server HP 9000 s operacnim systemem HP UX od firmy Hewlett Packard. Soutezici mohli k vyreseni uloh pouzivat programovaci jazyk C (norma ANSI) a Pascal (norma ISO). Hodnotily se pouze vysledky a nikoliv kvalita odevzdanych programu. Jedinou vyjimkou bylo casove omezeni. Pro kazdou ulohu byl stanoven casovy limit, ve kterem musela skoncit. Pri prekroceni tohoto limitu nebyla uloha prijata.
Soutez probihala podle pravidel stanovenych pro regionalni kolo ACM Programming Contest.
Je jiz tradici, ze hlavnim souteznim dnem je sobota. Aby meli vsichni soutezici stejne podminky, maji moznost zucastnit se den predem tj. v patek jakehosi predkola, ve kterem se mohou dukladne seznamit s prostredim vyhodnocovaciho systemu, s operacnim systemem, editory a mohou si zkusit vyresit cvicne ulohy. Toto predkolo take slouzi k otukani konkurencnich tymu, i kdyz neplati, ze kdo ma nejlepsi vysledky v patek, vyhraje soutez v programovani.
Zadani uloh maji soutezni tymy pripravene u pocitacu v zalepenych obalkach. Samotne zapoleni je odstartovano slovne nekterym z poradatelu a technicky spustenim vyhodnocovaciho systemu. Pokud nektery ze souteznich tymu otevre obalku s ulohami jeste pred zacatkem souteze, nasleduje diskvalifikace. Konec souteze je obdobny; po vyhlaseni nekterym z poradatelu nasleduje zastaveni vyhodnocovaciho systemu a zablokovani souteznich kont.
Soutezici pracuji na pracovnich stanicich PC s operacnim systemem Linux, ze kterych se pripojuji k serveru HP 9000 s operacnim systemem HP UX (Unix) . Kazdy tym ma kdispozici jeden pocitac a na nem ctyri virtualni terminaly, mezi kterymi lze prepinat pomoci klaves Alt F1, Alt F2 ... . K dispozici maji textovy editor joe, resp. jeho mutace jstarr, jpic, jmacs, ti otrlejsi mohou klidne pouzit vi. Napsany program se zkompiluje pomoci pripravene davky compile soubor. V teto davce jsou zahrnute potrebne knihovny a prepinace pro kompilator. Po napsani a odladeni je treba pouzit davku submit soubor na odevzdani ulohy. Nazev ulohy musi korespondovat s oznacenim ulohy (a, b, c ...), jeho pripona musi byt bud .c pro zdrojovy text v jazyce C, nebo .p pro jazyk Pascal. Pro ladeni jsou k dispozici pouze standardni prostredky dostupne v HP UX a nutno podotknout - nema to ani cenu zkouset. Zpracovavane ulohy je mozne vytisknout na sitovou tiskarnu pomoci davky print soubor. Vytisknuta data prinese tymu jeden z poradatelu, tzv. runner. Udaje o tom, kolik uloh uz odevzdali a s jakym uspechem, mohou soutezici ziskat pomoci programu state. Informace o prubeznem poradi souteznich tymu jsou s vyjimkou posledni pulhodiny vypisovany na zbylych pocitacich v soutezni mistnosti.
Vyresene a odevzdane ulohy v jazyce C nebo Pascal jsou testovany vyhodnocovacim systemem a mohou byt klasifikovany nasledovne:
O poradi rozhoduje:
Termin
pro letosni lokalni kolo byl stanoven na dny 26. a 27. dubna 1996. O ucast
v lokalnim kole projevilo zajem okolo dvaceti tymu. K oficialni prezentaci
v patek 26. dubna se nakonec dostavilo sestnact tymu. Na oficialnim zahajeni
lokalniho kola byli soutezici privitani vedoucim katedry pocitacu doc.
Ing. Borivojem Melicharem CSc. Po prednasce doc. Kolare venovane
programovani nastoupil reditel souteze Bernard Jech a seznamil soutezni
tymy s organizacnimi zalezitostmi. Pote se vsechny tymy presunuly k pocitacum
a zacalo treninkove klani. Ulohy urcene pro seznameni se se systemem byly
ty same jako v lonskem rocniku, a tak neni divu, ze nektere tymy odchazely
uz po pulhodine a na jejich konte byly vyresene vsechny ulohy. A soutez
v programovani mela najednou sve favority.
Ovsem ostre ulohy pro sobotni cast souteze uz byly pripravene a uderem devate hodiny bylo odstartovano lokalni kolo souteze v programovani, ve kterem se bojovalo o prvnich sest postupovych mist do prazskeho kola. Soutezici rozlepili obalky s ulohami a zavladlo hrobove ticho. Na jejich pobledlych oblicejich byla videt uporna snaha nejenom uloham porozumet, ale i nalezt nejake reseni, v tom lepsim pripade dokonce optimalni reseni.
Vetsina souteznich uloh sla resit nejakym naivnim algoritmem. Casove limity vsak byly voleny tak, aby naivni algoritmy neprosly, coz se nakonec ukazalo byt tvrdym oriskem pro vetsinu tymu. Po peti hodinach usilovneho zapoleni mely pouhe tri tymy odevzdane dve ulohy z moznych sesti, dalsi tymy odevzdaly jednu ulohu a nektere tymy nic. O poradi na postupovych mistech tak rozhodoval prevazne cas, takze bylo rozhodnuto soutez prodlouzit o jednu hodinu, aby tymy mely jeste cas odevzdat nektere z rozpracovanych uloh. Nicmene v nastavovanem case se uz nic moc nezmenilo, a tak nastal cas ukonceni souteze a vyhlaseni vysledku.
Prazske
kolo se uskutecnilo 3.-4. kvetna 1996 za ucasti souteznich tymu z FEL CVUT,
FJFI CVUT a MFF UK. A slo o hodne. Ve hre bylo pravo postupu do regionalniho
evropskeho kola, ktere se letos uskutecni v Bratislave. Pripraveny byly
i ceny od sponozora, jimz byla i tentokrat firma Hewlett
Packard.
Po oficialnim zahajeni v patek 3. kvetna, na nemz soutezni tymy privital dekan elektrotechnicke fakulty doc. Ing. Jan Uhlir, CSc. spolu s vedoucim katedry pocitacu doc. Ing. Borivojem Melicharem CSc., zacalo zkusebni kolo. Zkusebniho kola se nektere z tymu, ktere prosly lokalnim kolem FEL CVUT, neucastnily.
Na soutezici v prazskem kole cekalo osm uloh ruznych obtiznosti. A hned od pocatku bylo zrejme, ze pujde o strhujici souboj mezi nejlepsimi tymy MFF UK a FEL CVUT, kterym vice nez zdatne sekundovali doktorandi katedry pocitacu FEL CVUT (bez moznosti postupu do regionalniho kola). Prvni uloha (zadani c) byla uspesne prijata uz po dvanacti minutach! Poradi na prednich mistech se neustale menilo a mnohdy o poradi rozhodovaly pouhe desitky sekund. Vitezny tym nakonec vyresil sest uloh z osmi, soutezni tym na poslednim miste jednu ulohu. Na rozdil od lokalniho kola tedy nebylo nutno prodluzovat.
Pri vyhlasovani vysledku meli nejvice duvodu k radosti clenove vitezneho druzstva z MFF UK ve slozeni Jan Kotas, Michal Koucky, Vit Novak, kteri spolu s druzstvem FEL CVUT ve slozeni Jan Cada, Vladimir Drlik a Martin Kacer maji narok na postup do regionalniho kola.