PO-finalen 2012

Snabblänkar:
Regler för POF-tävlingen
Läsa från fil
Regler för KATT-tävlingen (NYTT)
Nyttiga tips

Liksom förra året består uttagningen till IOI och BOI består av två deltävlingar:

• En traditionell PO-final (POF) på berörda skolor: 2 eller 6 mars (skolan avgör med avseende på sportlovet).
• En internet-tävling, KATT (klur- och algoritmtalangtävling), som går över en helg, 16-20 mars (exakt utsträckning är preliminär).

Observera dock att segraren i den traditionella PO-finalen fortfarande räknas som svensk gymnasiemästare i programmering. Vi har full förståelse för att alla inte kan/vill delta i KATT-tävlingen som dessutom är mer restriktiv vad gäller språk och utvecklingsmiljöer.

Uppgifterna i internet-tävlingen kommer att vara betydligt svårare än i PO-finalen, men å andra sidan kommer tidspressen att vara mindre, så att man har förutsättningar för att tänka ut och implementera effektiva algoritmer av den typ som krävs i de internationella tävlingarna. Syftet med att införa denna nya typ av tävling var att överbrygga glappet mellan PO och de internationella tävlingarna, vilket många upplever som enormt. Samt naturligtvis att sporra finalisterna till en djupdykning i algoritmernas underbara värld.

Eftersom vi (naturligtvis) använder Kattis kommer de tillåtna språken i KATT-tävlingen begränsas till C, C++, Pascal och Java, medan alla språk är tillåtna i POF. Observera dock att endast C/C++ och Pascal kommer att vara tillåtet i IOI 2012, så vi rekommenderar att satsa på dessa om man ändå måste lära sig ett nytt språk.

Poängberäkning: Poängen från POF och KATT läggs helt enkelt ihop.

Regler för den traditionella PO-finalen 2012

• Tävlingen äger rum den 2 eller 6 mars (skolan avgör med avseende på sportlovet) på de skolor som har kvalificerade elever. Tävlingstiden är sex timmar effektiv tid.
• Tävlingen består av 6-7 uppgifter som samtliga ska lösas genom ett datorprogram.
• Uppgifterna ska lösas i valfritt programmeringsspråk. Du får till och med byta språk mellan olika uppgifter.
• Tävlingsbidragen lämnas i form av programmets källkod (i en eller flera filer). Inkludera en kommentar i källkoden med den fullständiga kommandoraden för att kompilera programmet, eller om du använder ett interpreterande språk (t.ex. Python eller PHP) vilken version programmet är skrivet för. Om programmet är utvecklat i Windows-miljö ska även EXE-filen bifogas.
• I varje källkodsfil ska finnas en kommentar innehållande namn och skola.
• Lösningarna poängsätts med max 5 poäng per uppgift. Fem tester, med varierande krav hos ditt program, kommer att göras vid rättningen (undantag kan finnas). Möjlighet till delpoäng finns om programmet klarar endast en del av dessa tester. Ingen närmare bedömning av programkoden görs.
• Ingen test av indata behöver göras. Alla testdata följer de specifikationer som givits i uppgiften. Om det trots detta, vid rättningen, uppstår exekveringsfel vid körning av programmet bedöms programmet som felaktigt för det testexemplet.
• Samtliga uppgifter leder fram till program vars exekveringstid normalt bör understiga 5 sekunder på en modern dator. Skulle en lösning leda fram till ett program vars exekveringstid överskrider denna tid bedöms programmet med 0 poäng för detta testexempel.
• Du kommer att få tillgång till de indatafiler som används i uppgiftens exempel.
• Deltagandet är individuellt vilket bland annat innebär att inget utbyte av idéer eller filer får ske under tävlingstiden. Självklart får din dator inte vara kopplad till vare sig internt eller externt nät.
• Hjälpmedel: Valfritt skriftligt material samt de manualer som är installerade på datorn. Däremot är det inte tillåtet att söka information på eller kommunicera via internet. Räknedosa är tillåten.
• I flera av uppgifterna ska indata läsas från en vanlig ASCII-fil. Se till att du behärskar den tekniken! (se nedan)
• Du behöver också veta hur du gör för att hantera och skriva ut stora heltal (64-bitars tal, d.v.s. med belopp upp till 4E18) i det språk du använder.
• Tävlingsbidragen ska läggas i roten på utdelad diskett eller i en av läraren angiven hårddiskkatalog. Filerna ska döpas till uppg1...uppg7 med passande filtillägg. Ingen hänsyn tas till andra filer. Var noga med vilka filer du lämnar in, så att du säkert lämnar in den korrekta versionen av ditt program.

