PilsProg 2009

Výsledky kvalifikace

PříjmeníJménoSplněných úlohČasFinále
MatějkaJan628.1208postupuje do finále
TesařKarel699.6989postupuje do finále
KlejchOndřej6137.0622postupuje do finále
JelenJakub6138.7064postupuje do finále
KrálJan6204.9897postupuje do finále
MacekDavid6209.5597postupuje do finále
JuraszekAdam6452.2028postupuje do finále
BilanskýMichal61767.2150postupuje do finále
ZikmundMartin63014.2842postupuje do finále
MelkaMartin5328.0256postupuje do finále
MohelníkováLucie5465.5194postupuje do finále
PřecechtělMartin5597.9550postupuje do finále
PalíšekLuboš51976.4061postupuje do finále
JaníčekDavid52147.8644postupuje do finále
NovotnáJitka53707.0092postupuje do finále
KovaříkLuboš4955.3269postupuje do finále
VazačTomáš41191.7183postupuje do finále
NovotnýJan41550.5961postupuje do finále
KlejnaTomáš41689.5169postupuje do finále
KováříkKarel41941.1297postupuje do finále
LockenbauerKarel31127.5017
SmolíkTomáš31384.3531
MalíkZdeněk253.1639
KratinaTomáš2199.2075
KodýdkováDana2739.2506
ThurnvaldMatěj2741.7206
MojzíkMichal16.9856
VašíčekVojtěch1271.4561
KlášterkováJana1285.5767
MarvalováJindra1285.6097
vondrasekvasek1334.7917
KlejnaTomáš1404.8039
KubátJan1502.4122
HavlíčkováVeronika1502.7122
FaltínTomáš1850.2897

Výsledky finále

PříjmeníJménoSplněných úlohČas
JuraszekAdam34.4267
KrálJan21.7842
MacekDavid22.2125
MatějkaJan22.4717
BilanskýMichal22.6561
TesařKarel23.6136
MelkaMartin23.7406
JelenJakub23.9839
JaníčekDavid24.4142
KlejchOndřej24.9822
KovaříkLuboš10.7239
ZikmundMartin11.0028
MohelníkováLucie11.1433
PřecechtělMartin11.5911
KováříkKarel11.6947
NovotnáJitka12.9442
NovotnýJan00
PalíšekLuboš00

Vysvětlivky:
Čas vyřešení je počítán v hodinách od zveřejnění úlohy

A jaké bylo finále?

Finále začíná ...

Harmonogram PilsProg 2009

Ilustrační úlohy:

NázevČísloÚspěšných řešitelů
AxB070435
Pascalův trojúhelník070310
Největší ze tří celých čísel080611
AplusB080510

Kvalifikační úlohy:

NázevOznačeníÚspěšných řešitelů
Průvodce turistů092612
Fragment092313
Obarvení grafu092519
Hádanka092434
Dvojice prvočísel092222
Chaos Sort092127

Finálové úlohy:

NázevOznačeníÚspěšných řešitelů
Poklad09301
Zakázané město09281
Tržiště092914
Eulerova prvočísla092711

Kvalifikační úlohy - řešení:

Nejprve je stručně popsán způsob, jakým je možno úlohu řešit. Jak úlohy řešili soutěžící, je ukázáno na vybraných příkladech zdrojových kódů odevzdaných soutěžních úloh.

Chaos Sort

Vytvoříme celočíselné pole, ve kterém si označíme pozice sudých např. 0 a pozice lichých čísel 1. Pole seřadíme vzestupně. Pak ho procházíme a pomocí dvou indexů (ukazatelů) vkládáme na odpovídající pozici do pole nul a jedniček vždy liché číslo odzadu a sudé číslo odpředu.

Příklad zdrojového kódu:

package main; import java.util.Scanner; public class Chaossort { static Scanner sc = new Scanner(System.in); static int nactiCislo() { int i = sc.nextInt(); return i; } public static void main(String[] args) { String text = ""; int pocet = nactiCislo(); int vsechnaCisla[]; vsechnaCisla = new int[pocet]; for (int i = 0; i < pocet; i++) { vsechnaCisla[i] = nactiCislo(); } for (int i = 0; i < pocet; i++) { for (int j = 0; j < pocet; j++) { if (vsechnaCisla[i] % 2 == 0 && vsechnaCisla[j] % 2 == 0) { if (vsechnaCisla[i] < vsechnaCisla[j]) { int mezi = vsechnaCisla[i]; vsechnaCisla[i] = vsechnaCisla[j]; vsechnaCisla[j] = mezi; } else { continue; } } else if ((vsechnaCisla[i] % 2 == 1 || vsechnaCisla[i] % 2 == -1) && (vsechnaCisla[j] % 2 == 1 || vsechnaCisla[j] % 2 == -1)) { if (vsechnaCisla[i] > vsechnaCisla[j]) { int mezi = vsechnaCisla[i]; vsechnaCisla[i] = vsechnaCisla[j]; vsechnaCisla[j] = mezi; } } } } for (int i = 0; i < pocet; i++) { if (i == pocet - 1) { text += vsechnaCisla[i] + ""; } else { text += vsechnaCisla[i] + " "; } } System.out.print(text); } }

Dvojice prvočísel

Ze zadání víme, že nebudeme potřebovat hodnotu větší než 80000. Proto nejprve vytvoříme logické pole o tomto rozměru, do kterého vložíme hodnotu true pro přirozená čísla větší než 1 a hodnotu false pro 0 a 1. Následně k označení prvočísel použijeme Eratosthenovo síto. Pro prvočíselné dvojice krom (3,5) platí (6k-1, 6k+1), kde k je přirozené číslo. Procházíme tudíž násobky čísla 6 zmenšené a zvětšené o 1 a ověřujeme v poli prvočísel, zda jsou to prvočísla. Pokud ano, zapíšeme menší z nich do nového pole dvojic o velikosti 1000 celočíselného typu. Takto pole postupně zaplníme. Tím připravíme tabulku všech potřebných dvojic a následuje čtení a vyhledání požadované dvojice, protože index v poli dvojic reprezentuje o 1 zmenšené pořadí (od nejmenších). Pro každou vstupní hodnotu se tak již opakuje jen výpis. Výpočet se provádí pouze jedenkrát. Tuto variantu je výhodné použít v případě velkého počtu testování, tj. pro rozsáhlý testovací soubor dat.

Příklad zdrojového kódu:

program dvojice; var a : array[0..80000] of boolean; i, j, p, s : longint; t : string; b : array[0..1000] of longint; begin for i := 0 to 80000 do a[i] := true; a[1] := false; for i := 2 to 40000 do if (a[i] = true) then begin j := 2 * i; while (j < 80000) do begin a[j] := false; j := j + i; end; end; s := 0; i := 3; repeat readln(t); if (t <> '') then begin val(t, p); while (s < p) do begin if ((a[i] = true) and (a[i - 2] = true)) then begin s := s + 1; b[s] := i - 2; end; i := i + 1; end; writeln('(', b[p], ', ', (b[p] + 2), ')'); end; until (t = '') end.

Fragment

Z fragmentu kódu zjistíme, že je-li:

    q*2 >= p
          
potom řešení neexisuje, jinak řešení existuje a je následující:
    u = ((p-1)/q)*q
    v = ((p-1)/q - 1) * q
          

Příklad zdrojového kódu:

import java.util.Scanner; public class Frag { public static void main(String args[]) { Scanner sc = new Scanner(System.in); int u, v, p, q; p = sc.nextInt(); q = sc.nextInt(); if(p > 2*q) { u = (p -1) - (p -1)%q; v = u - q; System.out.println(u+" "+v); } else { System.out.print("Reseni neexistuje."); } } }

Hádanka

Otestujeme, je-li první zadaná hodnota větší než druhá (součet, rozdíl). Potom

     x =(s-r)/2
     y =(s+r)/2
          
