PilsProg 2012

Výsledky kvalifikace

PříjmeníJménoSplněných úlohČasFinále
ZikmundMartin634,283postupuje do finále
PokornýMichael6273,774postupuje do finále
KaletaJuda6384,435postupuje do finále
SejkoraVojtěch6600,842postupuje do finále
KopecekMiroslav6638,351postupuje do finále
KozaJakub6913,998postupuje do finále
VáňaMartin6957,972postupuje do finále
ŠimsaŠtěpán62 896,180postupuje do finále
MácaJindřich63 978,539postupuje do finále
KasalickýTomáš5189,443postupuje do finále
MelkaMartin5630,038postupuje do finále
PolívkaVojtěch5861,609postupuje do finále
HübschOndřej51 255,294postupuje do finále
HájekDalimil52 316,155postupuje do finále
VašekVojtěch494,856
HlávkaVojtěch42 451,924
KlesaJosef42 755,071
VrbaFilip3177,529
KratochvílPavel31 225,725
BláhaRichard32 043,756
HulcováTereza230,844
NovýMarek277,201
DavídekHynek286,099
NguyenThi Tuyet Trang2314,135
FürbacherováJitka122,991
MartínekJiří148,925
JohánekPavel177,030

Výsledky finále

PříjmeníJménoSplněných úlohČas
ŠimsaŠtěpán42,460
HübschOndřej44,452
ZikmundMartin44,582
PokornýMichael45,779
KozaJakub47,995
VáňaMartin32,880
KopecekMiroslav34,894
MelkaMartin35,506
KasalickýTomáš36,796
PolívkaVojtěch37,187
SejkoraVojtěch38,191
KaletaJuda38,502
HájekDalimil22,406
MácaJindřich00,000

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

Poznámka:
Finalista Jindřich Máca se finálové soutěže nezúčastnil.

Ilustrační úlohy:

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

Kvalifikační úlohy:

NázevOznačeníÚspěšných řešitelů
Kdo vyhraje milión?121320
Smlouva s ďáblem121527
Zloději v muzeu121613
Obdélníky121424
Kanonýr121212
Fotbalové výsledky121115

Finálové úlohy:

NázevOznačeníÚspěšných řešitelů
Souostroví12216
Sněhulák122312
Šachové věže122413
Pokladna122212

A jaké bylo finále?

Finále začíná ...

Harmonogram PilsProg 2012

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.

