Odovzdávanie a testovanie programov

Programy odovzdávate preto, aby ste sa učili okrem teoretického algoritmického myslenia aj programovať.

V tomto článku sa dozviete:

• ako má váš program načítavať vstup a vypisovať výstup
• verzie kompilátorov, ktoré používame na testovanie
• príklady korektných programov
• vysvetlenia chybových hlášok testovača

Ako má vyzerať odovzdaný program

Program má čítať zo štandardného vstupu (stdin, resp. input, inak povedané klávesnice v konzole), písať na štandardný výstup (stdout, resp. output, inak povedané obrazovku). Výstup musí dodržiavať formát uvedený v zadaní. A za každým riadkom na výstupe musí byť znak nového riadku (v C++ '\n', v Jave/C# použite ### Your title here...println/WriteLine). Vo svojom riešení sa nemusíš zaoberať kontrolovaním správnosti vstupných údajov. Súbor sa môže volať ľubovoľne, pri submitovaní je vždy jasné, ktorú úlohu submituješ.

Počas behu sa musí tvoje riešenie správať slušne. Zakázaný je akýkoľvek prístup k súborovému systému (na vstup a výstup sa používa štandardný vstup a výstup), prístup do pamäte testovača, snaha akýmkoľvek spôsobom narušiť jeho fungovanie a všetky podobné aktivity. Explicitne je zakázané používať viac ako 1 thread, t. j. volať fork() a podobné.

Operačný systém a kompilátory na počítači, ktorý testuje riešenia

Vaše riešenia testujeme pod Arch Linuxom, na počítači, ktorý je vybavený 64bitovým procesorom (z toho napríklad vyplýva, že v C++ má premenná long veľkosť 64 bitov). Zoznam podporovaných jazykov nájdete tu.

Aktuálne používanú verziu kompilátoro nájdete vo svojom protokole, ale môžete očakávať, že verzie sú pomerne aktuálne (väčšinou najnovšie stabilné / LTS verzie).

Príklady korektných programov

Príklady korektných programov si môžeš pozrieť tu.

Pamäťový a časový limit

Odovzdaný program sa testuje na viacerých sadách vstupov. Za jednu sadu dostaneš bod ak program správne, dostatočne rýchlo (v časovom limite) a s použitím najviac vyhradenej pamäte vyrieši všetky vstupy sady. Ak program nesplní niektorú z daných podmienok, ako odpoveď testovača dostaneš jednu z hlášok, ktoré sú popísané tu.

Na každom vstupe sa tvoj program spúšťa odznova, teda behy na jednotlivých vstupoch sú ohraničené samostatne.

Ak nie je v zadaní úlohy povedané inak, pamäťový limit pre beh programu na jednom vstupe je 1 GB (teda napr. pole integerov s miliardou prvkov si nemôžeš dovoliť vytvoriť).

Časový limit na vyriešenie jedného vstupu je obvykle približne 1 sekunda (teda program stihne niekoľko 10-100 miliónov jednoduchých operácií). Časové limity nastavujeme tak, aby sa úlohy kategórie Z (1 - 3) dali určite vyriešiť na plný počet bodov aj v pomalších jazykoch (napr. v Pythone) a pri úlohách 4 - 5 sa toto tiež snažíme dodržať.

Môj program mi funguje, ale keď ho submitnem, neakceptujete ho!

Môžeš nás kontaktovať na discorde alebo na maili ksp-info@ksp.sk . Predtým ale vyskúšaj, či ti nepomôže jedna z nasledujúcich rád tu alebo nižšie:

Ak si dostal odpoveď Chyba počas behu programu/EXC (exception)

• Programy musia korektne skončiť, t.j. skončiť s návratovou hodnotou 0. Ak je tvoj program v jazyku C, hlavná funkcia main() musí vracať int a posledný príkaz pred jej ukončením musí byť return 0;.
• Skontroluj si, či tvoj program nepotrebuje viac pamäte ako dovoľuje pamäťový limit. Pamäťový limit pre úlohu býva zvyčajne 1 GB. Ak sa jej pokúsi použiť viac, nepodarí sa mu to a skončí s chybou. (Ak skoro všetku pamäť alokuješ staticky ako polia, toto spoznáš tak, že tvoj program spadne okamžite, teda čas jeho behu bude nanajvýš 2 ms.)
• Skontroluj si, či máš dosť veľké polia na to, aby si aj najväčší možný vstup dokázal uložiť do pamäte.

Ak si dostal odpoveď Prekročený časový limit/TLE (time limit exceeded)

• Každá úloha má nastavený svoj osobitný časový limit. Za tento čas má tvoje riešenie vyriešiť jeden z testovacích vstupov. Tvoj program dostane na každom testovacom vstupe rovnaký časový limit. Preto pomalé riešenia vyriešia malé vstupy (OK), ale veľké už nie (TLE). Ak tvoj program beží dlhšie (napríklad z dôvodu zacyklenia), tvoj program ukončíme a riešenie dostane na danej testovacej sade 0 bodov.
• Časový limit nastavujeme tak, aby sa s pomalšími jazykmi ako Python a Java dali vyriešiť úlohy 1-5 na plný počet bodov. Ak si myslíš, že by tvoje riešenie naprogramované v pomalšom jazyku malo dostať OK, napíš nám. Pri riešení náročnejších úloh (>5) odporúčame použiť rýchlejší jazyk ako napr. C++. Ak má tvoje riešenie optimálnu časovú zložitosť, ale je naprogramované v pomalšom jazyku, možno na posledných vstupoch dostaneš TLE, ale stále môžeš dostať plný počet bodov za popis riešenia.
• Ak zvykneš pri debugovaní dopísať do programu, aby po vypísaní výsledku počkal na stlačenie klávesy, skontroluj, či si v svojom programe takýto príkaz nezabudol (a od tohto prístupu si čo najskôr odvykni).
• Zamysli sa nad tým, či je tvoj algoritmus skutočne dosť rýchly na to, aby ľubovoľný možný vstup vyriešil v zadanom časovom limite. Ak áno, je problém v implementácii, ak nie, chce to inú, lepšiu myšlienku.
• Občas je pomalosť programu skrytá v príkazoch programovacieho jazyka. Napríklad spájanie dvoch reťazcov do jedného vo väčšine programovacích jazykov nefunguje v konštantnom čase, ale v čase úmernom ich dĺžkam.

Ak dostávaš odpoveď Zlá odpoveď/WA (wrong answer)

• V prvom rade skontroluj, či výstup vypisuješ presne vo formáte uvedenom v zadaní. (Nemám tam nejaké prázdne riadky navyše? Nechýbajú mi tam nejaké? Nemám navyše medzery na koncoch riadkov? Preklepy vo vypisovaných textoch?)
• Používaš dátový typ s dostatočne veľkým rozsahom? V C/C++ má int 32 bitov (char má 8, short 16, long 32, long long 64).
• Vypisuješ výsledok správne? Korektný formátovací reťazec pre long long je "%lld".
• Inicializuješ (resp. nuluješ) všetky premenné (a najmä polia), ktoré máš v programe?
• Ešte raz si poriadne prečítaj zadanie. Aj ak si si istý, že myšlienka tvojho riešenia je správna.
• Ešte raz poriadne skontroluj svoj program, otestuj ho na čo najviac vstupoch, vrátane okrajových prípadov. (Najmenší možný vstup? Najväčší možný vstup? Vstup špeciálneho tvaru?)
• Naše riešenie je skoro určite správne, ale občas sa aj my zmýlime. Ak si ani po naozaj podrobnom hľadaní nenájdeš chybu a myslíš si, že je chyba asi u nás, kontaktuj nás na discorde (Do správy prosím neuvádzaj svoj kód... sú verejné a my sa k tvojmu kódu vieme dostať)

Ak pri danom vstupe dostaneš IGN (ignored)

Testovanie vašich programov prebieha po sadách. Vstupy tvaru 1.a.in, 1.b.in, ... tvoria jednu sadu. Ak tvoj program vyrieši správne všetky vstupy zo sady, dostaneš bod (niekedy aj viacero bodov za sadu). Ak však riešenie na niektorom vstupe zlyhá (hocijaká chyba TLE, WA, EXC, ...), je jasné, že za danú sadu už bod nedostane a teda sa ďalšie vstupy tejto sady odignorujú. Vďaka tomu sa menej zaťažuje testovač.

Ak si dostal odpoveď Chyba počas kompilácie

• V C++ nezabudni po #include-och uviesť riadok "using namespace std;". Na rozdiel od niektorých (nekorektných) windowsových kompilátorov to g++ nerobí automaticky.
• Nepoužívaj knižnice špecifické pre jeden operačný systém (napr. pascalovská knižnica Dos, C-čkové conio.h a pod.).
• Samozrejme, poriadne si prečítaj výstup z nášho kompilátora. Pravdepodobne náš kompilátor nemá niektorú knižnicu alebo funkciu, ktorú sa snažíš použiť.
• U seba radšej vždy kompiluj so zapnutými warningami, t.j.: gcc/g++ -W -Wall program.c[pp]

Ak si dostal odpoveď Pokus o narušenie bezpečnosti

• Najčastejšia príčina Security exception je, že sa submitnutý program snaží otvoriť nejaký súbor. Tvoj program nesmie čítať ani vytvárať žiadne súbory, vstup má čítať "z klávesnice", výstup písať "na obrazovku".
• Skontroluj, či nepoužívaš zbytočné knižnice alebo knižnice závislé na platforme (napr. riadok uses Crt, DOS; nemá v tvojom programe čo robiť) a či nerobíš nedovolené veci nesúvisiace s riešením úlohy (napr. nevolaj ClrScr;).