Oddaja programa v avtomatsko preverjanje

Programe, ki jih izdelate v okviru seminarske naloge je najbolje oddati v avtomatsko preverjanje. Na strani, kjer ste izbrali probleme, so tudi povezave na "Online Judge", ki implementira avtomatsko preverjanje.

Javansko okolje, ki ga podpira avtomatsko preverjanje, je dokaj omejeno. Na voljo je le nekaj paketov iz standardnega Java API, program pa mora biti narejen na precej specifičen način. Oddajo programov v avtomatsko preverjanje toplo priporočamo, zaradi prej omenjenih razlogov pa ni obvezna.

Originalna navodila ter ostale nasvete lahko najdete na naslovu http://online-judge.uva.es/board/cms_articles.php?cid=1, malo več o programerskih tekmovanjih pa na http://www.acm.org/crossroads/xrds7-5/contests.html.

Prijava

Pred kakršnokoli oddajo progrma moramo biti registrirani. Registracijo opravimo na naslovu http://acm.uva.es/cgi-bin/OnlineJudge?UsersMgr:AddUser. Registracija poteka v več korakih: najprej izberemo geslo, nato moramo na naslednji strani izpolniti nekaj obveznih (ime, priimek, e-mail naslov in država) in nekaj neobveznih podatkov. Med ostalimi izbirami svetujemo izbor "Always to the E-Mail address specified at the top". Na zadnji strani dobimo svojo uporabniško oznako (Your User-ID) ' običajno pet številk in dve črki. Hkrati dobimo na naš elektronski naslov pošto, kjer sta zapisana tako uporabniška oznaka kot tudi geslo (če e-maila ne dobimo, smo najbrž naslov napisali narobe).

Prijavimo se le enkrat. Geslo bomo potrebovali le za spreminjanje naših podatkov, ne pa ob vsaki oddaji. Ob vsaki oddaji bomo morali napisati našo oznako uporabnika in številko naloge, ki jo oddajamo.

Način oddaje

Obstajata dva načina oddaje programa: z elektronsko pošto in s spletnim obrazcem.

Oddaja z elektronsko pošto

Izvorno kodo programa pošljemo z elektronsko pošto na naslov judge@uva.es. Izvorno kodo napišemo v telo sporočila (in ne v dodatek - priponko). V komentarju v programu mora biti vrstica z naslednjimi podatki:

  1. Tekst "@JUDGE_ID:"
  2. uporabniško oznako
  3. številko problema
  4. programski jezik
  5. neobvezen komentar
Ti podatki morajo biti v eni vrsti, ločeni s presledki. Primer: 

// @JUDGE_ID:  44832CX  443  Java

Če naš e-mail program dodaja kakšne vrstice na začetku ali na koncu sporočila (to radi delajo zastonjski e-mail programi), moramo pred prvo vrstico programa dodati vrstico 

@BEGIN_OF_SOURCE_CODE

in za zadnjo vrstico programa še 

@END_OF_SOURCE_CODE

E-mail odpošljemo in (skoraj) takoj dobimo odgovor, da je naš program sprejet v avtomatsko preverjanje, torej nekaj takega: 

Date: Thu, 15 Apr 2004 08:26:49 +0200
From: Valladolid Online Judge 
Message-Id: <200404150626.i3F6Qnw13512@acm.uva.es>
Subject: [417] Program Received: 443
X-Virus-Scanned: by amavisd-new at xenya.si

Dear X Y:

You are trying to solve "Humble Numbers" (problem 443).
I have received and stored your JAVA program. It will be compiled and run
as soon as possible; please be patient waiting for the results...

--
The Online Judge

--------------- The program I'll compile begins here: ---------------
// Program izpiše n-ta ponižna števila
// to so števila, ki so sestavljena iz prafaktorjev 2,3,5 ali 7.
// @JUDGE_ID:  44832CX  443  Java

import java.io.*;
import java.util.*;
class Main {
... izpuščene vrstice
} // class

Kakšno minuto kasneje (morda tudi več) dobimo oceno programa s posebnim e-mailom. Ocena je lahko različnih vrst:

Primer elektronske pošte, ki nam sporoča, da imamo v programu sintaktične napake, je tule: 

Date: Thu, 15 Apr 2004 08:24:25 +0200
From: Valladolid Online Judge 
To:
Subject: [412] Compile Error: 443

Dear :

The compiler couldn't compile your ANSI C/C++ or GNU Pascal/Java program.

