PilsProg 2011

Výsledky kvalifikace

PříjmeníJménoSplněných úlohČasFinále
ZikmundMartin639,160postupuje do finále
KaletaJuda6142,437postupuje do finále
HlásekFilip6196,931postupuje do finále
HübschOndřej6303,744postupuje do finále
SejkoraVojtěch6617,273postupuje do finále
KopečekMiroslav61 275,035postupuje do finále
BílýMichael61 598,995postupuje do finále
SouchaMichal61 615,241postupuje do finále
KozaJakub62 495,851postupuje do finále
ŠimsaŠtěpán62 676,817postupuje do finále
AmbrožJan63 411,634postupuje do finále
MácaJindřich41 966,302postupuje do finále
MelkaMartin3275,289postupuje do finále
PolákMatěj2300,322
BláhaMartin16,964
MartínekŠtěpán131,004
ZítkaTomáš1195,028
KlesaJosef1658,171

Výsledky finále

PříjmeníJménoSplněných úlohČas
HlásekFilip42,634
ZikmundMartin46,312
SouchaMichal47,318
KaletaJuda49,962
HübschOndřej39,470
BílýMichael310,284
MelkaMartin310,398
KozaJakub22,626
KopečekMiroslav23,707
AmbrožJan24,059
MácaJindřich12,391
SejkoraVojtěch00,000
ŠimsaŠtěpán00,000

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

Poznámka:
Finalisté Vojtěch Sejkora a Štěpán Šimsa se finálové soutěže nezúčastnili.

Ilustrační úlohy:

NázevČísloÚspěšných řešitelů
AxB070430
Pascalův trojúhelník070311

Kvalifikační úlohy:

NázevČísloÚspěšných řešitelů
Kde je Dalimil?111213
Propojení budov111411
Fontány111112
Najdi šach111313
Robot111518
Tabule výsledků111612

Finálové úlohy:

NázevČísloÚspěšných řešitelů
Číselná soustava112111
Deratizace11228
Král a chuďas11238
Procházka11245

A jaké bylo finále?

Finále začíná ...

Harmonogram PilsProg 2011

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.

Kde je Dalimil?

  1. Načtení počtu případů. Následně se tolikrát provedou body 2 - 4.
  2. Načtení a uložení dat do dvou tabulek - nejdříve tabulka znaků, kde se budou řetězce vyhledávat a poté tabulka s hledanými řetězci.
  3. Prohledání tabulky znaků a snaha najít první písmeno hledaného řetězce, pokud je nalezeno musí se prozkoumat 8 směrů, kde může být daný řetězec nalezen. Např. začít směrem vpravo dolů a pokračovat ve směru hodinových ručiček. V každém směru nejdříve zjistit, jestli je znak v tabulce znaků na pozici (od okraje) takové, aby se tam celý řetězec vešel. Poté porovnává v daném směru všechny znaky. Pokud souhlasí i poslední znak, zapíše se řetězec do tabulky na souřadnice od jeho prvního písmene.
  4. Tisk tabulky řetězců.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> #define FOR(i,n) for(i=0;i<n;i++) #define MAXN 100 int N,M; char m[MAXN][MAXN]; char w[MAXN]; const int D[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}}; int valid(int x,int y){ return !(x<0||y<0||x>=M||y>=N); } int doit(int x,int y,int dx,int dy){ int i; for(i=0;w[i]!='\0';i++) if(!valid(x+dx*i,y+dy*i)||w[i]!=m[x+i*dx][y+i*dy]) return 0; printf(&%d %d\n&,x+1,y+1); return 1; } int main(int argc, char *argv[]){ int t,T,i,j,k,K,l,ok; scanf(&%d&,&T); FOR(t,T){ if(t) printf("\n"); scanf("%d%d",&M,&N); FOR(i,M) scanf("%s",m[i]); FOR(i,M) FOR(j,N) if(m[i][j]>='A'&&m[i][j]<='Z') m[i][j]+='a'-'A'; scanf("%d",&K); FOR(k,K){ ok=0; scanf("%s",w); for(i=0;w[i]!='\0';i++) if(w[i]>='A'&&w[i]<='Z') w[i]+='a'-'A'; FOR(i,M){ FOR(j,N){ FOR(l,8) if(doit(i,j,D[l][0],D[l][1])){ ok=1; break; } if(ok) break; } if(ok) break; } } } return 0; }

Propojení budov