Fotbalové výsledky

  1. Vytvořit si třídu/strukturu/záznam uchovávající informace o jednotlivých týmech (název, počet bodů, zápasů, výher, atd.).
  2. Pro každou soutěž si načíst názvy týmů a vytvořit příslušné týmy.
  3. Načíst řádky s informacemi o zápasech. Z nich zjistit jména týmů a počty gólů. Jako vodítka pro dělení každé řádky použít znaky # a @. Z počtu gólů obou týmů lze zároveň určit, zda šlo o remízu, výhru či prohru u obou týmů. Takto zjištěné informace uložit do příslušných týmů.
  4. Seřadit týmy podle stanovených kritérií ve správném pořadí (tj. nejprve podle počtu získaných bodů, když mají stejně bodů, tak podle počtu výher, když mají i stejný počet výher, tak podle gólového rozdílu, atd.)
  5. Po seřazení vypsat název soutěže a všechny týmy. Pokud ještě nebyla zpracována poslední soutěž, pokračovat s další soutěží.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include <math.h> typedef struct { int enabled; int poradi; int remizy; int prohry; int obdrzene_goly; int index[6]; /* 0=body, 1=vyhry, 2=golovy_rozdil, 3=dane_goly, 4=zapasy /utkani, */ char nazev[32]; }TYM; char jmeno_souteze[100]; int pocet_tymu; TYM * tym_tab; void init_f(int tym) { int q; for (q=0;q<32;q=q+1) { tym_tab[tym].nazev[q]=0; } for (q=0;q<6;q=q+1) { tym_tab[tym].index[q]=0; } tym_tab[tym].index[0]=0; tym_tab[tym].index[4]=0; tym_tab[tym].index[1]=0; tym_tab[tym].remizy=0; tym_tab[tym].prohry=0; tym_tab[tym].index[2]=0; tym_tab[tym].index[3]=0; tym_tab[tym].obdrzene_goly=0; tym_tab[tym].poradi=0; } void print_tym(int tym) { printf("%d) %s %db, %dz (%d-%d-%d), %dgr (%d-%d)\n",tym_tab[tym].poradi,tym_tab[tym].nazev,tym_tab[tym].index[0],tym_tab[tym].index[4],tym_tab[tym].index[1],tym_tab[tym].remizy,tym_tab[tym].prohry,tym_tab[tym].index[2],tym_tab[tym].index[3],tym_tab[tym].obdrzene_goly); } int prohodit (int act_tym, int next_tym) { int fi; for (fi=0;fi<4;fi=fi+1) { if (tym_tab[act_tym].index[fi]<tym_tab[next_tym].index[fi]) return 1; if (tym_tab[act_tym].index[fi]>tym_tab[next_tym].index[fi]) return 0; } if (tym_tab[act_tym].index[4]>tym_tab[next_tym].index[4]) return 1; if (tym_tab[act_tym].index[4]<tym_tab[next_tym].index[4]) return 0; for (fi=0;fi<4;fi=fi+1) { if (tym_tab[act_tym].nazev[fi]==0) return 0; if (tym_tab[next_tym].nazev[fi]==0) return 1; if ( ((int)toupper(tym_tab[act_tym].nazev[fi]))>((int)toupper(tym_tab[next_tym].nazev[fi])) ) { return 1; } if ( ((int)toupper(tym_tab[act_tym].nazev[fi]))<((int)toupper(tym_tab[next_tym].nazev[fi])) ) { return 0; } } } int main(void) { int ps,fn,fpz,fni,fc; int j,i, bbs_end; char *name_id; char j_znak; int pocet_soutezi; int pocet_zapasu; int **field; float soucet; char temp_name1[32]; char temp_name2[32]; int temp_gol1,temp_gol2; TYM *temp_tym1; TYM *temp_tym2; scanf("%d",&pocet_soutezi); for (ps=0;ps<pocet_soutezi;ps=ps+1) { /*// loading data ////////////////////////////////////////////*/ if (ps==0) getchar(); name_id=&jmeno_souteze[0]; while ((*(name_id++)=getchar())!='\n') { } //printf("soutez: %s",jmeno_souteze); scanf("%d",&pocet_tymu); getchar(); tym_tab=(TYM*)malloc(pocet_tymu*sizeof(TYM)); for (fn=0;fn<pocet_tymu;fn=fn+1) { init_f(fn); name_id=(tym_tab[fn].nazev); while ((*(name_id++)=getchar())!='\n') { } *(name_id-1)=0; //printf("tym (%d) %s\n",fn,tym_tab[fn].nazev); } scanf("%d",&pocet_zapasu); //printf("zapasu: %d\n",pocet_zapasu); getchar(); for (fpz=0;fpz<pocet_zapasu;fpz=fpz+1) { name_id=&temp_name1[0]; while ((*(name_id++)=getchar())!='#') { } *(name_id-1)=0; scanf("%d@%d#",&temp_gol1,&temp_gol2); name_id=&temp_name2[0]; do { (*(name_id++))=getchar(); } while ((*(name_id-1)!='\n')&&(*(name_id-1)!=EOF)); *(name_id-1)=0; //printf("z%d.: %s#%d@%d#%s\n",fpz+1,temp_name1,temp_gol1,temp_gol2,temp_name2); /*-- update tabulky tymu ---------------------------------------*/ for (fn=0;fn<pocet_tymu;fn=fn+1) { if ((strcmp(temp_name1,tym_tab[fn].nazev))==0) { //printf("shoda pro tym %d\n",fn); temp_tym1=&(tym_tab[fn]); } if ((strcmp(temp_name2,tym_tab[fn].nazev))==0) { //printf("shoda pro tym %d\n",fn); temp_tym2=&(tym_tab[fn]); } } temp_tym1->index[4]+=1; temp_tym1->index[3]+=temp_gol1; temp_tym1->obdrzene_goly+=temp_gol2; temp_tym2->index[4]+=1; temp_tym2->index[3]+=temp_gol2; temp_tym2->obdrzene_goly+=temp_gol1; if (temp_gol1==temp_gol2) { temp_tym1->remizy+=1; temp_tym2->remizy+=1; } else { if (temp_gol1>temp_gol2) { temp_tym1->index[1]+=1; temp_tym2->prohry+=1; } else { temp_tym2->index[1]+=1; temp_tym1->prohry+=1; } } /*-- end_of update tabulky tymu --------------------------------*/ } /* end_of nacteni zapasu*/ /*- aktualizace udaju v tabulce_tymu -----------------*/ for (fn=0;fn<pocet_tymu;fn=fn+1) { tym_tab[fn].index[0]=((tym_tab[fn].index[1])*3+tym_tab[fn].remizy); tym_tab[fn].index[2]=(tym_tab[fn].index[3]-tym_tab[fn].obdrzene_goly); tym_tab[fn].index[5]= (int)toupper(tym_tab[fn].nazev[0]); /*print_tym(fn);*/ } //printf("\n"); /*- end-of aktualizace udaju v tabulce_tymu ----------*/ /*// END of _ loading data ////////////////////////////////////////////*/ temp_tym1=(TYM*)malloc(sizeof(TYM)); for (j=0;j<(pocet_tymu-1);j=j+1) { bbs_end=1; for (i=0;i<(pocet_tymu-1);i=i+1) { if ((prohodit(i,i+1))==1) { *temp_tym1=tym_tab[i+1]; tym_tab[i+1]=tym_tab[i]; tym_tab[i]=*temp_tym1; bbs_end=0; } } if (bbs_end==1) break; } //printf("body_sort done\n"); /*////// OUTPUT /////////////////////////////////////////////////////////*/ printf("%s",jmeno_souteze); for (fn=0;fn<pocet_tymu;fn=fn+1) { /*for (fc=0;fc<6;fc=fc+1) {printf("%d ",tym_tab[fn].index[fc]);} printf(":: ");*/ tym_tab[fn].poradi=(fn+1); print_tym(fn); } if(ps!=(pocet_soutezi-1)) {printf("\n");} //printf("ps:%d\n",ps); free((void*)temp_tym1); free((void*)tym_tab); } return 0; }

Kanonýr

Tato úloha se dá řešit pomocí analytické geometrie v rovině. Stačí určit vzdálenosti brankáře od přímek určených úsečkami HA a HB, kde H je poloha hráče, A je poloha jedné tyčky branky a B je poloha druhé tyčky branky. Pokud jsou obě vzdálenosti větší než akční rádius brankáře, brankář nemůže zabránit vstřelení gólu, a gól by tak mohl být vstřelen. Kromě brankáře však může vstřelení gólu zabránit nevhodné umístění míče. Vzhledem k přímé trajektorii míče není možné vstřelit gól z brankové čáry mimo branku.

Tedy: Pro každý případ určit obecné rovnice přímek (trajektorie míče), spočítat podle vzorce vzdálenost bodu (pozice brankáře) od nich a porovnat s akčním rádiem brankáře. Nevhodnou polohu míče pak ošetřit samostatnou podmínkou zjišťující, zda míč není na brankové čáře mimo branku.

Příklad zdrojového kódu:

program kanonyr; type tVektor = record x, y, l : extended; end; var i, N : integer; Ax, Ay, Bx, By, r, Cx, Cy, Dx, Dy, Ex, Ey : extended; a, b, c, d : extended; status : boolean; u, v : tVektor; begin readln(N); Cx := 52.5; Cy := 3.66; for i:=1 to N do begin readln; readln(Ax, Ay); readln(Bx, By, r); if (Ax - Cx = 0) then begin writeln('Nedal...'); continue; end; if (Bx+r < Ax) then begin writeln('Gol!!!'); continue; end; if (sqrt(sqr(Bx-Ax) + sqr(By-Ay)) <= r) then begin writeln('Nedal...'); continue; end; status := false; u.x := Cx - Ax; u.y := Cy - Ay; v.x := u.y * -1; v.y := u.x; Dx := Bx + v.x; Dy := By + v.y; a := (Ay - Cy) / (Ax - Cx); b := Cy - Cx*a; if (Bx - Dx = 0) then begin if (abs(Ay - By) > r) then status := true; end else begin c := (By - Dy) / (Bx - Dx); d := Dy - Dx*c; Ex := (d - b) / (a - c); Ey := a*Ex + b; if (sqrt(sqr(Ex-Bx) + sqr(Ey-By)) > r) then status := true; if (Ex > Cx) and (sqrt(sqr(Bx-Cx) + sqr(By-Cy)) > r) then status := true; end; u.x := Cx - Ax; u.y := (-1*Cy) - Ay; v.x := u.y * -1; v.y := u.x; Dx := Bx + v.x; Dy := By + v.y; a := (Ay - (-1*Cy)) / (Ax - Cx); b := (-1*Cy) - Cx*a; if (Bx - Dx = 0) then begin if (abs(Ay - By) > r) then status := true; end else begin c := (By - Dy) / (Bx - Dx); d := Dy - Dx*c; Ex := (d - b) / (a - c); Ey := a*Ex + b; if (sqrt(sqr(Ex-Bx) + sqr(Ey-By)) > r) then status := true; if (Ex > Cx) and (sqrt(sqr(Bx-Cx) + sqr(By-(-1*Cy))) > r) then status := true; end; if status then writeln('Gol!!!') else writeln('Nedal...'); end; readln; end.

Kdo vyhraje milión?

  1. Vypočítat prvních n prvočísel, kde n je počet programátorů a uložit si tato prvočísla do pole.
  2. Načíst si počet programátorů a vytvořit si kruh s načteným počtem programátorů (např. implementovaný polem), u každého lze zaznamenat, zda již byl vyřazen či nikoliv. Na začátku jsou všichni nevyřazeni.
  3. Vzít první prvočíslo z pole prvočísel (p1) a do kruhu programátorů si zaznamenat, že p1-tý programátor byl vyřazen. Vzít druhé prvočíslo (p2), popojít v kruhu o p2 programátorů a opět si zaznamenat, že programátor byl vyřazen.
  4. Předchozí bod opakovat, dokud nebude vyřazeno (n-1) programátorů. Když dojdu na konec pole, kterým je kruh implementován, vrátit se zpět na začátek a pokračovat v procházení. Již vyřazené programátory přeskakovat a jejich pozice nepočítat.
  5. Nakonec vypsat pozici v kruhu jediného zbývajícího programátora. Celý postup opakovat pro další zadané počty programátorů, dokud není zadaný počet programátorů nulový.

Příklad zdrojového kódu:

program milion; {$APPTYPE CONSOLE} var N,i,j,k:integer; pozice:array[1..3502] of boolean; m:integer; prvocisla:array[1..3502] of integer; begin prvocisla[1]:=2; prvocisla[2]:=3; for i:=3 to 3501 do begin m:=prvocisla[i-1]; repeat m:=m+1; j:=1; while(prvocisla[j]<=sqrt(m))and(m mod prvocisla[j] <> 0)do j:=j+1; until(prvocisla[j]>sqrt(m)); prvocisla[i]:=m; end; readln(N); while(N>0)do begin for i:=1 to N do pozice[i]:=true; j:=0; for i:= 1 to N-1 do begin k:=0; while(k<prvocisla[i])do begin j:=j+1; if(j>N)then j:=j-N; if(pozice[j])then begin k:=k+1; end; end; pozice[j]:=false; end; for i:=1 to N do if(pozice[i])then writeln(i); readln(N); end end.

Obdélníky

Obdélníky lze z množiny N čtverců vytvořit několika způsoby. První způsob je dát 1 až N obdélníků za sebe. Další možnost dát obdélníky do dvou řádek, přičemž v každé bude 1 až N/2 obdélníků. Další možností je dát obdélníky do třech řádek, přičemž v každé bude 1 až N/3 obdélníků a tak dále. Celkový počet obdélníků je pak součtem všech těchto (realizovatelných s daným počtem N) možností.

Celkový počet obdélníků se dá vyjádřit vzorcem: .

Příklad zdrojového kódu:

import java.util.Scanner; public class Obdelnik { private static final Scanner sc = new Scanner(System.in); public static void main(String[] args) { int N = sc.nextInt(); int pocet = N; for(int i = 2 ; i <= Math.pow(N,0.5); i++) pocet+=N/i-i+1; System.out.println(pocet); } }

Smlouva s ďáblem

  1. Načíst počet testovacích případů a pro tento počet opakovat.
  2. Načít obě čísla, zapamatovat si jejich součet.
  3. Obě čísla převrátit tak, aby jejich číslice byly pozpátku. To se dá vyřešit např. pomocí postupného celočíselného dělení deseti nebo převedením čísla na řetězec a jeho otočení.
  4. Obě otočená čísla sečíst a výsledek znovu převrátit.
  5. Je-li takto vzniklé číslo rovno nebo menší než původní součet obou zadaných čísel, ďábel vyhrál. Jinak ďábel prohrál.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> double otoc(double x) { int mist, k, i; int pom; char pole[50]; for(i=0;i<50;i++) pole[i] = 'x'; sprintf(pole, "%.0lf", x); for(i=0;pole[i]!='\0'; i++) ; //printf("\n\n"); //for(k=0;k<15;k++) printf("%c ", pole[k]); mist = i; k = i - 1; for(i=0;i < (int) (mist/2);i++,k--){ pom = (int) pole[i]; pole[i] = pole[k]; pole[k] = (char) pom; } //for(i=0;i<15;i++) printf("%c ", pole[i]); return (double) (atof(pole)); } int main(int argc, char *argv[]) { int i, N; double a, b, c; double potom, puvodne; scanf("%d", &N); for(i=0;i<N;i++) { scanf("%lf %lf", &a, &b); puvodne = (a + b); a = otoc(a); b = otoc(b); c = a + b; potom = otoc(c); if (potom <= puvodne) printf("%d: dabel vyhral\n", (int) potom); else printf("%d: dabel prohral\n", (int) potom); } return 0; }

Zloději v muzeu

V každém případě je dobré začít vytvořením mapky muzea do dvourozměrného pole na základě načtených dat. Úlohu pak lze řešit například procházením všech aktivních senzorů a na základě jejich strany a pozice určovat možné x a y souřadnice zlodějů. Protože zloději jsou dva, v úvahu může připadat více kombinací získaných souřadnic. Proto je třeba otestovat všechny kombinace x a y souřadnic dvou zlodějů, zda dávají stejnou konfiguraci zapnutých senzorů, jako je zadaná. Výsledkem bude jediná kombinace a ta odpovídá řešení úlohy, které je ještě třeba seřadit (viz zadání).

Výše uvedený postup je časově nenáročný, ale nepostihne případ, kdy jsou zloději (nebo jeden ze zlodějů) zcela (tj. ze všech stran) zakryti exponáty - v tom případě nebude nalezena žádná kombinace souřadnic zlodějů odpovídající vstupu. Pokud nastane tato situace, je možné použít další postup (hrubou silou) - postupně zloděje umisťovat na všechny možné pozice (s výjimkou pozic, kde jsou exponáty), aktivovat příslušné senzory a testovat, zda konfigurace aktivovaných senzorů odpovídá načtené konfiguraci. Tento postup je univerzální (tj. postihne všechny varianty), ale je časově náročný. Vzhledem k malé velikosti muzea ho však lze použít nejen jako doplnění algoritmu popsaného v předchozím odstavci, ale i samostatně.

Příklad zdrojového kódu:

import java.util.Scanner; public class DvaZlodeji { static int[][] muzeum; static final Scanner sc = new Scanner(System.in); static int neni = -8; static int prekazka = -1; public static void main(String[] args) { int radku = sc.nextInt(); int sloupcu = sc.nextInt(); do { muzeum = new int[radku + 1][sloupcu + 1]; int E = sc.nextInt(); for (int i = 0; i < E; i++) muzeum[sc.nextInt() - 1][sc.nextInt() - 1] = prekazka; sc.nextLine(); String[] sen = sc.nextLine().split(" "); int k = 0; int senzor; // zleva for (int i = 0; i < sen.length; i++) { if (sen[i].length() < 1) senzor = muzeum.length - 1; else senzor = Integer.parseInt(sen[i]) - 1; for (; k < senzor; k++) { for (int j = 0; j < muzeum[0].length && muzeum[k][j] != prekazka; j++) { muzeum[k][j] = neni; // na toto misto nesviti senzor, // tedy se tam urcite› nemuze // nikdo nachazet } } if (senzor < muzeum.length - 1) for (int j = 0; j < muzeum[0].length && muzeum[senzor][j] != prekazka; j++) muzeum[senzor][j]++; k++; } // zhora sen = sc.nextLine().split(" "); k = 0; for (int i = 0; i < sen.length; i++) { if (sen[i].length() < 1) senzor = muzeum[0].length - 1; else senzor = Integer.parseInt(sen[i]) - 1; for (; k < senzor; k++) { for (int j = 0; j < radku + 1 && muzeum[j][k] != prekazka; j++) { muzeum[j][k] = neni; // na toto misto nesviti senzor, // tedy se tam urcite› nemuze // nikdo nachazet } } if (senzor < muzeum[0].length - 1) for (int j = 0; j < radku + 1 && muzeum[j][senzor] != prekazka; j++) muzeum[j][senzor]++; k++; } // zprava sen = sc.nextLine().split(" "); k = 0; for (int i = 0; i < sen.length; i++) { if (sen[i].length() < 1) senzor = radku; else senzor = Integer.parseInt(sen[i]) - 1; for (; k < senzor; k++) { for (int j = sloupcu - 1; j >= 0 && muzeum[k][j] != prekazka; j--) { muzeum[k][j] = neni; // na toto misto nesviti senzor, // tedy se tam urcite› nemuze // nikdo nachazet } } if (senzor < radku) if (muzeum[senzor][sloupcu] == 0) for (int j = sloupcu - 1; j >= 0 && muzeum[senzor][j] != prekazka; j--) muzeum[senzor][j]++; k++; } // zdola sen = sc.nextLine().split(" "); k = 0; for (int i = 0; i < sen.length; i++) { if (sen[i].length() < 1) senzor = sloupcu; else senzor = Integer.parseInt(sen[i]) - 1; for (; k < senzor; k++) { for (int j = radku - 1; j >= 0 && muzeum[j][k] != prekazka; j--) { muzeum[j][k] = neni; // na toto misto nesviti senzor, // tedy se tam urcite nemuze // nikdo nachazet } } if (senzor < sloupcu) if (muzeum[radku][senzor] == 0) for (int j = radku - 1; j >= 0 && muzeum[j][senzor] != prekazka; j--) muzeum[j][senzor]++; k++; } Spojka.pocet = 0; boolean prvni = true; int pocetDvojek = 0, pocetJednicek = 0; int porovnavaci = 0; int[] naRadek = new int[radku]; for (int i = 0; i < muzeum.length - 1; i++) { for (int j = 0; j < muzeum[i].length - 1; j++) { if (muzeum[i][j] >= porovnavaci) { naRadek[i]++; switch (muzeum[i][j]) { case 1: pocetJednicek++; if (pocetJednicek + pocetDvojek >= 2) porovnavaci = Math.max(1, porovnavaci); break; case 2: pocetDvojek++; if (pocetDvojek >= 2) porovnavaci = 2; break; } new Spojka(i, j, prvni); prvni = false; } } } System.out.println(); tist(); if (Spojka.pocet == 2) { System.out.print(Spojka.prvni); } else { Spojka s = Spojka.prvni; Spojka predchozi = null; for (s = Spojka.prvni; s != null; predchozi = s,s = s.s) { if (muzeum[s.R][s.S] < porovnavaci) { naRadek[s.R]--; Spojka.odeber(predchozi, s); } } for (s = Spojka.prvni; s != null; s = s.s) { if (naRadek[s.R] == 1) { for (int i = s.S + 1; i < sloupcu; i++) muzeum[s.R][i]--; for (int i = s.S - 1; i >= 0; i--) muzeum[s.R][i]--; for (int i = s.R + 1; i < radku; i++) muzeum[i][s.S]--; for (int i = s.R - 1; i >= 0; i--) muzeum[i][s.S]--; } } predchozi = null; tist(); for (s = Spojka.prvni; s != null; predchozi = s,s = s.s) { if (muzeum[s.R][s.S] < porovnavaci) { naRadek[s.R]--; Spojka.odeber(predchozi, s); } } System.out.print(Spojka.prvni); } radku = sc.nextInt(); sloupcu = sc.nextInt(); } while (radku != 0 && sloupcu != 0); } static private void tist() { /* for (int i = 0; i < muzeum.length - 1; i++) { for (int j = 0; j < muzeum[i].length - 1; j++) { System.out.format("%2d, ", muzeum[i][j]); } System.out.println(); }*/ } static class Spojka { public static int pocet; public static Spojka prvni; private static Spojka minuly; public final int S, R; public Spojka s; Spojka(int r, int s, boolean prvni) { pocet++; S = s; R = r; if (prvni) Spojka.prvni = this; else Spojka.minuly.s = this; Spojka.minuly = this; } public static void odeber(Spojka predchozi, Spojka odebirany) { pocet--; if (predchozi == null) Spojka.prvni = odebirany.s; else predchozi.s = odebirany.s; } @Override public String toString() { String s = (R+1) + " " + (S+1) + "\n"; if (this.s != null) s += this.s.toString(); return s; } } }

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ů.

Souostroví

Pro každý ostrov vyřešíme úlohu zvlášť. Síť silnic na každém ostrově lze chápat jako neorientovaný souvislý graf bez nadbytečných hran. Hledáme nejdelší cestu - použijeme prohledávání do hloubky:

Příklad zdrojového kódu:

program reseni; const MAXN = 2010; type THrana = record l : longint; c : longint; end; type THrany = array [1..MAXN, 1..MAXN] of THrana; var N : longint; var a, b, l, i, j : longint; var hrany : THrany; var maxd : longint; var visited : array [1..MAXN] of boolean; var poctyhran : array [1..MAXN] of integer; procedure projdi( i : longint; d : longint ); var m : longint; begin for m := 1 to poctyhran[i] do begin if ( not visited[hrany[i,m].c] ) then begin if ( ( d + hrany[i,m].l ) > maxd ) then begin maxd := d + hrany[i,m].l; end; visited[hrany[i,m].c] := true; projdi( hrany[i,m].c, d + hrany[i,m].l ); end; end; end; procedure vyres(); begin maxd := 0; for i := 1 to N do begin //jdeme z vrcholu for j := 1 to N do begin visited[j] := false; end; visited[i] := true; projdi(i, 0); end; writeln( maxd ); end; begin readln( N ); while ( N <> 0 ) do begin for i := 1 to N do begin poctyhran[i] := 0; end; while ( not(eoln) ) do begin readln( a, b, l ); poctyhran[a] := poctyhran[a] + 1; hrany[a,poctyhran[a]].l := l; hrany[a, poctyhran[a]].c := b; poctyhran[b] := poctyhran[b] + 1; hrany[b,poctyhran[b]].l := l; hrany[b, poctyhran[b]].c := a; end; vyres(); readln; readln(N); end; end.

Pokladna

V příkladu hledáme nejnižší nevyplatitelnou částku, tedy nejnižšší částku, kterou nelze poskládat z dostupných mincí. Začneme od nejmenších mincí. Pokud mám například 1 korunu 1 dvoukorunu a 1 pětikorunu, nejnižší částka, kterou už nemůžu vyplatit je 4 koruny, protože 1 + 2 = 3 a 5 už je moc.

Hledáme tedy případ (od nejmenších mincí), kdy součet menších mincí je alespoň o 2 menší než hodnota nejbližší vyšší mince. Nesmíme však zapomenout na možnost, že máme dostatek všech potřebných mincí pro vytvoření libovolné částky. V tom případě je nejnižšší nevyplatitelná částka o 1 větší než celkový součet všech mincí.

Příklad zdrojového kódu:

#include <stdio.h> #include <math.h> int minci[6]; /*1,2,5,10,20,50*/ int Tminci[6]; int hodn[6]={1,2,5,10,20,50}; int max = 50*1000+20*1000+10*1000+5*1000+2*1000+1000; int jde_vypl(int castka) { int fi; int zbytek; zbytek = castka; for (fi=5;fi>=0;fi=fi-1) { /*printf("na '%d' je %d minci, deleni: %d\n",hodn[fi],minci[fi],zbytek/hodn[fi]);*/ while (((zbytek/hodn[fi])>0)&&(minci[fi]!=0)) {zbytek= zbytek - hodn[fi]; minci[fi]= minci[fi] -1; } /*printf("po '%d' zbylo: %d\n",hodn[fi],zbytek);*/ } if (zbytek==0) return 1; else return 0; } int main() { int n,fa,fm,ft; scanf("%d",&n); for (fa=0;fa<n;fa+=1) { scanf("%d %d %d %d %d %d",&Tminci[0],&Tminci[1],&Tminci[2],&Tminci[3],&Tminci[4],&Tminci[5]); for (fm=1;fm<max;fm+=1) { for (ft=0;ft<6;ft+=1) { minci[ft]=Tminci[ft]; } if ((jde_vypl(fm))==0) {printf ("%d\n",fm); break; } } } }

Sněhulák

Máme vypočítat výšku sněhuláka v mm, když známe množství sněhu v litrech a víme, že poměr poloměrů největší, střední a nejmenší koule je 1 : 3/4 : 9/16. Poloměr pak lze vyjádřit z objemu:

Výšku sněhuláka pak můžeme vypočítat následovně (nesmíme zapomenout snížit sněhuláka podle zadání o 10 % a správně převést jednotky):

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> #include <math.h> double cuberoot(double x) { return exp(log(x)/3.0); } int main(int argc, char** argv) { long N, V; double pi = 3.1415926535897; double R, f, V2; double mult = (1.0 + pow(3.0/4.0, 3.0) + pow(3.0/4.0, 6.0)); scanf("%d", &N); while (N--) { scanf("%ld", &V); V2 = (double)V; R = cuberoot(V2 / ((4.0/3.0) * pi * mult)) * 100.0; R *= (1.0 + 3.0/4.0 + 9.0/16.0) * 2.0 * 0.9; f = floor(R); //printf("%f\n", R); if (R - f >= 0.5) { printf("%ld\n", (long)f + 1); } else { printf("%ld\n", (long)f); } } return 0; }

Šachové věže

Úkolem je zjistit kolika způsoby lze rozestavit N věží na šachovnici N x N, tak aby se neohrožovaly. Začneme tedy umisťovat věže např. po řádkách. Do každé řádky můžeme umístit maximálně jednu (jinak by se věže ohrožovaly). Do první řádky můžeme věž umístit libovolně, tj. N způsoby. Do druhé řádky můžeme dát věž libovolně, kromě sloupce, ve kterém je věž v prvním řádku, tedy N-2 způsoby. Do třetí řádky můžeme dát věž libovolně, kromě sloupců, ve kterých je věž v prvním a druhém řádku, a tak dále. Celkový počet rozmíštění je tedy N * (N - 1) * ... * 1 = N!

Příklad zdrojového kódu:

import java.util.*; public class sachy{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); while(N!=0){ System.out.println(fac(N)); N = sc.nextInt(); } } public static int fac(int num){ int res=1; for (int i=2; i<=num; i++){ res = res*i; } return res; } }