[Notes: - Select C, C++, JAVA or PASCAL in the @JUDGE_ID field, to ensure that
          I'll use the proper compiler. Place a 'program...' sentence in Pascal.
          Note that entry point in Java is a 'main' function in a 'Main' class.
        - Do not use more than 1024 characters per line, or 40,000 bytes per
          program, if you are submitting your programs by E-Mail.
        - Do not use '//' comments except in C++ programs [And Note that this
          is not Borland C or Turbo Pascal!].
        - Some mail tools reformat your text or the standard mail headers.
          I compiled the lines I resent you in the "Program Received" message.
          (if your mail system adds extra lines to your letter, please include
          a "@end_of_source_code" string after the last source code line).

Here are the compiler error messages:

02458403_24.java: In class `Main':
02458403_24.java: In method `main(java.lang.String[])':
02458403_24.java:40: Can't search method `sort' in package `Arrays'.
     Arrays.sort(hn);
     ^
1 error

--

PS: Check the board at http://acm.uva.es/board/

The Online Judge (Linux acm.uva.es 2.4.18-27.7.x i686)
Judge software version 2.8 [http://acm.uva.es/problemset/]
Thu Apr 15 06:24:25 UTC 2004

Bistven del sporočila, ki pravi, da program ni dal pravilnih rezultatov, je tule: 

Subject: [417] Wrong Answer: 443
...
Your program has not solved the problem. It ran during 1.500 seconds.
...

Bistven del sporočila, ki pravi, da je program predolgo računal, je tule: 

Subject: [421] Time Limit Exceeded: 443
...
Your program has used more time (10.084 seconds) than the maximum allowed
for this problem by this judge (10 seconds).
...

Bistven del sporočila, ki pravi, da je program v redu, je tule: 

Subject: [425] Accepted: 443
...
Your JAVA program has solved Ok the problem 443 (Humble Numbers)
in 1.180 seconds using as much as 2680 kbytes of virtual memory.
Congratulations!
...

Oddaja s spletnim obrazcem
Izvorno kodo programa oddamo v preverjanje na naslovu http://acm.uva.es/problemset/submit.php. V obrazcu moramo vpisati:
  1. uporabniško oznako
  2. številko problema
  3. programski jezik
  4. neobvezen komentar

V tekstualno okno vpišemo izvorno kodo našega programa (navadno s copy/paste iz urejevalnika). Lahko pa namesto tega tudi izberemo datoteko, ki jo želimo odposlati.

Če smo si nastavili obveščanje z e-mailom (kot je bilo svetovano zgoraj ob prijavi), dobimo rezultate z enakimi e-maili, kot so bili opisani pri oddaji programa prek elektronske pošte.

Če si nismo nastavili obveščanja z e-mailom, moramo sami spremljati status oddaje, kot je to opisano na strani za oddajo.

Priprava programa

Navajeni smo, da je javanski program javen razred, v katerem se izvede metoda main. V oddanih programih ne sme biti javnih razredov, zato mora biti glavni program v ne-javnem razredu z imenom Main. V isti datoteki so lahko še drugi (ne-javni) razredi, če jih potrebujemo. Ker ne oddajamo datoteke, se seveda ni treba ukvarjati s tem, da bi morala biti datoteka imenovana enako kot javen razred v njej.

Tak program je uporaben tudi lokalno, le da morajo biti vsi razredi v eni datoteki, saj prevajalnik ne zna najti datoteke po imenu razreda.

Morda najbolj nadležna omejitev je pri branju podatkov iz standardnega vhoda. Navajeni smo, da podatke beremo s približno tako strukturo: 

BufferedReader vhod = new BufferedReader(new InputStreamReader(System.in));
while (true) {
  String vrsta = vhod.readLine();
  if (vrsta == null) break;
  // nekaj naredimo z vhodno vrstico v spremenljivki vrsta
}

Zaradi omejitev v modulu java.io, ne moremo uporabiti System.in kot argumenta. Običajno si zato naredimo svojo metodo za branje vrstic iz standardnega vhoda, recimo takole: 

  public static String readLn () {
    byte[] line = new byte[100];
    int len = 0, ch = -1;
    try {
      while (true) {
        ch = System.in.read();                   // naslednji znak
        if ((ch < 0) || (ch == '\n')) break;     // konec vrste?
        if (len >= line.length) {                // podaljšamo tabelo
          byte[] line1 = new byte[line.length*2];
          System.arraycopy(line,0,line1,0,line.length);
          line = line1;
        }
        if (ch != '\r') line[len++] = (byte)ch;  // spustimo CR za Windows
      }
    }
    catch (IOException ee) { return null; }      // napaka
    if ((ch < 0) && (len == 0)) return null;     // konec vhoda
    return new String(line,0,len);               // normalna vrsta
  } // readLn

// ...
while (true) {
  String vrsta = readLine();
  if (vrsta == null) break;
  // nekaj naredimo z vhodno vrstico v spremenljivki vrsta
}

Za avtomatsko preverjanje je dodatna zahteva tudi poseben komentar, kjer je določena naša uporabniška oznaka in številka problema, katerega rešitev pošiljamo. V enem od komentarjev v programu moramo navesti naslednje podatke (v tem vrstnem redu):

  1. Tekst "@JUDGE_ID:"
  2. uporabniško oznako
  3. številko problema
  4. programski jezik
  5. neobvezen komentar
Ti podatki morajo biti v eni vrsti, ločeni s presledki. Primer: 

// @JUDGE_ID:  44832CX  443  Java

V primeru oddajanja s spletnim obrazcem ta komentar ni obvezen, ampak ne škodi.

Ostale omejitve

Čas izvajanja programa je omejen, zato moramo pogosto malce razmisliti o učinkovitosti postopka.

Mnogih modulov standardnega javanskega APIja ni, zato je včasih namesto klicanja metod iz knjižnice treba napisati kako metodo po svoje.

Primer

Program iz problema 443 (tisti, ki je obdelan v primeru) smo oddali v avtomatsko preverjanje. Vnaprej jasni popravki programa so naslednji:

Tako preurejen program bi bil takšen (spremembe so poudarjene): 

// Program izpiše n-ta ponižna števila
// to so števila, ki so sestavljena iz prafaktorjev 2,3,5 ali 7.
// @JUDGE_ID:  44832CX  443  Java

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

class Main {

  final static int maxI = 5842;      // do kje znamo izpisovati ponižna števila

  public static String readLn () {
    byte[] line = new byte[100];
    int len = 0, ch = -1;
    try {
      while (true) {
        ch = System.in.read();                   // naslednji znak
        if ((ch < 0) || (ch == '\n')) break;     // konec vrste?
        if (len >= line.length) {                // podaljšamo tabelo
          byte[] line1 = new byte[line.length*2];
          System.arraycopy(line,0,line1,0,line.length);
          line = line1;
        }
        if (ch != '\r') line[len++] = (byte)ch;  // spustimo CR za Windows
      }
    }
    catch (IOException ee) { return null; }      // napaka
    if ((ch < 0) && (len == 0)) return null;     // konec vhoda
    return new String(line,0,len);               // normalna vrsta
  } // readLn

  public static void main (String[] mmm) throws Exception {
//    BufferedReader vhod = new BufferedReader(new InputStreamReader(System.in));
    while(true) {           // Neskoncna zanka, ustavili jo bomo z ukazom break
//      int nn = Integer.parseInt(vhod.readLine().trim());   // Preberemo podatek
      int nn = Integer.parseInt(readLn().trim());          // Preberemo podatek
      if (nn == 0) break;    // Podatek 0 pomeni konec podatkov, ustavimo zanko
      if ((1 <= nn) && (nn <= maxI)) {
        System.out.println("The " + nn + koncnica(nn) + " humble number is " +
                           humble_number(nn) + ".");
      }
      else {
        System.out.println("Število "+ nn +" ni iz intervala [1, "+maxI+"].");
      }
    }
  } // main

  // Metoda vrne končnico vrstilnega števnika.
  public static String koncnica(int nn) {
    nn = nn % 100;                         // zanimivi sta le zadnji dve števki
    if ((nn >= 11) && (nn <= 13)) return "th";         // 11, 12, 13 so posebej
    nn = nn % 10;                           // sedaj odloca le še zadnja števka
    if (nn == 1) return "st";
    if (nn == 2) return "nd";
    if (nn == 3) return "rd";
    return "th";
  } // koncnica

  // Metoda vrne n-to ponižno število.
  public static int humble_number(int nn) {
    if (nn == 1) return 1;
    int humble = 0;
    int kandidat = 2;
    int kateroPon = 1;
    while (kateroPon < nn) {                           // nismo še nasli n-tega
      int n_st = kandidat;
      while ( n_st % 2 == 0) n_st = n_st / 2;        // dokler obstaja faktor 2
      while ( n_st % 3 == 0) n_st = n_st / 3;                       // faktor 3
      while ( n_st % 5 == 0) n_st = n_st / 5;                       // faktor 5
      while ( n_st % 7 == 0) n_st = n_st / 7;                       // faktor 7
      if ( n_st == 1) {                  // ni drugh faktorjev razen 2, 3, 5, 7
        humble = kandidat;                           // zato je število ponižno
        kateroPon++;
      }
      kandidat++;
    }
    return humble;
  } // humble_number

} // class

Klub spremembi javnosti razreda in spremembi imena razreda, lahko tak program testiramo tudi na svojem računalniku: prevajamo ga običajno (tu nimamo sicer običajnih težav zaradi neenakega imena datoteke in imena razreda, ker razred ni javen). Prevedeni razred bo na datoteki Main.class, ne glede na ime izvorne datoteke. Prevedeno .class datoteko preprosto poženemo z ukazom 

> java Main
1
The 1st humble number is 1.
2
The 2nd humble number is 2.
3
The 3rd humble number is 3.
10
The 10th humble number is 10.
100
The 100th humble number is 450.
101
The 101st humble number is 480.
102
The 102nd humble number is 486.
1000
The 1000th humble number is 385875.
0

>

Ko smo program preizkusili na svojem računalniku, smo program oddali, tako kot je navedeno zgoraj. Po pričakovanju smo dobili odgovor, da je program predolgo računal: 

[690] Time Limit Exceeded: 443
...
Your program has used more time (10.084 seconds) than the maximum allowed
for this problem by this judge (10 seconds).
...

To bi morali vedeti že zaradi čakanja na rezultat o 1000. pohlevnem številu (5842. pohlevnega števila nismo dočakali).

Da bi program torej zares oddali v avtomatsko preverjanje, ga moramo pospešiti. Ideja, kako bomo to storili, je zapisana že v primeru oddaje seminarske naloge. Vseh 5842 pohlevnih števil si bomo izračunali vnaprej, tako da bomo v štirih zankah šli čez vse potence 2, 3, 4 in 7 in si v tabelo spravljali njihove produkte. Tabelo pohlevnih števil bomo le še posortirali po velikosti, da bomo lahko potem takoj odgovarjali na vprašanja o pohlevnem številu z določeno zaporedno številko.

Zapišimo del programa, s katerim bomo naračunali tabelo: 

// deklaracije
  final static int maxN = 2000000000; // največje število, ki nas zanima
  final static int maxI = 5842;       // število pohlevnih števil do tam

  static int[] hn = new int[maxI+1];  // tabela pohlevnih števil
  static int hnL = 0;                 // do kje je polna

// na začetku metode main

    for (long p2 = 1; p2 <= maxN; p2 *= 2)
      for (long p3 = 1; p2*p3 <= maxN; p3 *= 3)
        for (long p5 = 1; p2*p3*p5 <= maxN; p5 *= 5)
          for (long p7 = 1; p2*p3*p5*p7 <= maxN; p7 *= 7) {
            long nn = p2*p3*p5*p7;
            if (nn <= maxN) hn[hnL++] = (int)nn;
          }
    Arrays.sort(hn);

V zankah smo morali uporabiti števce tipa long, ker pogoji naloge zahtevajo, da gremo takorekoč do meje obsega int: prvi naslednja vrednost vsakega števca bi že prekoračila obseg int. Za sortiranje smo uporabili statično metodo sort iz razreda Arrays.

Metode humble_number iz originalnega programa ne potrebujemo več, le stavek 

        System.out.println("The " + nn + koncnica(nn) + " humble number is " +
                           humble_number(nn) + ".");

moramo popraviti v 

        System.out.println("The " + nn + koncnica(nn) + " humble number is " +
                           hn[nn] + ".");

Program smo preizkusili na svojem računalniku in deluje kot strela. Po oddaji programa v avtomatsko preverjanje pa žal dobimo 

Subject: [412] Compile Error: 443

The compiler couldn't compile your ANSI C/C++ or GNU Pascal/Java program.

[Notes: - Select C, C++, JAVA or PASCAL in the @JUDGE_ID field, to ensure that
          I'll use the proper compiler. Place a 'program...' sentence in Pascal.
          Note that entry point in Java is a 'main' function in a 'Main' class.
        - Do not use more than 1024 characters per line, or 40,000 bytes per
          program, if you are submitting your programs by E-Mail.
        - Do not use '//' comments except in C++ programs [And Note that this
          is not Borland C or Turbo Pascal!].
        - Some mail tools reformat your text or the standard mail headers.
          I compiled the lines I resent you in the "Program Received" message.
          (if your mail system adds extra lines to your letter, please include
          a "@end_of_source_code" string after the last source code line).

Here are the compiler error messages:

02458403_24.java: In class `Main':
02458403_24.java: In method `main(java.lang.String[])':
02458403_24.java:40: Can't search method `sort' in package `Arrays'.
     Arrays.sort(hn);
     ^
1 error

ker javansko okolje avtomatskega preverjanja ne podpira razreda Arrays (vsaj ne v celoti).

Zato bomo morali sortiranje napisati v naš program kar na roke. Dodamo metodo 

  public static void sort(int[] tbl) {
  // bubble sort
    int kn = tbl.length-1;                   // konec nesortiranega dela tabele
    while (kn > 0) {
      int nkn = 0;                              // nov konec nesortiranega dela
      for (int ii = 0; ii < kn; ii++) {
        // če je potrebno, zamenjamo sosednja elementa
        if (tbl[ii] > tbl[ii+1]) {
          int tt = tbl[ii]; tbl[ii] = tbl[ii+1]; tbl[ii+1] = tt;
          nkn = ii;                  // označimo, da je vsaj to tu nesortirana
        }
      }
      kn = nkn;
    }
  } // sort

in namesto Arrays.sort(hn) kličemo le sort(hn). Ob ponovni oddaji zlahka opravimo avtomatsko preverjanje in dobimo sporočilo 

Subject: [425] Accepted: 443
...
Your JAVA program has solved Ok the problem 443 (Humble Numbers)
in 1.180 seconds using as much as 2680 kbytes of virtual memory.
Congratulations!
...

Za radovedneže je torej celoten uspešno oddan program tak: 

// Program izpiše n-ta ponižna števila
// to so števila, ki so sestavljena iz prafaktorjev 2,3,5 ali 7.
// @JUDGE_ID:  44832CX  443  Java

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

class Main {

  public static String readLn () {
    byte[] line = new byte[100];
    int len = 0, ch = -1;
    try {
      while (true) {
        ch = System.in.read();                   // naslednji znak
        if ((ch < 0) || (ch == '\n')) break;     // konec vrste?
        if (len >= line.length) {                // podaljšamo tabelo
          byte[] line1 = new byte[line.length*2];
          System.arraycopy(line,0,line1,0,line.length);
          line = line1;
        }
        if (ch != '\r') line[len++] = (byte)ch;  // spustimo CR za Windows
      }
    }
    catch (IOException ee) { return null; }      // napaka
    if ((ch < 0) && (len == 0)) return null;     // konec vhoda
    return new String(line,0,len);               // normalna vrsta
  } // readLn

  public static void sort(int[] tbl) {
  // bubble sort
    int kn = tbl.length-1;                   // konec nesortiranega dela tabele
    while (kn > 0) {
      int nkn = 0;                              // nov konec nesortiranega dela
      for (int ii = 0; ii < kn; ii++) {
        // če je potrebno, zamenjamo sosednja elementa
        if (tbl[ii] > tbl[ii+1]) {
          int tt = tbl[ii]; tbl[ii] = tbl[ii+1]; tbl[ii+1] = tt;
          nkn = ii;                  // označimo, da je vsaj to tu nesortirana
        }
      }
      kn = nkn;
    }
  } // sort

  final static int maxN = 2000000000; // največje število, ki nas zanima
  final static int maxI = 5842;       // število pohlevnih števil do tam

  public static void main (String[] args) {

    int[] hn = new int[maxI+1];  // tabela pohlevnih števil
    int hnL = 0;                 // do kje je polna

    for (long p2 = 1; p2 <= maxN; p2 *= 2)
      for (long p3 = 1; p2*p3 <= maxN; p3 *= 3)
        for (long p5 = 1; p2*p3*p5 <= maxN; p5 *= 5)
          for (long p7 = 1; p2*p3*p5*p7 <= maxN; p7 *= 7) {
            long nn = p2*p3*p5*p7;
//            System.out.println(p2+" "+p3+" "+p5+" "+p7+" "+nn+" "+hnL);
            if (nn <= maxN) hn[hnL++] = (int)nn;
          }
//  Arrays.sort(hn);
    sort(hn);

    while (true) {
      int nn = Integer.parseInt(readLn().trim());
      if (nn == 0) break;
      if ((1 <= nn) && (nn <= maxI))
        System.out.println("The "+ nn + koncnica(nn)+" humble number is "+ hn[nn] +".");
      else
        System.out.println("Stevilo "+ nn +" ni iz intervala [1, 5842]!");
    }
  } // main

  // Metoda vrne končnico vrstilnega števnika.
  public static String koncnica(int nn) {
    nn = nn % 100;                         // zanimivi sta le zadnji dve števki
    if ((nn >= 11) && (nn <= 13)) return "th";         // 11, 12, 13 so posebej
    nn = nn % 10;                           // sedaj odloca le še zadnja števka
    if (nn == 1) return "st";
    if (nn == 2) return "nd";
    if (nn == 3) return "rd";

    return "th";
  } // koncnica

} // class