a jsou-li výsledkem celá čísla, je nutno je uspořádat vzestupně. Pokud x, y nejsou celá čísla, vypíšeme, že došlo k chybě.

Příklad zdrojového kódu:
program prjHadanka; var pocet : integer; indexRadku : integer; soucet : integer; rozdil : integer; vymena : integer; dvojnasobek : integer; existuji : boolean; prvniCislo, druheCislo : integer; begin readln( pocet ); for indexRadku := 1 to pocet do begin read( soucet ); readln( rozdil ); if soucet < rozdil then begin vymena := soucet; soucet := rozdil; rozdil := vymena; end; existuji := false; if ( soucet >= rozdil ) then begin dvojnasobek := soucet - rozdil; if ( dvojnasobek mod 2 ) = 0 then begin existuji := true; end; end; if existuji then begin prvniCislo := dvojnasobek div 2; druheCislo := soucet - prvniCislo; write( prvniCislo ); write(' '); writeln( druheCislo ); end else begin writeln( 'chyba!' ); end; end; readln; end.

Obarvení grafu

Použijeme prohledávání grafu do hloubky (matice). Při nalezení každého vrcholu je třeba zkontrolovat, zda jsou sousední vrcholy obarveny opačnou barvou než právě nalezený vrchol a jsou-li neobarvené, obarvit je tak. Nalezneme-li sousední vrchol, který je už obarven barvou právě nalezeného vrcholu, prohledávání končí a graf je neobarvitelný. V opačném případě, tj. pokud při prohledávání dojdeme až na konec, je graf obarvitelný.

Příklad zdrojového kódu:

#include <stdio.h> int vrcholy[200][200]; int N; int L; int i; int a,b; int fronta[200]; int barvy[200]; int fend; int point; int main() { scanf("%d",&N); scanf("%d",&L); for (i=0;i<L;i++) { scanf("%d %d",&a,&b); vrcholy[a][b] = 1; vrcholy[b][a] = 1; } fronta[0] = 0; barvy[0] = -1; fend = 1; point = -1; while (point++ < fend) { for (i=0;i<N;i++) { if (vrcholy[fronta[point]][i] == 0) continue; if (barvy[i] == barvy[fronta[point]]) break; if (barvy[i] == 0) fronta[fend++] = i; barvy[i] = -barvy[fronta[point]]; } if (i != N) break; } if (i != N) printf("Nelze obarvit\n"); else printf("Lze obarvit\n"); }

Průvodce

Využijeme upravené algoritmy pro hledání nejkratší cesty: Dijkstrův a Floyd-Warshallův. Jelikož zadávané mapy měst nepatří mezi husté grafy, je znatelně rychlejší první uvedený.
Dijkstrův algoritmus
Složitost tohoto algoritmu je O(V*E). Vyhledáváme nejlepší cestu mezi dvěma vrcholy a to tak, že postupně prohledáváme graf do šířky, ale pouze ve vrcholech, "které vypadají slibně". Začneme prohledávat pomocí BFS v počátečním vrcholu a dále pokračujeme v těch vrcholech, do kterých se nám v každém kroku podařilo dostat nejvíce lidí. Pokud jsme se již nějakou cestou dostali do cíle, pokračujeme tak dlouho v prohledávání, dokud nebude jasné, že všechny další cesty mohou vést nejlépe ke stejnému výsledku.
Floyd-Warshallův algoritmus
Složitost tohoto algoritmu je O(n3). Vyhledáváme nejkratší cestu pro každou dvojici vrcholů grafu a to tak, že pro každé dva vrcholy zjišťujeme, zdali mezi nimi neexistuje kratší cesta přes jiný vrchol, tj. pro každé dva vrcholy zkontrolujeme, zda z prvního do druhého nemůžeme převézt více lidí, pokud použijeme cestu přes nějaký třetí vrchol.

Příklad zdrojového kódu:

#include <stdio.h> int min(int a, int b){ return (b<a ? b : a); } struct tvylet{ int start, cil, pocet, delka, prutok; }; int cesta[101][101], N, marked[101]; struct tvylet vylet; void projdi(int v, int h){ /*printf("%d(%d) ", v, h);*/ if(v == vylet.cil){ if(h > vylet.prutok) vylet.prutok = h; return; } int i; marked[v] = 1; for(i=1; i<=N; i++) if(cesta[v][i]) if(!marked[i]) projdi(i, min(h, cesta[v][i])); marked[v] = 0; } int main(){ int i, a, b, c, max = 0; scanf("%d %d",&N,&i); for(a=0; a<N; a++){ marked[a] = 0; for(b=0; b<N; b++) cesta[a][b] = 0; } while(i--){ scanf("%d %d %d", &a, &b, &c); cesta[a][b] = c; cesta[b][a] = c; if(c > max) max = c; } vylet.prutok = vylet.delka = 0; scanf("%d %d %d", &vylet.start, &vylet.cil, &vylet.pocet); projdi(vylet.start, max); while(vylet.pocet > 0){ vylet.pocet -= vylet.prutok-1; vylet.delka++; } printf("%d\n", vylet.delka); }

Finálové úlohy - řešení:

Nejprve je stručně popsán způsob, jakým je možno úlohu řešit. Následně je ukázán zdrojový kód možného řešení.

Poklad

Prohledáváme stavový prostor metodou BFS - prohledávání do šířky. Při sestavování stromu řešení zavrhneme varianty, které se již objevily (např. stav na počátku) a nejsou cílové (stav na konci= řešení).

Příklad zdrojového kódu:

import java.io.IOException; public class Poklad {// Poklad private class Node { public int[][] matrix; public int zeroI; public int zeroJ; public char move; public int moveLabel; public Node previous; public Node queueNext; public Node(int[][] matrix, char move, int moveLabel, Node previous) { this.matrix = matrix; this.move = move; this.moveLabel = moveLabel; this.previous = previous; for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { if (matrix[i][j] == 0) { zeroI = i; zeroJ = j; return; } } } } private int[][] copyMatrix() { int[][] newMatrix = new int[matrix.length][matrix[0].length]; for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { newMatrix[i][j] = matrix[i][j]; } } return newMatrix; } private Node moveDown() { int[][] newMatrix = copyMatrix(); newMatrix[zeroI][zeroJ] = newMatrix[zeroI - 1][zeroJ]; newMatrix[zeroI - 1][zeroJ] = 0; return new Node(newMatrix, 'D', newMatrix[zeroI][zeroJ], this); } private Node moveUp() { int[][] newMatrix = copyMatrix(); newMatrix[zeroI][zeroJ] = newMatrix[zeroI + 1][zeroJ]; newMatrix[zeroI + 1][zeroJ] = 0; return new Node(newMatrix, 'U', newMatrix[zeroI][zeroJ], this); } private Node moveLeft() { int[][] newMatrix = copyMatrix(); newMatrix[zeroI][zeroJ] = newMatrix[zeroI][zeroJ - 1]; newMatrix[zeroI][zeroJ - 1] = 0; return new Node(newMatrix, 'L', newMatrix[zeroI][zeroJ], this); } private Node moveRight() { int[][] newMatrix = copyMatrix(); newMatrix[zeroI][zeroJ] = newMatrix[zeroI][zeroJ + 1]; newMatrix[zeroI][zeroJ + 1] = 0; return new Node(newMatrix, 'R', newMatrix[zeroI][zeroJ], this); } public Node[] developNode() { Node[] nodeArray = new Node[3]; int index = 0; if (zeroI == 0 && this.move != 'D') { nodeArray[index++] = moveUp(); } if (zeroI == 1 && this.move != 'U') { nodeArray[index++] = moveDown(); } if (zeroJ != 0 && this.move != 'R') { nodeArray[index++] = moveLeft(); } if (zeroJ != 2 && this.move != 'L') { nodeArray[index++] = moveRight(); } return nodeArray; } public boolean isSolution() { if (matrix[0][0] == 1 && matrix[0][1] == 2 && matrix[0][2] == 3 && matrix[1][0] == 4 && matrix[1][1] == 5 && matrix[1][2] == 0) { return true; } else { return false; } } @Override public String toString() { String result = ""; Node node = this; while (node.previous != null) { if (node != this) { result = ", " + result; } result = node.moveLabel + result; node = node.previous; } return result; } } private class Queue { private Node first; private int count; public Queue() { first = null; count = 0; } public boolean isEmpty() { if (count == 0) { return true; } else { return false; } } public void insert(Node[] nodeArray) { for (Node node: nodeArray) { if (node != null) { insert(node); } } } public void insert(Node node) { if (count == 0) { first = node; } else { node.queueNext = first; first = node; } count++; } public Node remove() { Node node = first; Node previousNode = null; count--; if (count == 0) { first = null; return node; } else { while (node.queueNext != null) { previousNode = node; node = node.queueNext; } } previousNode.queueNext = null; return node; } } private final int MAX_LINE_LENGTH = 100; private final byte BUFFER[] = new byte[MAX_LINE_LENGTH]; private final char CHAR_LF = 10; private final char CHAR_CR = 13; private String readLine() { int index = 0; int readedChar = -1; try { while (index < MAX_LINE_LENGTH) { readedChar = System.in.read(); if (readedChar == CHAR_CR) { continue; } if (readedChar < 0 || readedChar == CHAR_LF) { break; } BUFFER[index] = (byte) readedChar; index++; } } catch (IOException e) { return null; } if (readedChar < 0 && index == 0) { return null; } return (new String(BUFFER, 0, index)); } private void run() { String line; String[] parsedLine; int[][] matrix = new int[2][3]; for (int i = 0; i < matrix.length; i++) { line = readLine(); parsedLine = line.split(" "); for (int j = 0; j < matrix[0].length; j++) { matrix[i][j] = Integer.parseInt(parsedLine[j]); } } Queue queue = new Queue(); Node rootNode = new Node(matrix, 'X', -1, null); if (rootNode.isSolution()) { return; } queue.insert(rootNode); Node node; int limit = 0; while (!queue.isEmpty()) { if (limit >= 5000) { System.out.println("No solution found within 5000 steps"); break; } limit++; node = queue.remove(); if (node.isSolution()) { System.out.println(node); break; } else { queue.insert(node.developNode()); } } } public static void main(String[] args) { new Poklad().run(); } }

Zakázané město

Řešením je prohledávání grafu do šířky a nalezení nejkratší cesty. Nejjednodušší řešení je nalézt nejkratší cesty mezi všemi síněmi (AB,AC,BC), tj. tři průchody BFS. Pokud jedna z cest nebyla nalezena, cesta neexistuje. V opačném případě provedeme součet dvou kratších cest.
Lepší postup (cca o 15% rychlejší, záleží na datech) je během načítání nalézt souřadnice síní A, B, C a tyto pak seřadit tak, aby síň A byla ta, co je nejvíce vlevo nahoře a síň B byla ta, co je nejvíce vpravo dole. Pak postupně nalézt nejkratší cesty v prvním průchodu pro AB a AC, v druhém průchodu pro BC (stačí jen dva průchody BFS namísto původních tří). Výsledkem je součet dvou nejkratších nalezených cest.

Příklad zdrojového kódu:

import java.util.Scanner; public class Mesto { public static int[][] cesta; public static String[][] mapa; public static void najdiCestu(int delka, int x, int y) { if(mapa[x][y].equalsIgnoreCase("0")) return; cesta[x][y] = delka; delka++; if(x>0 && x< mapa.length) { if(cesta[x-1][y] > delka) najdiCestu(delka, x-1, y); if(cesta[x+1][y] > delka) najdiCestu(delka, x+1, y); } if(y<0 && y < mapa[0].length) { if(cesta[x][y-1] > delka) najdiCestu(delka, x, y-1); if(cesta[x][y+1] > delka) najdiCestu(delka, x, y+1); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int x,y; String radek; int[] a = {0,0}; int[] b = {0,0}; int[] c = {0,0}; x = sc.nextInt(); y = sc.nextInt(); sc.nextLine(); mapa = new String[x][y]; for(int i = 0; i < x; i++) { radek = sc.nextLine(); for(int j = 0; j < y; j++) { mapa[i][j] = "" + radek.charAt(j); if(mapa[i][j].equalsIgnoreCase("a")) { a[0] = i; a[1] = j; } if(mapa[i][j].equalsIgnoreCase("b")) { b[0] = i; b[1] = j; } if(mapa[i][j].equalsIgnoreCase("c")) { c[0] = i; c[1] = j; } } } cesta = new int[x][y]; for(int i = 0; i < x; i++) { for(int j = 0; j < y; j++) { cesta[i][j] = 100000; } } najdiCestu(0,a[0], a[1]); int ab = cesta[b[0]][b[1]]; int ac = cesta[c[0]][c[1]]; for(int i = 0; i < x; i++) { for(int j = 0; j < y; j++) { cesta[i][j] = 100000; } } najdiCestu(0, b[0], b[1]); int bc = cesta[c[0]][c[1]]; int delka1 = Math.min(ac, ab)+ bc + 1; int delka2 = Math.min(ab, bc)+ ac + 1; int delka3 = Math.min(ac, bc)+ ab + 1; int delka = Math.min(Math.min(delka1, delka2), delka3); if(delka > 100000) { System.out.println("Cesta neexistuje"); } else { System.out.println("Delka nejkratsi cesty: " + delka); } } }

Tržiště

V zápisu výrazu se střídají čísla a znaménka, začíná a končí se číslem. Můžeme použít rekurzi či iterační výpočet. Nejprve načteme číslo, pak otestujeme, zda už neni konec zápisu (dle dalšího načteného symbolu), pokud ano vrátíme výsledek pokud ne, zjistíme, zda další symbol je + a v tomto případě vrátíme výsledek + hodnotu(zbytku), jinak provedeme načtení dalšího čísla, vynásobíme a pokračujeme čtením dalšího symbolu s následným testem konce, atd.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h>; int zustatek; int last_number; int cislo; int main() { scanf("%d",&cislo); last_number = cislo; while (getchar() == ' ') { switch (getchar()) { case '*': scanf("%d",&cislo); last_number *= cislo; break; case '+': scanf("%d",&cislo); zustatek += last_number; last_number = cislo; break; default: printf("error\n"); } } printf("%d",zustatek + last_number); }

Eulerova prvočísla

Princip algoritmu je jednoduchý. V každém zadaném rozsahu zjistíme pro každé číslo vhodnou metodou pro test prvočísel (např. Eratosthenovo síto), jestli vzorec n2 + n + 41 poskytuje prvočíslo. Zjistíme počet takto získaných prvočísel, spočteme procenta a zaokrouhlíme.
Pokud zadané intervaly nebudou pokrývat celý rozsah <0, 10000>, bude rychlejší pro zjištění prvočísla vždy přímo volat tuto metodu. Jinak je výhodnější nejdříve zjistit pro každé číslo z tohoto intervalu, zda tvoří po dosazení do vzorce prvočíslo, tento výsledek uložit do pole a poté využívat hodnoty z takto vytvořeného pole.

Příklad zdrojového kódu:

program eul_prv; var a,b,i,j,prvocislo,prv,proc:longint; cislo:longint; pocet_c,procenta:real; begin read(a); readln(b); prv:=0; prvocislo:=0; for i:=a to b do begin cislo:=i*i+i+41; for j:=2 to trunc(sqrt(cislo)) do begin if (cislo mod j=0) then begin prvocislo:=0; break; end else prvocislo:=1; end; if (prvocislo=1) then prv:=prv+1; end; pocet_c:=b-a+1; procenta:=(prv/pocet_c)*100; proc:=Round(procenta); writeln(proc); end.