Att läsa från ASCII-fil

Indatan för en uppgift kan ges på två sätt (framgår av problemtexten). Dels genom en dialog med användaren, som i (det traditionella) kvalet. Men oftast ges indata i en ASCII-fil. Filen består av flera rader där varje rad kan innehålla flera tal eller strängar. Dessa åtskiljs alltid med ett blanksteg. Det lättaste sättet att läsa indata är därför att använda funktioner som hanterar indatan som en uppsättning tokens åtskilda av whitespace, som kan vara såväl blanksteg som radbrytningar.

Vi ger här exempel på hur man i fem språk kan läsa in följande indata från filen fil.txt:
4 6
3.22 Text


OBS! Denna förteckning är ny och ska betraktas som en möjlig hjälp. Fel kan förekomma. Du måste testa detta själv innan tävlingen.

C

   #include <stdio.h>
   ...
   int a1, a2;
   char word[100];
   double d;
   FILE *fil=fopen("fil.txt", "rt");
   fscanf(fil, "%d %d", &a1, &a2);
   fscanf(fil, "%lf %s", &d, word);

C++

   #include <iostream>
   using namespace std;
   ...
   int a1, a2;
   char word[100];
   double d;
   ifstream fil("fil.txt");
   fil >> a1 >> a2;
   fil >> d >> word;

Java (J2SE)

   import java.util.Scanner;
   import java.io.File;
   ...
   Scanner sc=null;
   try {
     sc = new Scanner(new File("fil.txt"));
   } catch (Exception e) { ... }
   int a1=sc.nextInt(), a2=sc.nextInt();
   double d=sc.nextDouble();
   String word=sc.next();

Pascal

   VAR
   infile : Text;
   a1, a2 : Integer;
   d : Double;
   word : string[100];
   ...
   Assign(infile, 'fil.txt');
   Reset(infile);
   Readln(infile, a1, a2);
   Readln(infile, d, word);
   Close(infile);

Basic

   Dim s,word As String
   Dim a1, a2 As Integer
   Dim d As Double
   Dim sar() As String
   ...
   Open "fil.txt" For Input As #1
   Line Input #1, s
   sar = Split(s," ")
   a1 = val(sar(0))
   a2 = val(sar(1))
   Line Input #1, s
   sar = Split(s," ")
   d = val(sar(0))
   word = sar(1)

Nyttiga tips

Denna lista gäller främst PO-finalen. För KATT rekommenderas vår träningssajt där du kan lära dig mer om olika algoritmer. Och att träna på gamla tävlingar, se vår länksamling.

• Var beredd på att finalen liknar kvalet, utom att uppgifterna är svårare. Tonvikten ligger lite mer på att tänka ut en effektiv algoritm än på att bara skriva ett korrekt program, även om det förstås alltid är viktigast att programmet fungerar. Rent programmeringstekniskt är det bara en sak som tillkommer, du måste kunna läsa indata till programmet från en vanlig textfil (se ovan).
• Läs igenom kommentarerna och titta på lösningarna till kvaluppgifterna. Du hittar allting här. Du kan alltid lära dig några knep som du har nytta av.
• Se till att du förstår hur man använder rekursiva funktioner. En introduktion finns här.
• Träna på gamla problem! Detta är det bästa sättet att förbereda sig. Många av dem kan du lösa med det automatiska rättningsprogrammet Kattis.
• Kolla in de teoriavsnitt som rekommenderas på sidan Inför PO.
• Ta för vana att testa ditt program med något mer indata än det givna så att du ser att det fungerar. På det sättet kan man hitta småbuggar som man slipper gräma sig över när man får resultatet.
• Kontakta oss om du undrar över något.