súťaž stredoškolákov v programovaní
Tento dokument obsahuje oficiálne pravidlá súťaže v programovaní ProFIIT, ktorej usporiadateľom je Fakulta informatiky a informačných technológií Slovenskej technickej univerzity v Bratislave (FIIT STU). Súťaž je určená pre žiakov stredných škôl. Organizátor môže pravidlá ešte upraviť. Definitívna podoba pravidiel sa zverejní v internetovom sídle fakulty najneskôr tri dni pred začatím súťaže.
1 Všeobecné ustanovenia
ProFIIT je súťaž v programovaní pre žiakov stredných škôl. Odporúča sa najmä pre tých stredoškolákov, ktorí sa plánujú prihlásiť na bakalárske štúdium informatiky na FIIT STU s nástupom v nasledujúcom akademickom roku.
ProFIIT prebieha v dvoch kolách:
- korešpondenčné kolo
- finále
Ak nie je uvedené inak, pre obidve kolá súťaže platia rovnaké pravidlá.
Pravidlá súťaže ProFIIT vznikli na základe pravidiel medzinárodnej programátorskej súťaže ACM.
2 Kto sa môže súťaže zúčastniť
Prvého — korešpondenčného — kola súťaže sa môžu zúčastniť jednotlivci alebo dvojčlenné tímy žiakov stredných škôl. Každý súťažiaci musí byť v školskom roku, v ktorom sa súťaže zúčastňuje, žiakom strednej školy alebo osemročného gymnázia. Súťaž je určená predovšetkým pre žiakov, ktorí navštevujú 4. ročník strednej školy alebo oktávu v osemročnom gymnáziu (maturanti). Finále súťaže ProFIIT je súťaž jednotlivcov a zúčastnia sa ho súťažiaci najúspešnejších tímov z korešpondenčného kola.
3 Registrácia
Súťaže sa môžu zúčastniť len zaregistrovaní účastníci. Účastníci, ktorí spĺňajú podmienky súťaže sa môžu zaregistrovať v elektronickom systéme pre organizáciu ProFIIT iba v čase podľa harmonogramu súťaže. Počet tímov, ktoré sa môžu zaregistrovať je obmedzený.
4 Priebeh súťaže
Prvé kolo súťaže bude prebiehať korešpondenčnou formou cez Internet. V termíne vyhláseného začiatku prvého kola podľa harmonogramu súťaže bude v elektronickom systéme pre organizáciu ProFIIT zverejnených 10 problémov. Riešenia problémov možno odovzdať iba do termínu ukončenia prvého kola súťaže podľa harmonogramu. Druhého kola súťaže — finále — sa zúčastnia najlepší jednotlivci a tímy, pričom tentokrát všetci budú súťažiť ako jednotlivci. Súťaž bude prebiehať na určenom mieste a bude trvať 5 hodín. Na riešenie bude 6 problémov.
Cieľom oboch kôl súťaže bude vytvoriť počítačové programy ako správne riešenia čo najväčšieho počtu problémov a prostredníctvom systému ich odovzdať v čo najkratšom čase. Ako riešenie sa odovzdáva zdrojový súbor programu napísaný v programovacom jazyku Pascal, C alebo C++. Program nemôže závisieť od prítomnosti žiadneho externého súboru a ani nemôže žiadny takýto súbor vytvárať. Vstup sa načítava zo štandardného vstupu (klávesnica) a výstup sa vypisuje na štandardný výstup (obrazovka), pozri časť 6. Každé riešenie môže byť zapísané v ľubovoľnom z uvedených programovacích jazykov bez ohľadu na predošlé odovzdané riešenia.
Odovzdané programy sa v systéme automaticky skompilujú, vykonajú a otestuje sa ich vstupno-výstupné správanie. Každé odoslané riešenie sa potom buď prijme ako vyhovujúce alebo sa zamietne. Ak bude riešenie zamietnuté, je možné odovzdať ďalšie riešenie. Za nevyhovujúce riešenia je súťažiaci penalizovaný. Celú túto činnosť automaticky bez zásahu človeka (avšak pod dozorom rozhodcov) vykoná a výsledok otestovania odovzdaného riešenia bude súťažiacim prezentovať elektronický systém pre organizáciu ProFIIT formou správy. Zoznam všetkých správ systému a spôsob hodnotenia je uvedený v časti Hodnotenie riešení.
Na priebeh súťaže a automatické vyhodnocovanie riešení dozerajú rozhodcovia. Rozhodcami sú spravidla členovia akademickej obce FIIT (študenti aj zamestnanci). Rozhodcovia majú konečnú právomoc rozhodovať, či sú uvedené riešenia správne, alebo nie. Proti rozhodnutiu rozhodcov sa nie je možné odvolať.
V prípade problémov s porozumením zadaní alebo so systémom, sa môžu súťažiaci opýtať rozhodcov prostredníctvom elektronickej pošty. Pokiaľ rozhodcovia uznajú, že nejasnosť v zadaní skutočne existuje, budú o nej informovaní všetci súťažiaci.
Celkové priebežné výsledky súťaže budú zverejňované na stránke systému ProFIIT počas celej súťaže okrem posledných 5 dní pri korešpondenčnom kole a posledných 60 minút vo finále.
Súťažiaci môžu používať všetku dostupnú literatúru.
5 Programovacie jazyky
Všetky programy budú testované pod operačným systémom FreeBSD 5.2-RC1.
Programy v Pascale budú kompilované pomocou Free Pascal Compiler verzia 2.4.2.
Programy v C a C++ budú kompilované pomocou gcc verzia 3.3.3, ktoré vyžaduje štandardy:
- C: ANSI "C89" = ISO "C90" (podľa normy ANSI X3.159-1989, ISO/IEC 9899:1990)
- C++: ISO/IEC 14882:1998
6 Povolené a zakázané funkcie
Súťažiaci majú povolené používať len obmedzenú podmnožinu funkcií poskytovaných programovacími jazykmi. Vo všeobecnosti je možné používať všetky funkcie, ktoré sú používané pre štandardný vstup (napr. pre C: scanf, sscanf, getchar, gets, pre Pascal: read, readln), vytváranie štandardného výstupu (napr. pre C: printf, putchar, pre Pascal: write, writeln - bez súboru), prácu s pamäťou (napr. pre C: malloc, free, pre Pascal: new, dispose) a matematickými výpočtami (napr. sqrt, qsort) a prácu s reťazcami (napr. strcmp, strcpy).
Nie je povolené:
- otvárať súbor iný ako štandardný vstup a štandardný výstup (napr. pre C: open, fopen, pre Pascal: append, reset)
- používať viac ako jeden proces (napr. pre C: signal, fork)
- používať akékoľvek sieťové prostriedky (napr. pre C: socket).
6.1 Jazyky C, C++
V jazyku C je povolené používať funkcie deklarované v nasledovných hlavičkových súboroch (pozn.: nie všetky z deklarovaných funkcií týchto hlavičkových súborov sú povolené, pozri nižšie):
- stdio.h
- stdlib.h
- ctype.h
- string.h
- math.h
- limits.h
- complex.h
K týmto hlavičkovým súborom je v jazyku C++ navyše povolené používať funkcie deklarované v hlavičkových súboroch:
- string
- complex
- iostream
- memory
- set
- vector
- map
- queue
- deque
- multiset
- multimap
- priority_queue
- algorithm
- stack
- hash_set
- hash_map
- hash_multiset
- hash_multimap
- hash
- list
- slist
- bit_vector
- bitset
- iterator
- valarray
- numerics
- functional
- numeric
- ctime
- utility
Okrem funkcií deklarovaných v iných ako povolených hlavičkových súboroch, nie je v súťaži povolené používať funkcie zo zoznamu zakázané funkcie pre C, C++. Pre zjednodušenie uvádzame aj zoznam všetkých povolených funkcií pre jazyky C, C++.
6.2 Jazyk Pascal
V jazyku Pascal nie sú povolené žiadne rozšírenia štandardnej knižnice (t. j. v programe nepoužívajte "uses"). Na zvláštnej stránke uvádzame zakázané funkcie pre Pascal.
7 Hodnotenie riešení
Výsledok testovania odovzdaného riešenia má podobu práve jednej správy z:
Správa | Význam |
Chyba pri kompilovaní | Nepodarilo sa preložiť zaslaný zdrojový kód. |
Chyba pri behu programu | Program bol úspešne preložený, ale počas výpočtu sa zrútil (napríklad kvôli deleniu nulou alebo zlému prístupu do pamäte). |
Vypršanie časového limitu | Program bol úspešne preložený a spustený, ale neskončil počas požadovaného časového limitu. Buď sa v ňom vyskytol nekonečný cyklus, alebo bol použitý málo efektívny algoritmus. |
Zlá odpoveď | Program sa začal vykonávať, skončil a vytvoril nejaké (poprípade aj žiadne) výsledky, ale tieto výsledky nie sú správne. |
Prezentačná chyba | Program skončil a vypísal nejaké výsledky, ktoré sa zdajú byť v poriadku. Ich tvar však nie je presne taký, ako bol požadovaný v zadaní. Často ide o preklep, vynechanú medzeru vo výstupe a podobne. |
Akceptovaný | Program je uznaný za správny. Daný problém sa považuje za úspešne vyriešený. |
Volanie nepovolenej funkcie | Súťažiaci sa pokúsili použiť niektorú z nepovolených funkcií programovacieho jazyka. |
Porušenie pravidiel | Táto odpoveď sa použije, keď rozhodcovia zistia nejaké iné porušenie pravidiel alebo nesplnenie zadania. |
Iba správa Akceptovaný znamená, že sa riešenie prijalo ako vyhovujúce. Všetky ostatné správy znamenajú zamietnutie riešenia. Pre každý problém, ktorý bude nakoniec Akceptovaný, sa počíta čas v sekundách od začiatku súťaže po okamih, kedy bol úspešne odovzdaný. Za každé (predchádzajúce) nesprávne odovzdanie (okrem chyby pri kompilovaní a použitie/volanie nepovolenej knižnice/funkcie) riešenia problému sa do celkového času pre tento problém pripočítava penalizácia 1 deň pre korešpondenčné kolo a 10 minút pre finále súťaže.
8 Hodnotenie súťaže
Súťažiaci sú hodnotení podľa počtu odovzdaných správnych riešení. Teda vo výslednom rebríčku sú súťažiaci zoradení podľa počtu vyriešených problémov (čím viac vyriešených problémov, tým lepšie umiestnenie). V prípade, že viac súťažiacich vyrieši rovnaký počet problémov, títo sa zoradia podľa súčtu celkových časov pre správne vyriešené problémy vrátane penalizácií za odovzdané nesprávne riešenia (čím kratší čas, tým lepšie umiestnenie). Za problémy, ktoré neboli nakoniec správne odovzdané, sa penalizácie nepripočítavajú.
Víťazmi súťaže ProFIIT sú prví traja úspešní riešitelia vo finále. Úspešný riešiteľ je každý účastník finále ProFIIT, ktorý vyrieši najmenej 2 problémy.
9 Fair-play
Súťažiaci sa pri registrácii zaväzujú dodržiavať pravidlá súťaže. Ďalej sa zaväzujú, že všetky ich odovzdané riešenia budú ich vlastné, ktoré sami napísali, žiadna iná osoba im pritom nebude pomáhať ani nepoužijú riešenia alebo ich časti, ktoré namiesto nich napísal niekto iný. Tiež sa zaväzujú, že nebudú s riešením zadaní pomáhať iným súťažiacim. V prípade zistenia akéhokoľvek porušenia pravidiel bude súťažiaci diskvalifikovaný (v prípade tímu bude diskvalifikovaný celý tím).