PilsProg 2013

Výsledky kvalifikace

PříjmeníJménoSplněných úlohČasFinále
LáskaJiří6109,634postupuje do finále
HájekDalimil6670,348postupuje do finále
ŠimsaŠtěpán62 291,451postupuje do finále
LejnarJan4875,894postupuje do finále
ZindulkaMikuláš4928,757postupuje do finále
HübschOndřej42 554,979postupuje do finále
SoukupJan42 589,841postupuje do finále
BoháčRichard3510,199postupuje do finále
DavídekHynek255,041postupuje do finále
PřevrátilMichal2157,949postupuje do finále
BalákVojtěch2276,746postupuje do finále
ŠvecKamil2563,733postupuje do finále
MacháčekDominik2923,461postupuje do finále
NejdlMichal178,431
HálaVáclav1129,226
NguyenThi Tuyet Trang1269,786
MazanecMartin1269,849
KluzáčekMichal1284,083
SejkoraVojtěch1321,349
JáchymováAnežka1435,101

Výsledky finále

PříjmeníJménoSplněných úlohČas
ŠimsaŠtěpán55,271
HübschOndřej59,978
SoukupJan36,023
ZindulkaMikuláš23,898
HájekDalimil24,108
BoháčRichard24,576
LáskaJiří25,068
DavídekHynek11,198
MacháčekDominik11,380
BalákVojtěch00,000
LejnarJan00,000
PřevrátilMichal00,000
ŠvecKamil00,000

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

Poznámka:
Finalisté Vojtěch Balák, Michal Převrátil a Kamil Švec se finálové soutěže nezúčastnili.

Ilustrační úlohy:

NázevOznačeníÚspěšných řešitelů
AplusB080540
AxB070437
Největší ze tří celých čísel080633
Pascalův trojúhelník070327

Kvalifikační úlohy:

NázevOznačeníÚspěšných řešitelů
Symetrie131113
Karambol13127
Jezdec131318
Hacker13149
Mosty13153
Setkání13164

Finálové úlohy:

NázevOznačeníÚspěšných řešitelů
Vzorec lásky13219
Profesoři13225
Kostky13233
Cestovatel13244
Týmy13252

A jaké bylo finále?

Finále začíná ...

Harmonogram PilsProg 2013

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.

Symetrie

  1. Pro každý testovací případ si vytvořit pole uchovávající souřadnice (x a y) jednotlivých načtených bodů.
  2. Pokud je bodů 0, střed symetrie neexistuje. Pokud je 1 bod, střed symetrie existuje. Pro více bodů:
  3. Seřadit pole bodů podle souřadnice x. Body se stejnou souřadnicí x dále seřadit podle souřadnice y.
  4. Procházet pole bodů od začátku až od konce a počítat souřadnice středu pro jednotlivé dvojice bodů. Nejprve pro první a poslední bod, pak pro druhý a předposlední bod atd.
  5. Průběžně porovnávat souřadnice vypočtených středů. Jakmile je vypočten střed o jiných souřadnicích než předchozí středy, končit - střed symetrie neexistuje.
  6. Pokud po průchodu celého pole bodů měly všechny vypočtené středy stejné souřadnice, střed symetrie existuje.

Příklad zdrojového kódu:

import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public final class Symetrie { private static int[][][] scannPoints() { Scanner s = new Scanner(System.in); byte p = s.nextByte(); int[][][] points = new int[p][][]; for (byte i = 0; i < p; i++) { short n = s.nextShort(); points[i] = new int[n][2]; for (int j = 0; j < n; j++) { points[i][j][0] = s.nextInt(); points[i][j][1] = s.nextInt(); } } s.close(); return points; } public static void main(String[] args) { int[][][] points = scannPoints(); for (byte i = 0; i < points.length; i++) { boolean symetrical = true; Arrays.sort(points[i], new Comparator<int[]>(){ @Override public int compare(int[] x, int[] y) { return y[0] - x[0] == 0?y[1] - x[1]:y[0] - x[0]; } }); for(short j = 1; j < points[i].length/2 + 1; j++) { if (points[i][j-1][0] - points[i][j][0] != points[i][points[i].length-j-1][0] - points[i][points[i].length-j][0] || points[i][j-1][1] - points[i][j][1] != points[i][points[i].length-j-1][1] - points[i][points[i].length-j][1]) { symetrical = false; break; } } System.out.println(symetrical?"ano":"ne"); } } }