Tato úloha se dá řešit jako hledání nejmenší kostry v grafu. To lze provést pomocí Kruskalova algoritmu, který je založen na tom, že se v grafu postupně hledají nejkratší hrany a pokud ty spojují 2 vrcholy, které doposud nejsou nijak spojeny, tuto hranu použije. V tomto případě tedy vypočteme vzdálenosti mezi každými dvěma budovami (síť budov jako graf, budovy jako jednotlivé vrcholy, spojnice mezi budovami hrany a vzdálenost budov jako hodnota odpovídajících hran). K uložení hran použijeme datovou strukturu halda. Postupně pak hrany procházíme a kontrolujeme, zda-li spojují 2 nespojené budovy. Pokud ano, pripočteme jejich vzdálenost k výsledné délce kabelu.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> #include <math.h> #define L(A, B) sqrt((X[A]-X[B])*(X[A]-X[B])+(Y[A]-Y[B])*(Y[A]-Y[B])) #define MAXN 751 typedef struct { int a, b; } hrana; int X[MAXN]; int Y[MAXN]; int parent[MAXN]; int cmp(const void* a, const void* b) { hrana* aa = (hrana*)a; hrana* bb = (hrana*)b; return L(aa->a, aa->b)-L(bb->a, bb->b); } //dfu: int root(int v) { if(parent[v] == 0) return v; else return root(parent[v]); } int find(int a, int b) { return root(a) == root(b) ? 1 : 0; } void uni(int x, int y) { int a = root(x), b = root(y); if(a != b) parent[a] = b; } int main() { int n; while(scanf("%d", &n) == 1) { double kabely[1000][1000]; int i, j; for(i = 0; i < n; i++) scanf("%d %d", &X[i], &Y[i]); for(i = 0; i < n; i++) for(j = 0; j < n; j++) kabely[i][j] = 0; int m; scanf("%d", &m); for(i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); a--;b--; kabely[a][b] = 1; kabely[b][a] = 1; } hrana* hrany = malloc(sizeof(hrana)*n*n); // int* parent = malloc(sizeof(int)*n); int h = 0; for(i = 0; i < n; i++) for(j = i+1; j < n; j++) { if(kabely[i][j] == 0) hrany[h].a = i; hrany[h++].b = j; } qsort(hrany, h, sizeof(hrana), cmp); double ans = 0; for(i = 0; i < n; i++) parent[i] = 0; for(i = 0; i < n; i++) for(j = 0; j < n; j++) { if(kabely[i][j] == 1) uni(i, j); } for(i = 0; i < h; i++) { if(find(hrany[i].a, hrany[i].b) == 0) { uni(hrany[i].a, hrany[i].b); ans += L(hrany[i].a, hrany[i].b); } } ans += 0.5; printf("%d", (int)ans); } }

Fontány

Použijeme algoritmus prohledávání grafu do šírky - BFS (bludište reprezentuje matice). Algoritmus muže mít více modifikací.
Postup

  1. začít fontánou, která je nejvíce vlevo nahoře (vpravo dole) - označme ji jako A
  2. prohledávat celý graf od fontány A a zapamatovat vzdálenost fontán AB a AC, nalezení obou fontán. Konec
  3. leží-li na některé z cest třetí fontána (AC:B nebo AB:C) je to nejkratší cesta. Konec
  4. neleží-li, pak nutno prohledat od fontány B k fontáně C (BC), zapamatovat si vzdálenost.
  5. secíst dvě nejkratší cesty. Konec

Příklad zdrojového kódu:

program fontany; const MAX = 50; type TPole = array[1..MAX] of array[1..MAX] of integer; TSouradnice = array[1..2] of integer; var cesta, p, tp : TPole; A, B : 1..MAX; i, j, ab, ac, bc, mx : integer; c : char; RAZ, DVA, TRI : TSouradnice; function Hledej(start, cil : TSouradnice; delka : integer) : integer; var tmp : TSouradnice; begin if (p[start[1]][start[2]] <> -1) and (cesta[start[1],start[2]]>delka) then begin cesta[start[1], start[2]] := delka; delka := delka + 1; if start[1]>1 then begin tmp := start; tmp[1] := tmp[1]-1; Hledej(tmp, cil, delka); end; if start[1]<A then begin tmp := start; tmp[1] := tmp[1]+1; Hledej(tmp, cil, delka); end; if start[2]>1 then begin tmp := start; tmp[2] := tmp[2]-1; Hledej(tmp, cil, delka); end; if start[2]<B then begin tmp := start; tmp[2] := tmp[2] + 1; Hledej(tmp, cil, delka); end; Hledej := cesta[cil[1]][cil[2]]; end else Hledej := 0; end; begin readln(A, B); for i:=1 to A do begin for j:=1 to B do begin read(c); if c='x' then p[i][j] := -1; if c=' ' then p[i][j] := 0; if c='1' then begin RAZ[1] := i; RAZ[2] := j; end; if c='2' then begin DVA[1] := i; DVA[2] := j; end; if c='3' then begin TRI[1] := i; TRI[2] := j; end; end; readln; end; for i:=1 to MAX do for j:=1 to MAX do cesta[i][j] := 30000; ab := Hledej(RAZ, DVA, 0); for i:=1 to MAX do for j:=1 to MAX do cesta[i][j] := 30000; bc := Hledej(DVA, TRI, 0); for i:=1 to MAX do for j:=1 to MAX do cesta[i][j] := 30000; ac := Hledej(RAZ, TRI, 0); mx := ab; if bc > mx then mx := bc; if ac > mx then mx := ac; if (ab+bc+ac-mx > 30000) then writeln(0) else writeln(ab+bc+ac-mx); end.

Najdi šach

Mějme šachovnici s rozmístěnými figurami. Na šachovnici se nachází právě dva králové, u kterých máme za úkol zjistit, zda jsou v šachu. Načteme a uložíme si rozmístění figur do matice. Během načítání si také uložíme souřadnice obou králů. Nyní musíme pro oba krále ověřit, zda se nenacházejí v šachu. Král se nachází v šachu, pokud je pole, na kterém stojí, ohrožováno nepřátelskou figurou.

Postup

  1. Načtení šachovnice.
  2. Nalezení souřadnic obou králů.
  3. Určení, zda se některý z králů nachází v šachu.
  4. Vypsání výsledku.

Příklad zdrojového kódu:

import java.io.*; import java.util.*; public class sachy{ static sachovnice hraciPole; static int hraID; public static void main(String [] args){ Scanner sc = new Scanner(System.in); hraciPole = new sachovnice(); boolean pokracovat=false; hraID=0; do{ hraID++; pokracovat=false; for (int j=0; j<8;j++){ //String kontrola; String radka = sc.nextLine(); for (int i=0; i<8;i++){ //System.out.println("PRIDAVAM "+i+"-"+j+" : "); sachovnice.pridatFigurku(radka.charAt(i)+"", i, j); if (radka.charAt(i)!='.') pokracovat=true; //kontrola+=radka.charAt(i); //System.out.print(radka.charAt(i)); // System.out.println("PRIDAVAM "+i+"-"+j+" : "+radka.charAt(i)); } //System.out.println(); } if (pokracovat){ sc.nextLine(); sachovnice.zkontrolovat(); } }while (pokracovat==true); } } class sachovnice{ static figurka [][] figurky; static figurka bKral; static figurka cKral; sachovnice(){ figurky = new figurka[8][8]; } static void pridatFigurku(String ID, int x, int y){ //if (ID.equals('.')) return; figurky[x][y] = new figurka(ID,x,y); //if (ID.equals("K")) System.out.println("EQ"); if (ID.equals("K")) bKral = figurky[x][y]; if (ID.equals("k")) cKral = figurky[x][y]; } static void zkontrolovat(){ boolean cK = cKral.ohrozena(); boolean bK = bKral.ohrozena(); if (!cK & !bK) System.out.println("Hra #"+sachy.hraID+": ani jeden kral nema sach"); if (cK & !bK) System.out.println("Hra #"+sachy.hraID+": cerny kral ma sach"); if (!cK & bK) System.out.println("Hra #"+sachy.hraID+": bily kral ma sach"); } } class figurka{ char ID; int barva; sachovnice pole; int x; int y; figurka(String mID,int xx, int yy){ if (Character.isUpperCase(mID.charAt(0))) barva=1; else barva=0; String tID = mID.toUpperCase(); ID=tID.charAt(0); pole = sachy.hraciPole; x=xx; y=yy; } boolean ohrozena(){ boolean res = false; // Kontrola, jestli je tato figurka ohrozena // STRELEC + KRALOVNA // Vpravo dolu int c=0; for (int i=x+1; i<8; i++){ c++; int j=y+c; if (j>7) break; //System.out.println(this.ID+""+this.barva+" : kontrola "+i+"-"+j+" XXX barva kontrol.: "+pole.figurky[i][j].barva+" / kral: "+this.barva+" XXX ID kontrol.: "+pole.figurky[i][j].ID); if ((pole.figurky[i][j].ID=='B' || pole.figurky[i][j].ID=='Q')& this.barva!=pole.figurky[i][j].barva){ res=true; break; }else if (pole.figurky[i][j].ID!='.') break; } // Vpravo nahoru c=0; for (int i=x+1; i<8; i++){ c--; int j=y+c; if (j<0) break; if ((pole.figurky[i][j].ID=='B' || pole.figurky[i][j].ID=='Q') & this.barva!=pole.figurky[i][j].barva){ res=true; break; }else if (pole.figurky[i][j].ID!='.') break; } // Vlevo dolu c=0; for (int i=x-1; i>=0; i--){ c++; int j=y+c; if (j>7) break; if ((pole.figurky[i][j].ID=='B' || pole.figurky[i][j].ID=='Q') & this.barva!=pole.figurky[i][j].barva){ res=true; break; }else if (pole.figurky[i][j].ID!='.') break; } // Vlevo nahoru c=0; for (int i=x-1; i>=0; i--){ c--; int j=y+c; if (j<0) break; //System.out.println(this.ID+""+this.barva+" : kontrola "+i+"-"+j+" XXX barva kontrol.: "+pole.figurky[i][j].barva+" / kral: "+this.barva+" XXX ID kontrol.: "+pole.figurky[i][j].ID); if ((pole.figurky[i][j].ID=='B' || pole.figurky[i][j].ID=='Q') & this.barva!=pole.figurky[i][j].barva){ res=true; break; }else if (pole.figurky[i][j].ID!='.') break; } //System.out.println("<><><>; KONTROLA barva:"+this.barva); // VEZ + KRALOVNA // Dolu for (int j=y+1; j<8; j++){ int i=x; if ((pole.figurky[i][j].ID=='R' || pole.figurky[i][j].ID=='Q') & this.barva!=pole.figurky[i][j].barva){ res=true; break; }else if (pole.figurky[i][j].ID!='.') break; } // Nahoru for (int j=y-1; j>=0; j--){ int i=x; //System.out.println(this.ID+""+this.barva+" : kontrola "+i+"-"+j+" XXX barva kontrol.: "+pole.figurky[i][j].barva+" / kral: "+this.barva+" XXX ID kontrol.: "+pole.figurky[i][j].ID); //System.out.println(pole.figurky[j][i].ID+" & "+this.barva+"!="+pole.figurky[i][j].barva); if ((pole.figurky[i][j].ID=='R' || pole.figurky[i][j].ID=='Q') & this.barva!=pole.figurky[i][j].barva){ res=true; break; }else if (pole.figurky[i][j].ID!='.') break; } // Vpravo for (int j=x+1; j<8; j++){ int i=y; if ((pole.figurky[j][i].ID=='R' || pole.figurky[j][i].ID=='Q') & this.barva!=pole.figurky[j][i].barva){ res=true; break; }else if (pole.figurky[j][i].ID!='.') break; } // Vlevo for (int j=x-1; j>=0; j--){ int i=y; if ((pole.figurky[j][i].ID=='R' || pole.figurky[j][i].ID=='Q') & this.barva!=pole.figurky[j][i].barva){ res=true; break; }else if (pole.figurky[j][i].ID!='.') break; } //System.out.println("<><><> KONTROLA barva:"+this.barva); // PESAK if (barva==1) // smer dolu if (x>0 & y>0) if ((pole.figurky[x-1][y-1].ID=='P')&(pole.figurky[x-1][y-1].barva==0)) res=true; if (x<7 & y>0) if ((pole.figurky[x+1][y-1].ID=='P')&(pole.figurky[x+1][y-1].barva==0)) res=true; if (barva==0) // smer nahoru if(x>0 & y<7) if ((pole.figurky[x-1][y+1].ID=='P')&(pole.figurky[x-1][y+1].barva==1)) res=true; if (x<7 & y<7) if ((pole.figurky[x+1][y+1].ID=='P')&(pole.figurky[x+1][y+1].barva==1)) res=true; // KUN int nx; int ny; nx=x-1; ny=y-2; if (nx>=0 & nx<8 &ny>=0 &ny<8) if (pole.figurky[nx][nx].barva!=this.barva & pole.figurky[nx][ny].ID=='N') res=true; nx=x-1; ny=y+2; if (nx>=0 & nx<8 &ny>=0 &ny<8) if (pole.figurky[nx][nx].barva!=this.barva & pole.figurky[nx][ny].ID=='N') res=true; nx=x-2; ny=y-1; if (nx>=0 & nx<8 &ny>=0 &ny<8) if (pole.figurky[nx][nx].barva!=this.barva & pole.figurky[nx][ny].ID=='N') res=true; nx=x-2; ny=y+1; if (nx>=0 & nx<8 &ny>=0 &ny<8) if (pole.figurky[nx][nx].barva!=this.barva & pole.figurky[nx][ny].ID=='N') res=true; nx=x+1; ny=y-2; if (nx>=0 & nx<8 &ny>=0 &ny<8){ //System.out.println("Kral barva: "+this.barva+" || "+x+"-"+y+ " XXX " + pole.figurky[nx][nx].barva+" - "+this.barva +" //"+ pole.figurky[nx][ny].ID); if (pole.figurky[nx][nx].barva!=this.barva & pole.figurky[nx][ny].ID=='N') res=true; } nx=x+1; ny=y+2; if (nx>=0 & nx<8 &ny>=0 &ny<8){ //System.out.println("<><><> KONTROLA barva:"+this.barva); //System.out.println("Kral barva: "+this.barva+" || "+x+"-"+y+ " XXX " + pole.figurky[nx][nx].barva+" - "+this.barva +" //"+ pole.figurky[nx][ny].ID); if (pole.figurky[nx][nx].barva!=this.barva & pole.figurky[nx][ny].ID=='N') res=true; } nx=x+2; ny=y-1; if (nx>=0 & nx<8 &ny>=0 &ny<8) if (pole.figurky[nx][nx].barva!=this.barva & pole.figurky[nx][ny].ID=='N') res=true; nx=x+2; ny=y+1; if (nx>=0 & nx<8 &ny>=0 &ny<8) if (pole.figurky[nx][nx].barva!=this.barva & pole.figurky[nx][ny].ID=='N') res=true; return res; } }

Robot

Mřížku instrukcí načteme do matice odpovídající velikosti. Dále si vytvoříme celočíselnou matici stejné velikosti, do které budeme zaznamenávat časy, ve kterých robot vstoupil na daná pole. Tuto matici inicializujeme hodnotami, které budou určovat, že robot tato pole ještě nenavštívil. Nyní umístíme robota na jeho počáteční políčko a čas návštěvy tohoto pole nastavíme na 0. Robota budeme přesouvat podle instrukcí. Pokud robota přesuneme na políčko, které ještě nenavštívil, nastavíme čas návštěvy na hodnotu času návštěvy předchozího políčka zvětšeného o 1. Pokud je následující políčko mimo mřížku, robot ukončil svůj průchod a vypíšeme na obrazovku čas návštěvy políčka, ze kterého robot mřížku opustil. Pokud robota přesuneme na políčko, které již dříve navštívil, tak robot vstoupil do nekonečné smyčky. Pak můžeme ukončit robotův průchod a vypsat počet kroků před vstupem do smyčky, který je roven času návštěvy políčka, které robot již dříve navštívil, rovněž vypíšeme počet kroků ve smyčce, který je roven rozdílu časů, ve kterých robot navštívil již dříve navštívené políčko a poslední políčko, ze kterého robot toto dříve navštívené políčko objevil.

Příklad zdrojového kódu:

program robot; type bod=record s :char; d :integer; end; divnypole=array[1..10,1..10]of bod; procedure NactiSit(var sit:divnypole; y,x:byte); var i,i2:integer; begin for i:=1 to y do begin for i2:=1 to x do begin sit[i][i2].d:=0; read(sit[i][i2].s) end; readln end; end; var sit :divnypole; start,i,i2,kroku :integer; x,y :byte; uvnitr:boolean; begin read(y); while y<>0 do begin readln(x,start); nactisit(sit,y,x); i:=1; i2:=start; kroku:=1; uvnitr:=true; while (sit[i][i2].d=0) and uvnitr do begin sit[i][i2].d:=kroku; inc(kroku); //writeln(kroku,' ',sit[i][i2].s); case sit[i][i2].s of 'W':inc(i2,-1); 'N':inc(i,-1); 'S':inc(i); 'E':inc(i2); end; uvnitr:=(i>0)and(i<=y)and(i2>0)and(i2<=x); end; if uvnitr then writeln(sit[i][i2].d-1,':',kroku-sit[i][i2].d) else writeln(kroku-1,':exit'); read(y); end; end.

Tabule výsledků

K ukládání dat o jednotlivých odevzdáních používáme pro každý soutěžní tým pole úspěšně vyřešených problémů a neúspěšných odevzdání - do jednoho z nich je vždy vloženo dané odevzdání dle vstupu. Po načtení všech odevzdání je vyhodnoceno skóre každého týmu podle zadáním specifikovaných kritérií. Týmy jsou razeny dle počtu vyrešených problémů (čím více, tím lépe) a dle rostoucího penalizačního času (čím méně, tím lépe).

Příklad zdrojového kódu:

program Tabule_vysledku; {$APPTYPE CONSOLE} type tttym= record cislo:integer; vyreseno:integer; zarazen:boolean; cas:integer; ulohy:array[1..9] of integer; end; Ttym = array[1..100] of Tttym; var tymy:Ttym; i,j,k:integer; pocetpripadu:integer; tym, uloha, doba:integer; znakdopl,znak:char; temptym:tttym; begin readln(pocetpripadu); readln; for i:=1 to pocetpripadu do begin //vynulovani tymu for j:=1 to 100 do begin with tymy[j] do begin cislo:=j; vyreseno:=0; zarazen:=false; cas:=0; for k:=1 to 9 do ulohy[k]:=0; end; end; //vynulovani tymu //naplneni tymu udaji / zacatek while not(eoln) do begin readln(tym,uloha,doba,znakdopl,znak); //case of zacatek case znak of 'I':begin tymy[tym].zarazen:=true; if tymy[tym].ulohy[uloha]>=0 then tymy[tym].ulohy[uloha]:=tymy[tym].ulohy[uloha]+20; end; 'C':begin if tymy[tym].ulohy[uloha]>=0 then begin tymy[tym].vyreseno:=tymy[tym].vyreseno+1; tymy[tym].zarazen:=true; tymy[tym].cas:=tymy[tym].cas+doba+tymy[tym].ulohy[uloha]; tymy[tym].ulohy[uloha]:=-1; end; end; 'R':tymy[tym].zarazen:=true; 'U':tymy[tym].zarazen:=true; 'E':tymy[tym].zarazen:=true; end; //case of konec end; //naplneni tymu udaji / konec //serazeni tymu for j:=1 to 99 do for k:=j+1 to 100 do begin//1 if tymy[j].zarazen and tymy[k].zarazen then begin//2 if tymy[j].vyreseno<tymy[k].vyreseno then begin temptym:=tymy[j]; tymy[j]:=tymy[k]; tymy[k]:=temptym; end else if tymy[j].vyreseno=tymy[k].vyreseno then begin//3 if tymy[j].cas>tymy[k].cas then begin temptym:=tymy[j]; tymy[j]:=tymy[k]; tymy[k]:=temptym; end else if tymy[j].cas=tymy[k].cas then if tymy[j].cislo>tymy[k].cislo then begin temptym:=tymy[j]; tymy[j]:=tymy[k]; tymy[k]:=temptym; end; end;//3 end;//2 end;//1 //vystup for j:=1 to 100 do begin if tymy[j].zarazen then writeln(tymy[j].cislo,' ',tymy[j].vyreseno,' ',tymy[j].cas); end; readln; writeln; end; readln; { TODO -oUser -cConsole Main : Insert code here } end.

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 řešení vytvořeného jedním z finalistů.

Číselná soustava

Vstup načteme do dvou řetězců, které převedeme na čísla, tato dvě čísla sečteme a opět převedeme do nového číselného systému.
Postup:
Celý řetězec procházíme a postupně načítáme znak po znaku a vytváříme přepis daného čísla do standardní podoby. Pokud narazíme v řetězci na číslici, tak ji uložíme do proměnné, podle specifikace nového číselného systému musí vždy po číslici následovat písmeno. Načteme toto písmeno a dle jeho definice a hodnoty násobíme danou číslici v proměnné. Tento mezikrok uložíme, k němu přičteme další až získáme přepis daného řetězce na číslo. Totéž provedeme pro druhý řetězec. Obě čísla sečteme a převedeme výslednou hodnotu do nového číselného systému. Přepis ze standardního čísla do nového číselného formátu je též jednoduchý. Do prázdného řetězce postupně načítáváme číslo zleva doprava. Určíme jeho délku převodem na řetězec. Pokud číslo obsahuje číslici 0, tak k řetězci připojíme pouze prázdný řetězec, pokud číslo obsahuje číslici 1, připojíme do řetězce pouze dané písmeno, jinak musíme rozhodnout podle pozice, kde se nacházíme v čísle, o jaký řád se jedná a připojíme písmeno. Výsledkem je výpis převedeného řetězce.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> #define FOR(i,N) for(i=0;i<N;i++) char a[20],b[20]; int decode(char x[20]){ int i,z=1,sum=0; for(i=0;x[i]!='\0';i++){ if(x[i]>='1'&&x[i]<='9') z=x[i]-'0'; else{ if(x[i]=='m') sum+=1000*z; if(x[i]=='c') sum+=100*z; if(x[i]=='x') sum+=10*z; if(x[i]=='i') sum+=z; z=1; } } return sum; } void code(int x){ if(x/1000){ if(x/1000>1) printf("%d",x/1000); printf("m"); x%=1000; } if(x/100){ if(x/100>1) printf("%d",x/100); printf("c"); x%=100; } if(x/10){ if(x/10>1) printf("%d",x/10); printf("x"); x%=10; } if(x){ if(x>1) printf("%d",x); printf("i"); } printf("\n"); } int main(){ int T,t; scanf("%d",&T); FOR(t,T){ scanf("%s",a); scanf("%s",b); code(decode(a)+decode(b)); } return 0; }

Deratizace

Použijeme pole o velikosti 1025 x 1025. Celé jej naplníme nulami. Každá souřadnice představuje křižovatku, kde mohou mít krysy hnízdo. Načteme ze vstupu počet scénářů a vytvoříme cyklus. V cyklu načítáme sílu bomby a počet krysích hnízd. V matici vybereme čtvercovou „podmatici“ o velikosti d = 2 * síla bomby a do každého jejího prvku přičteme velikost krysí populace. Samozřejmostí je ohlídat kraje matice. Po zapsání všech krysích populací stačí projít matici od levého horního rohu a najít její maximální prvek. Do výpisu zadáme souřadnice x a y a hodnotu tohoto prvku.

Příklad zdrojového kódu:

/* * To change this template, choose Tools | Templates * and open the template in the editor. */ package pilsprog; import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; /** * * @author PilsProg */ public class u2 { /** * @param args the command line arguments */ public static void main(String[] args) {//throws FileNotFoundException { Scanner cin = new Scanner(System.in);//new File("input.txt"));// int sc = cin.nextInt(); int d,n,x=0,y=0,p,kx,ky; int[][] pole = new int[1024][1024]; for (int i=0;i!=sc;i++) { d = cin.nextInt(); n = cin.nextInt(); for (int j=0;j!=n;j++) { x = cin.nextInt(); y = cin.nextInt(); p = cin.nextInt(); kx=(x+d+1)>1024 ? 1024 : (x+d+1); ky=(y+d+1)>1024 ? 1024 : (y+d+1); x=(x-d)<0 ? 0 : (x-d); y=(y-d)<0 ? 0 : (y-d); for (int k = x; k != kx; k++) { for (int l = y; l != ky; l++) { pole[k][l]+=p; } } } p=-1; for (int k = 0; k < 1024; k++) { for (int j = 0; j < 1024; j++) { if (pole[k][j]>p) { x=k; y=j; p=pole[k][j]; } pole[k][j]=0; } } System.out.println(x+" "+y+" "+p); } cin.close(); } }

Král a chuďas

Vytvořit matici A[m][n],kde A[i][k] - je nejdelší úsek neobsahující žádnou 1 začínající (i,k), tj. procházet matici a pokud je tam 1 dáme 0, pokud je tam nula, vložíme kolikatá nula to je (inkrementace pocetNul).
Pro všechny (i,k) je nutno prohledat cyklem matici ( l-šířka j-výška) ve sloupci a počítat kolikrát je v něm obsažena nula, spočíst počet nul celé takovéto plochy a porovnat s maximální plochou a nastavit případně nové max.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> #define FOR(i,N) for(i=0;i<N;i++) #define MAXN 111 int N,M; int m[MAXN][MAXN],s[MAXN][MAXN]; int get(int x1,int y1,int x2,int y2){ return s[x2][y2]-s[x1][y2]-s[x2][y1]+s[x1][y1]; } int main(){ int i,j,k,l,best; scanf("%d%d",&N,&M); while(N||M){ best=0; FOR(i,N) FOR(j,M) scanf("%d",&(m[i][j])); FOR(i,N+1) s[i][0]=0; FOR(i,M+1) s[0][i]=0; FOR(i,N) FOR(j,M){ s[i+1][j+1]=m[i][j]+s[i][j+1]+s[i+1][j]-s[i][j]; } FOR(i,N) FOR(j,M){ for(k=i+1;k<=N;k++) for(l=j+1;l<=M;l++){ //printf("%d %d %d %d: %d\n",i,j,k,l,get(i,j,k,l)); if(get(i,j,k,l)) break; best=(k-i)*(l-j)>best?(k-i)*(l-j):best; } } printf("%d\n",best); scanf("%d%d",&N,&M); } return 0; }

Procházka

Pro každý případ vytvoříme matici o velikosti rovné počtu křižovatek (první načtené číslo). Načteme počet hran a provádíme následující cyklus: načteme novou řádku, tj. novou hranu sestávající ze dvou čísel i a j a hranu zadáme do matice tak, že inkrementujeme prvek na pozici [i][j] a [j][i] (graf je neorientovaný). Po zpracování všech hran budeme mít vytvořenu symetrickou matici sousednosti, kde číslo na indexu [i][j] indikuje počet hran mezi příslušnými vrcholy i a j. Hledáme cestu grafem, která každou hranu projde právě jednou, tj. Eulerovský tah. Ten existuje v souvislém grafu právě tehdy, když stupně všech vrcholů jsou sudé.Nejprve budeme zjišťovat, zda graf splňuje podmínku sudých stupňů, poté, zda je souvislý. Pokud jsou obě podmínky splněny, je možné v takovém grafu projít všechny cesty a žádnou z nich nepoužít dvakrát – tj. přesně to, co je v zadání vyžadováno. Protože každý řádek v matici sousednosti představuje jeden vrchol grafu (křižovatku), jeho stupeň získáme tak, že sečteme počet hran, které z něho vycházejí. Projdeme tedy každý řádek matice a budeme sčítat hodnoty v tomto řádku. Součet dělíme mod 2 a pokud je výsledek různý od nuly, nepokračujeme a do logické proměnné „vystup“ vracíme hodnotu false, indikující, že průchod není možné uskutečnit. Pokud v ověřování sudosti uspějeme, zjišťujeme, zda je graf souvislý, tj. jestli z každého vrcholu grafu existuje cesta ke všem ostatním vrcholům. V neorientovaném grafu stačí prohledat do šířky. Pokud je souvislý, musíme takto objevit veškeré vrcholy. Graf procházíme z vrcholu 0. Při každém nově objeveném vrcholu inkrementujeme proměnnou "počet" a poté, co je hledání ukončeno, zkontrolujeme, zda je tato proměnná menší než počet vrcholů. Pokud ano, znamená to, že nebyly objeveny všechny vrcholy, z čehož dle původní úvahy plyne, že graf není souvislý. Vrátíme tedy hodnotu indikující, že průchod není možné uskutečnit (vystup = false). Vytiskneme příslušné hlášení, „lze“ pokud je v proměnné „vystup“ true a nebo „nelze“ pokud je vystup false.

Příklad zdrojového kódu:

#include<stdio.h> #define FOR(i,N) for(i=0;i<N;i++) #define MAXN 222 int m[MAXN][MAXN],N,R; int visited[MAXN]; void dfs(int x){ visited[x]=1; int i; FOR(i,N) if(m[x][i]&&visited[i]==0) dfs(i); } int visit(int x){ dfs(x); int i; FOR(i,N) if(visited[i]==0) return 0; return 1; } int count(){ int i,j,sum; FOR(i,N){ sum=0; FOR(j,N) sum+=m[i][j]; if(sum%2) return 0; } return 1; } int main(){ int i,x,y; scanf("%d%d",&N,&R); FOR(i,R){ scanf("%d%d",&x,&y); m[x][y]=1; m[y][x]=1; } if(visit(0)==0||count()==0) printf("nelze\n"); else printf("lze\n"); return 0; }