• 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 Pascale/Jave/C# použite writeln/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 Debian 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). Pre jazyky používame kompilátory s nasledovnými nastaveniami:

  • C: gcc -static -O2 -std=gnu99 -lm riesenie.c
  • C++: g++ -static -O2 -std=gnu++17 riesenie.cc
  • Pascal: fpc -Sg -O2 riesenie.pas
  • Java: javac riesenie.java
  • C#/Mono: mcs riesenie.cs

Z týchto nastavení vyplýva napr., že v C++ podporujeme novinky zo štandardu C++11 a že kód optimalizujeme, teda tvoj kód v C/C++/Pascal-e môže u nás v niektorých prípadoch bežať o dosť rýchlejšie ako u teba. Používame tieto verzie kompilátorov:

  • C/C++: GCC 8.3.0
  • Pascal: freepascal 3.0.4
  • Java: openjdk 11.0.14
  • C#: mono 5.18.0
  • Python: python 3.10
  • Haskell: ghc 8.4.4

Príklady korektných programov

Ako riešenie úlohy "na vstupe je pár malých celých čísel na dvoch riadkoch, spočítajte ich a vypíšte ich súčet" by sme uznali napr. nasledujúce programy:

C

#include <stdio.h>

int main(void) {
  int x, TOTAL=0;
  while (scanf("%d",&x)==1) TOTAL += x;
  printf("%d\n",TOTAL);
  return 0;
}

C++

#include <iostream>
using namespace std;

int main(void) {
  int x, TOTAL=0;
  while (cin >> x) TOTAL += x;
  cout << TOTAL << endl;
  return 0;
}

Pascal

var x, TOTAL : longint;

begin
   TOTAL := 0;
   while not eof do begin
      readln(x);
      TOTAL := TOTAL + x;
   end;
   writeln(TOTAL);
end.

Java

Testovanie Javy je trochu komplikovanejšie, keďže pri kompilácii súbory premenúvame. Aby všetko fungovalo ako má, zdroják musí obsahovať práve jednu vonkajšiu classu a táto classa nesmie byť public.

Spustená bude metóda main dotyčnej vonkajšej classy. (Vovnútri vonkajšej classy môžete deklarovať iné classy, ak chcete/potrebujete.)

Ďalej, zdrojový kód v Jave nesmie byť deklarovaný ako súčasť nejakého package.

import java.io.*;
import java.util.*;

class WholeProgram {
  public static void main(String args[])   {
    String Line;
    int TOTAL = 0;
    try     {
      BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
      while (true) {
        Line = stdin.readLine();
        if (Line == null) break;
        StringTokenizer st = new StringTokenizer(Line);
        int x = Integer.parseInt(st.nextToken());
        TOTAL += x;
      }
    }
    catch (EOFException e) { }
    catch (IOException e) { }
    System.out.println(TOTAL);
  }
}

C#/Mono

using System;

class MojeRiesenie {
  public static void Main() {
    int TOTAL = 0;
    while (true) {
      string Line = Console.ReadLine();
      if (Line == null) break;
      TOTAL += int.Parse( Line );
    }
    Console.WriteLine("{0}", TOTAL);
  }
}

Python

a = int(input())
b = int(input())
print( a+b )

Haskell

Funkcia, ktorú máme spustiť, sa musí volať main

main :: IO ()
main = do
  a <- getLine
  b <- getLine
  print (sucet (read a) (read b))

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é v časti textu o kúsok ďalej.

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 samozrejme kontaktovať v diskusii pod príkladom alebo na maili ksp-info@ksp.sk . Predtým ale vyskúšaj, či ti nepomôže jedna z nasledujúcich rád:

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 je momentálne rovnaký pre všetky programovacie jazyky a nastavujeme ho 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). V Pascale má integer len 16 bitov. Používaj longint, kde sa len dá. Pokiaľ ti 32 bitov nestačí a potrebuješ až 64 bitov, tak použi int64.
  • 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 v diskusii pod príkladom (Do diskusie pod príkladom prosím neuvádzaj svoj kód.. diskusie 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] fpc -Cr -Ct -Co -vew program.pas
  • Vo FreePascale nepoužívaj vnorené komentáre, t.j. napríklad kód { writeln('Test'); {!!!!!} nie je v poriadku, pri štandardnom nastavení ho FreePascal neskompiluje, lebo si myslí, že aj za znakom } ešte pokračuje komentár.

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;).

Čas poslednej úpravy: 7. október 2022 23:06