Karambol

Tato úloha se dá řešit pomocí pravoúhlého trojúhelníka. Je třeba si uvědomit, že odrazy jsou dokonalé (energie se neztrácí a úhel odrazu se rovná úhlu dopadu). Pak si lze situaci tranformovat na případ, kdy se koule pohybuje pořád rovně přes několik přilehlých karambolových stolů (viz obrázek). Z počtu odrazů od horizontální a vertikální stěny a délky stěn lze pak spočítat délky odvěsen pravoúhlého trojúhelníka (viz obrázek). Z nich lze určit úhel i délku přepony, což je dráha uraženaná koulí. Tuto vzdálenost stačí vydělit časem, čímž se získá rychlost. Tyto výpočty je třeba provést pro každý testovací případ.

Příklad zdrojového kódu:

#include<stdio.h> #define _USE_MATH_DEFINES #include <math.h> #ifndef M_PI #define M_PI 3.1415926535897932385 #endif typedef struct { float u; float v; } result; result calc(int a,int b,int t,int m,int n) { result ret; /*printf("%d %d %d %d %d",a,b,t,m,n);*/ ret.v = sqrt(pow(a*m,2)+pow(b*n,2))/t; ret.u = atan(((float)(b*n))/(a*m))/M_PI*180; return ret; } int main(int argc,char** argv) { unsigned int i,count; int a,b,t,m,n; result r; scanf("%u",&count); for(i=0;i<count;i++) { scanf("%d%d%d%d%d",&a,&b,&t,&m,&n); r = calc(a,b,t,m,n); printf("%.2f %.2f\n",r.u,r.v); } return 0; }

Jezdec

Nejprve je třeba si uvědomit, jak mohou být jezdci poskládáni nejtěsněji vedle sebe na velké šachovnici (jinými slovy, jakým nejhustějším "vzorem" jezdců lze šachovnici vyplnit). Takový vzor je znázorněn na obrázku (vpravo). V každém sloupci/řádku se tedy střídá políčko s jezdcem a prázdné políčko. V tomto okamžiku stačí spočítat, kolik je jezdců celkem, k čemuž se využijí rozměry šachovnice. Je však třeba dát pozor na speciální případy, kdy menší rozměr šachovnice je roven 2 nebo 1, jak je znázorněno na obrázku (uprostřed, respektive vlevo). V těchto případech jsou vzory jezdců jiné, což je třeba zohlednit. Výpočet je třeba zopakovat pro každý testovací případ.

Příklad zdrojového kódu:

program project1; {$mode objfpc}{$H+} uses {$IFDEF UNIX}{$IFDEF UseCThreads} cthreads, {$ENDIF}{$ENDIF} Classes { you can add units after this }; var m,n,x:longint; j:integer; begin repeat read(m); if m<>0 then begin read; read(n); if (n>m) then begin x:=n; n:=m; m:=x; end; if (m=1) or (n=1) then j:=m else if (n=2) then if (m mod 4 = 1) then j:=m+1 else j:=(round(m/4 +0.2)) *4 else j:=(m*n) div 2 + (m*n) mod 2; writeln(j); end until m=0 ; readln; end.

Hacker

Jednou z možností, jak tuto úlohu řešit, je rekonstruovat si všechny permutace a podle čísla řádky určit původní zprávu. Toho lze docílit následujím postupem:

  1. Vytořit pole znaků a pole řetězců o délkách odpovídající počtu znaků zakódované zprávy, která je na vstupu.
  2. Pole znaků naplnit znaky zakódované zprávy. Pole řětezců rovněž, výsledkem tak je pole jednoznakových řetězců.
  3. Pole řetězců seřadit podle abecedy. Tím se získá první (pole řetezců) a poslední (pole znaků) sloupec všech permutací, viz obrázek (vlevo).
  4. Protože permutace jsou cyklické, lze zřetězením posledního a prvního znaku (tj. znaku z pole znaků a řetězce z pole řetězců) určit první dva znaky všech permutací. Tím v poli řetězců vzniknou dvouznakové řetězce. Seřadit toto pole řetězců.
  5. Protože permutace jsou cyklické, lze zřetězením posledního znaku a odpovídajícího řetězce určit první tři znaky všech permutací. Tyto trojznakové řetězce v poli řetězců opět seřadit.
  6. Postup opakujeme, dokud délky řetězců nedosáhnou délky zakódované zprávy. V tomto okamžiku byly vytvořeny všechny cyklické permutace, viz obrázek (vpravo).
  7. Vybrat řádku (permutaci) podle čísla řádky ze vstupu. Tato permutace je původní zprávou a tedy výstupem programu.

Příklad zdrojového kódu:

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; char** tab; char in[11111]; int line,n=0,lev; bool cmp(const char* a, const char* b) { return strcmp(a+lev, b+lev) < 0; } int main() { scanf("%d\n", &line); char c; while(scanf("%c", &c) == 1) { if(c >= 'A' && c <= 'z') in[n++] = c; } tab = (char**)malloc(sizeof(char*)*n); for(int i = 0; i < n; i++) tab[i] = (char*)malloc(sizeof(char)*(n+1)); for(int i = 0; i < n; i++) for(int j = 0; j < n+1; j++) tab[i][j] = '\0'; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) tab[j][n-i-1] = in[j]; lev = n-i-1; sort(tab, tab+n, cmp); } printf("%s\n", tab[line-1]); return 0; }

Mosty

  1. Pro každý testovací případ opakovat:
  2. Vytvořit dvourozměrné celočíselné pole pro uložení mapy a načíst do něj mapu ze vstupu. Moře (.) lze ukládat např. jako -1 a pevninu (#) jako 0.
  3. Projít celé dvourozměrné pole a z každé pevniny (hodnota 0) provést osmisměrné záplavové vyplňování (rekurzivní algoritmus pro vyplnění všech okolních buněk, které mají stejnou hodnotu) kladným číslem. Pro první použít 1, pro druhé 2, atd. Tím se zajistí, že každý souvislý ostrov se bude skládat z buněk se stejným kladným číslem. Zároveň se tím zjistí počet ostrovů.
  4. Pokud je ostrovů 0 nebo 1, mosty nejsou třeba. Jinak je třeba spočítat délku mostů a počet nespojených souostroví:
  5. Najít všechny vertikální a všechny horizontální mosty. Projít dvourozměrné pole po sloupcích a počítat počet buněk s mořem mezi buňkami s pevninou. Každý nalezený most si uložit s čísly obou ostrovů a délkou. Pak projít dvourozměrné pole po řádcích a provést totéž. Je třeba dát si pozor na to, že mosty nevedou v buňkách pole, ale mezi nimi. Je proto potřeba kontrolovat najednou dva sloupce/řádky.
  6. Pokud nebyl nalezen ani jeden most, mosty nelze sestrojit. Pokud byl nalezen alespoň jeden, zjistit, zda lze postavit všechny potřebné a jejich délku:
  7. Seřadit mosty vzestupně podle délky. Vytvořit pomocné celočíselné pole o velikosti odpovídající počtu ostrovů. Pole naplnit čísly ostrovů (např. pro 5 ostrovů vznikne pole s prvky 1, 2, 3, 4, 5). Na začátku je tedy předpoklad, že všechny ostrovy jsou nespojené a počet nespojených souostroví tak odpovídá počtu ostrovů.
  8. Procházet postupně mosty. Pro každý most využít čísla prvního a druhého ostrova, které spojuje, jako indexy do pomocného pole. Pokud jsou v obou buňkách pomocného pole různá čísla, ostrovy jestě nejsou propojené. V tom případě obě buňky naplnit stejným číslem (ostrova s nižším číslem), snížit počet nespojených souostroví a do celkové délky mostů přičíst délku mostu. Pokračovat, dokud není počet nespojených souostroví roven 1 nebo dokud nedojdou mosty.
  9. Podle počtu mostů a počtu nespojených souostroví vypsat příslušný výstup.

Příklad zdrojového kódu:

/** @author Dalda */ import java.util.*; public class Mosty { static Scanner sc = new Scanner(System.in); //SMER DOLU = vetsi I (=Y) static final int[][] tah = //zvysovani I(=Y) a J(=X) {{0, 1}, {0, -1}, {1, 0}, {-1,0}, {-1, 1}, {-1, -1}, {1, 1}, {1, -1}}; static int[][] pole; static int r, s; static int pocetOstrovu; static int celkovaDelka; static int pocetMostu; static ArrayList<Ostrov> ostrovy; static int[][] vzdalen; public static void main(String[] args) { int n = sc.nextInt(); for(int oblast = 1; oblast <= n; oblast++){ r = sc.nextInt(); s = sc.nextInt(); sc.nextLine(); pole = new int[r][s]; //-5 = ostrov; 0 = more for(int i = 0; i < r; i++){ //nacteme char[] radka = sc.nextLine().toCharArray(); for(int j = 0; j < s; j++){ pole[i][j] = radka[j] == '#' ? -5 : 0; } } pocetMostu = 0; celkovaDelka = 0; pocetOstrovu = 0; ostrovy = new ArrayList<Ostrov>(); //dfs na hledani ostrovu spocitejOstrovy(); if(pocetOstrovu < 2){ System.out.println("Oblast "+oblast); System.out.println("Mosty nejsou treba."); continue; } //sestaveni 4 hranic kazdeho ostrova for(int i = 0; i < ostrovy.size(); i++){ hranice(i); } //staveni nejkratsich mostu vzdalen = new int[pocetOstrovu][pocetOstrovu]; for(int i = 0; i < vzdalen.length; i++){ Arrays.fill(vzdalen[i], -1); } for(int i = 0; i < pocetOstrovu; i++){ //pro kazdy ostrov minDelky(i); //spocitej min delku k ostatnim } //minimalni kostra init ArrayList<Most> kSerazeni = new ArrayList<Most>(); for(int i =0; i < pocetOstrovu; i++){ for(int j = 0; j<pocetOstrovu; j++){ if(i == j) continue; if(vzdalen[i][j] != -1 && vzdalen[i][j] != 0){ kSerazeni.add(new Most(i, j, vzdalen[i][j])); } } } Most[] noveSeraz = new Most[0]; noveSeraz = kSerazeni.toArray(noveSeraz); //Algoritmus pro tvorbu minimalni kostry - mosty a ostrovy Arrays.sort(noveSeraz); int[] keKostre = new int[pocetOstrovu]; for(int i =0; i< pocetOstrovu; i++) keKostre[i] = i; for(int i =0; i < noveSeraz.length && pocetOstrovu > 1;i++){ if(keKostre[noveSeraz[i].from] != keKostre[noveSeraz[i].to]){ celkovaDelka += noveSeraz[i].delka; pocetMostu++; int w1 = keKostre[noveSeraz[i].from]; int w2 = keKostre[noveSeraz[i].to]; for(int j = 0; j < keKostre.length; j++){ if(keKostre[j] == w2){ keKostre[j] = w1; } } pocetOstrovu--; } } //tisk vysledku System.out.println("Oblast "+oblast); if(celkovaDelka == 0){ System.out.println("Mosty nelze postavit."); } else{ System.out.println("Mostu je: "+pocetMostu+", celkove delky "+celkovaDelka+"."); } if(pocetOstrovu > 1){ System.out.println("Nespojenych souostrovi: "+pocetOstrovu); } } //for oblast } //main static void minDelky(int os){ //min delky z tohoto ostrovu Ostrov oO = ostrovy.get(os); Queue<Bodik> q = new LinkedList<Bodik>(); for(Bod i : oO.horni) q.add(new Bodik(i.x, i.y, Bodik.UP, 0)); for(Bod i : oO.dolni) q.add(new Bodik(i.x, i.y, Bodik.DOWN, 0)); while(!q.isEmpty()){ //nahoru a dolu bfs Bodik b = q.remove(); if(pole[b.y][b.x] != os+1 && pole[b.y][b.x] != 0){ if(vzdalen[os][pole[b.y][b.x]-1] == -1 || vzdalen[os][pole[b.y][b.x]-1] > b.vzdal-1){ vzdalen[os][pole[b.y][b.x]-1] = b.vzdal-1; } } if(b.x-1 >= 0){ if(pole[b.y][b.x-1] != os+1 && pole[b.y][b.x-1] != 0){ if(vzdalen[os][pole[b.y][b.x-1]-1] == -1 || vzdalen[os][pole[b.y][b.x-1]-1] > b.vzdal-1){ vzdalen[os][pole[b.y][b.x-1]-1] = b.vzdal-1; } } } if(b.x+1 < s){ if(pole[b.y][b.x+1] != os+1 && pole[b.y][b.x+1] != 0){ if(vzdalen[os][pole[b.y][b.x+1]-1] == -1 || vzdalen[os][pole[b.y][b.x+1]-1] > b.vzdal-1){ vzdalen[os][pole[b.y][b.x+1]-1] = b.vzdal-1; } } } if(b.typ == Bodik.UP && b.y-1 >= 0){ q.add(new Bodik(b.x, b.y-1, b.typ, b.vzdal+1)); } else if(b.typ == Bodik.DOWN && b.y+1 < r){ q.add(new Bodik(b.x, b.y+1, b.typ, b.vzdal+1)); } } for(Bod i : oO.leva) q.add(new Bodik(i.x, i.y, Bodik.LEFT, 0)); for(Bod i : oO.prava) q.add(new Bodik(i.x, i.y, Bodik.RIGHT, 0)); while(!q.isEmpty()){ //vlevo a vpravo bfs Bodik b = q.remove(); if(pole[b.y][b.x] != os+1 && pole[b.y][b.x] != 0){ if(vzdalen[os][pole[b.y][b.x]-1] == -1 || vzdalen[os][pole[b.y][b.x]-1] > b.vzdal-1){ vzdalen[os][pole[b.y][b.x]-1] = b.vzdal-1; } } if(b.y-1 >= 0){ if(pole[b.y-1][b.x] != os+1 && pole[b.y-1][b.x] != 0){ if(vzdalen[os][pole[b.y-1][b.x]-1] == -1 || vzdalen[os][pole[b.y-1][b.x]-1] > b.vzdal-1){ vzdalen[os][pole[b.y-1][b.x]-1] = b.vzdal-1; } } } if(b.y+1 < r){ if(pole[b.y+1][b.x] != os+1 && pole[b.y+1][b.x] != 0){ if(vzdalen[os][pole[b.y+1][b.x]-1] == -1 || vzdalen[os][pole[b.y+1][b.x]-1] > b.vzdal-1){ vzdalen[os][pole[b.y+1][b.x]-1] = b.vzdal-1; } } } if(b.typ == Bodik.LEFT && b.x-1 >= 0){ q.add(new Bodik(b.x-1, b.y, b.typ, b.vzdal+1)); } else if(b.typ == Bodik.RIGHT && b.x+1 < s){ q.add(new Bodik(b.x+1, b.y, b.typ, b.vzdal+1)); } } } static void hranice(int ostrovNum){ Ostrov a = ostrovy.get(ostrovNum); //horni Bod[] pickA = new Bod[a.maxX-a.minX +1]; for(int i = a.minX; i <= a.maxX; i++){//pro kazdy sloupec spocitej i int pomoc = a.minY; while(pole[pomoc][i] != ostrovNum+1) pomoc++; pickA[i-a.minX] = new Bod(i, pomoc); } ostrovy.get(ostrovNum).horni = pickA; //dolni Bod[] pickB = new Bod[a.maxX-a.minX +1]; for(int i = a.minX; i <= a.maxX; i++){//pro kazdy sloupec spocitej i int pomoc = a.maxY; while(pole[pomoc][i] != ostrovNum+1) pomoc--; pickB[i-a.minX] = new Bod(i, pomoc); } ostrovy.get(ostrovNum).dolni = pickB; //vlevo Bod[] pickC = new Bod[a.maxY-a.minY +1]; for(int i = a.minY; i <= a.maxY; i++){//pro kazdy radek spocitej j int pomoc = a.minX; while(pole[i][pomoc] != ostrovNum+1) pomoc++; pickC[i-a.minY] = new Bod(pomoc, i); } ostrovy.get(ostrovNum).leva = pickC; //vpravo Bod[] pickD = new Bod[a.maxY-a.minY +1]; for(int i = a.minY; i <= a.maxY; i++){//pro kazdy radek spocitej j int pomoc = a.maxX; while(pole[i][pomoc] != ostrovNum+1) pomoc--; pickD[i-a.minY] = new Bod(pomoc, i); } ostrovy.get(ostrovNum).prava = pickD; } static void spocitejOstrovy(){ for(int i = 0; i < r; i++){ for(int j = 0; j<s; j++){ if(pole[i][j] == -5){ ostrovy.add(new Ostrov()); dfs(i, j); pocetOstrovu++; } } } } static void dfs(int i, int j){ pole[i][j] = pocetOstrovu+1; if(j < ostrovy.get(pocetOstrovu).minX) ostrovy.get(pocetOstrovu).minX = j; if(j > ostrovy.get(pocetOstrovu).maxX) ostrovy.get(pocetOstrovu).maxX = j; if(i < ostrovy.get(pocetOstrovu).minY) ostrovy.get(pocetOstrovu).minY = i; if(i > ostrovy.get(pocetOstrovu).maxY) ostrovy.get(pocetOstrovu).maxY = i; for(int t = 0; t < tah.length;t++){ int a = i+tah[t][0]; int b = j+tah[t][1]; if(a >= 0 && b >= 0 && a < r && b < s){ if(pole[a][b] == -5){ dfs(a,b); } } } } } class Bodik{ int x, y; int typ; //1 = nahoru 2 = dolu 3 = vlevo 4 = vpravo int vzdal; static final int UP = 1; static final int DOWN = 2; static final int LEFT = 3; static final int RIGHT = 4; public Bodik(int x, int y, int typ, int vzdal){ this.x = x; this.y = y; this.typ = typ; this.vzdal = vzdal; } } class Bod{ int x, y; public Bod(int x, int y){ this.x = x; this.y = y; } public String toString(){ return x+"-"+y; } } class Ostrov{ int minX; int minY; int maxX; int maxY; Bod[] horni, dolni, leva, prava; public Ostrov(){ this.minX = Integer.MAX_VALUE; this.minY = Integer.MAX_VALUE; this.maxX = Integer.MIN_VALUE; this.maxY = Integer.MIN_VALUE; } } class Most implements Comparable<Most> { int from; int to; int delka; public Most(int from, int to, int delka){ this.from = from; this.to = to; this.delka = delka; } @Override public int compareTo(Most b){ if(this.delka < b.delka) return -1; else if(this.delka == b.delka) return 0; else return 1; } }

Setkání

  1. Vytvořit si třídu/strukturu/záznam pro uložení linky, jejích zastávek a sousedních linek. Načíst linky a zastávky. Podle zastávek vyskytujících se na více linkách naplnit strukturu linek a sousedních linek. Tím vznikne neorientovaný graf.
  2. Vytvořit si matici počtu přestupů mezi zastávkami. Pomocí procházení do šířky grafu linek určit počty přestupů mezi zastávkami a uložit je do vytvořené matice.
  3. Vytvořit si třídu/strukturu/záznam pro uložení kamaráda (množství peněz, permanentka, startovací zastávka) a načíst všechny kamarády.
  4. Pro každou zastávku spočítat, kolik je potřeba jízdenek pro všechny kamarády, aby se do této zastávky dostali. K tomu lze využít známé počty přestupů mezi zastávkami, aktuální zkoumanou zastávku a startovací zastávku každého kamaráda.
  5. Průběžně si pamatovat zastávku, pro kterou byl počet jízdenek nejmenší. Po průchodu všech zastávek je výsledkem zastávka s minimálním počtem jízdenek.
  6. Je třeba dát pozor na speciální případy. Zastávka nelze použít pro setkání, pokud se na ní z libovolné startovací zastávky kamarádů nedá dostat, nebo pokud na to některý z kamarádů bez permanentky nemá dostatek peněz. Pokud toto platí pro všechny zastávky, nelze setkání uskutečnit.

Příklad zdrojového kódu:

#include<cstdio> #include<algorithm> using namespace std; #define INF 1000000000 int N,M,L; int link[105]; int len[105][105]; int K; int gold[105],start[105],perm[105]; int main(){ scanf("%d%d",&N,&M); int i,j,k; for(i=0;i<N;i++){ for(j=0;j<N;j++) len[i][j]=INF; len[i][i]=0; } for(i=0;i<M;i++){ scanf("%d",&L); for(j=0;j<L;j++) scanf("%d",link+j); for(j=0;j<L;j++) for(k=0;k<L;k++){ if(j!=k) len[link[j]-1][link[k]-1]=1; } } for(k=0;k<N;k++) for(i=0;i<N;i++) for(j=0;j<N;j++) len[i][j]=min(len[i][j],len[i][k]+len[k][j]); // for(i=0;i<N;i++){ for(j=0;j<N;j++) printf("%d ",len[i][j]); printf("\n"); } scanf("%d",&K); for(i=0;i<K;i++){ scanf("%d%d%d",gold+i,start+i,perm+i); gold[i]/=16; if(perm[i]==1) gold[i]=INF-1; } int best,besti,sum; best=INF; for(i=0;i<N;i++){ sum=0; for(k=0;k<K;k++){ if(len[start[k]-1][i]>gold[k]) break; if(perm[k]==0) sum+=len[start[k]-1][i]; } if(k==K && sum<best){ best=sum; besti=i+1; } } if(best<INF) printf("%d %d\n",besti,16*best); else printf("0\n"); return 0; }

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

Vzorec lásky

Zadána dvě jména složená z různých znaků, zajímají nás pouze veká a malá písmena:

Příklad zdrojového kódu:

import java.util.*; import java.io.*; public class Main { private static int hodnotaJmena(String jmeno){ int ret = 0; for(int i = 0; i < jmeno.length(); i++){ if(jmeno.charAt(i) >= 'a' && jmeno.charAt(i) <= 'z') ret += (jmeno.charAt(i) - 'a' + 1); } return ret; } private static int soucet(int n){ int ret = 0; while(n > 0){ ret += n % 10; n /= 10; } if(ret < 10) return ret; return soucet(ret); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String jmeno1 = sc.nextLine().toLowerCase().trim(); String jmeno2 = sc.nextLine().toLowerCase().trim(); int jm1 = hodnotaJmena(jmeno1); int jm2 = hodnotaJmena(jmeno2); int vysl1 = soucet(jm1); int vysl2 = soucet(jm2); //System.out.println(vysl1 + " " + vysl2); float ret = (vysl1 > vysl2 ? (float)vysl2 / vysl1 : (float)vysl1 / vysl2) * 100; System.out.println((int)ret + " %"); } }

Profesoři

V příkladu máme zadáno nejnižší a nejvyšší procento profesorů mezi akademickými pracovníky. Hledáme počet pracovníků tak, aby procento profesorů bylo mezi zadanými hranicemi (ne včetně):

Příklad zdrojového kódu:

var i,j,a,b:longint; c,d,p,q:real; begin readln(p,q); a:=0; for i:=1 to 10001 do begin for j:=1 to i do begin c:=j/i*100; if (c>p) and (c<q)and (a=0) then begin a:=i; end; end; end; writeln(a); readln; end.

Kostky

Máme určit, z kolika kostek s různobaravnými stěnami ze postavit na sebe tak, aby vznikla věž, kdy každá boční stěna je jednobarevná:

Příklad zdrojového kódu:

#include<cstdio> int n,m; char dice[1005][10],ch; bool is[1005][15]; int i,j,k,l; char col[10]={'A','B','F','H','L','M','O','R','S','Z'}; bool ok; int num,maxnum; int main(){ scanf("%d\n",&n); for(i=0;i<n;i++){ for(j=0;j<6;j++){ scanf("%c",&dice[i][j]); for(k=0;k<10;k++) if(col[k]==dice[i][j]) is[i][k]=true; } scanf("%c",&ch); } // for(i=0;i<n;i++) for(j=0;j<6;j++) printf("%c\n",dice[i][j]); maxnum=0; for(i=0;i<10;i++){ for(j=0;j<10;j++){ if(i==j) continue; for(k=0;k<10;k++){ if(k==i || k==j) continue; for(l=0;l<10;l++){ if(l==i || l==j || l==k) continue; num=0; for(m=0;m<n;m++){ if(!is[m][i] || !is[m][j] || !is[m][k] || !is[m][l]) continue; ok = false; // if(i==0 && j==2) printf("barvy %c %c %c %c\n",col[i],col[j],col[k],col[l]); // if(i==0 && j==2) printf("kostka %c-%c,%c-%c,%c-%c\n",dice[m][0],dice[m][3],dice[m][1],dice[m][2],dice[m][4],dice[m][5]); if((dice[m][0]==col[i] && dice[m][3]==col[k]) || (dice[m][3]==col[i] && dice[m][0]==col[k]) || (dice[m][1]==col[i] && dice[m][2]==col[k]) || (dice[m][2]==col[i] && dice[m][1]==col[k]) || (dice[m][4]==col[i] && dice[m][5]==col[k]) || (dice[m][5]==col[i] && dice[m][4]==col[k])) ok=true; // if(ok) printf("%c %c %c %c %d\n",col[i],col[j],col[k],col[l],m); if(ok && ((dice[m][0]==col[j] && dice[m][3]==col[l]) || (dice[m][3]==col[j] && dice[m][0]==col[l]) || (dice[m][1]==col[j] && dice[m][2]==col[l]) || (dice[m][2]==col[j] && dice[m][1]==col[l]) || (dice[m][4]==col[j] && dice[m][5]==col[l]) || (dice[m][5]==col[j] && dice[m][4]==col[l]))) num++; // if(i==0 && j==2) printf("%d\n",num); } if(num>maxnum) maxnum=num; } } } } printf("%d\n",maxnum); // while(getchar()!='a'); return 0; }

Cetovatel

Úkolem je zjistit na mapě světa, jaký je největší kontinent, na kterém se nenachází cestovatel:

Příklad zdrojového kódu:

#include<stdio.h> #include<string.h> #include<math.h> /*#include<stdbool.h>*/ char mapa[20][20]; int m,n; #define ISLAND 1 #define ISLAND_VIS 2 void help() { while(getchar()!='\n'); } int shall_con() { int i,j; for(i=0;i<m;i++) { for(j=0;j<n;j++) { if(mapa[i][j] == ISLAND) return 1; } } return 0; } int size(int x, int y) { int ret = 0,i,j; if(mapa[x][y]==ISLAND) { ret=1; mapa[x][y]=ISLAND_VIS; for(i=-1;i<=1;i++) { if(x+i>=0||x+i<m) {ret += size(x+i,y);} ret += size(x,(y+i+n)%n); } } return ret; } int main(int argc, char** argv) { int x,y; int i,j; int chr; int res,tmp; while(1) { scanf("%d %d",&m,&n); for(i=0;i<m;i++) { help(); for(j=0;j<n;j++) { mapa[i][j]= getchar()=='1'; } } scanf("%d %d",&x,&y); size(x,y); res = 0; while(shall_con()) { for(i=0;i<m;i++) { for(j=0;j<n;j++) { if(mapa[i][j] == ISLAND) { tmp=size(i,j); if(tmp>res) res = tmp; break; } } } } printf("%d\n",res); help();help(); if((chr=getchar())=='\n'||chr==EOF) break; else ungetc(chr,stdin); } return 0; }

Týmy

Máme určit uspořádání studentů do dvojic (týmů) tak, aby součet vzájemných vzdáleností studentů v týmech byl co nejnižší:

Příklad zdrojového kódu:

#include<cstdio> #include<cmath> int n; int X[30],Y[30]; double dist[30][30]; bool done[30]; int minx,miny; char name[10001]; int x,y; double sum; int edges[12][2]; bool ok; double one,two; int main(){ scanf("%d",&n); int i,j,k,l; for(i=0;i<2*n;i++){ scanf("%s%d%d",name,&x,&y); X[i]=x; Y[i]=y; } for(i=0;i<2*n;i++){ for(j=0;j<2*n;j++){ if(i==j) continue; dist[i][j]=sqrt((double)((double)X[i]-X[j])*((double)X[i]-X[j])+((double)Y[i]-Y[j])*((double)Y[i]-Y[j])); } } sum=0.0; for(k=0;k<n;k++){ for(i=0;i<2*n;i++){ if(done[i]) continue; for(j=0;j<2*n;j++){ if(done[j] || i==j) continue; minx = i; miny = j; } } for(i=0;i<2*n;i++){ if(done[i]) continue; for(j=0;j<2*n;j++){ if(done[j] || i==j) continue; if(dist[i][j]<dist[minx][miny]){ minx=i; miny=j; } } } done[minx]=true; done[miny]=true; sum+=dist[minx][miny]; edges[k][0]=minx; edges[k][1]=miny; } // printf("%.2lf\n",sum); ok = false; while(!ok){ ok = true; for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(i==j) continue; one=dist[edges[i][0]][edges[i][1]]+dist[edges[j][0]][edges[j][1]]; two=dist[edges[i][0]][edges[j][0]]+dist[edges[i][1]][edges[j][1]]; if(one>two){ sum+=two-one; l = edges[i][1]; edges[i][1]=edges[j][0]; edges[j][0]=l; ok = false; } one=dist[edges[i][0]][edges[i][1]]+dist[edges[j][0]][edges[j][1]]; two = dist[edges[i][0]][edges[j][1]]+dist[edges[i][1]][edges[j][0]]; if(one>two){ sum+=two-one; l = edges[i][1]; edges[i][1]=edges[j][1]; edges[j][1]=l; ok = false; } } } } printf("%.2lf\n",sum); // while(getchar()!='a'); return 0; }