PilsProg 2008

Výsledky kvalifikace

PříjmeníJménoSplněných úlohČasFinále
SilhavyJan51212.3194postupuje do finále
KovaříkLuboš52364.7800postupuje do finále
VaníkJakub53076.6317postupuje do finále
SobotkaZdeněk42182.2206postupuje do finále
PiklJan378.8950
OsmíkŠtěpán31577.8022postupuje do finále
LánskýLukáš31619.0258postupuje do finále
PřecechtělMartin2117.5228postupuje do finále
ChýlekAdam2147.9450postupuje do finále
RůžičkaJan2805.3264
MaršíkJiří21888.3417postupuje do finále
ŠvábJan17.7436
KnytlTomáš19.0289

Výsledky finále

PříjmeníJménoSplněných úlohČas
MaršíkJiří43.6181
VaníkJakub45.9769
OsmíkŠtěpán48.9583
LánskýLukáš22.8144
SilhavyJan23.6342
SobotkaZdeněk24.4761
KovaříkLuboš10.7608
ChýlekAdam13.6653
PřecechtělMartin00

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 2008

Ilustrační úlohy:

NázevČísloÚspěšných řešitelů
AxB070416
Pascalův trojúhelník070316
Největší ze tří celých čísel08066
AplusB08056

Kvalifikační úlohy:

NázevČísloÚspěšných řešitelů
Tělocvikářův problém08256
Petr se stěhuje08246
Loďka08232
Koza082212
Kam vedou všechny cesty08215
Bakterie082012

Finálové úlohy:

NázevČísloÚspěšných řešitelů
Cizinec08503
Oblázky08515
Převozník08524
Sekvence čísel08538

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

Příklady zdrojových kódů jsou vybrány z odevzdaných soutěžních úloh.

Bakterie

Počet žijících bakterií je dán Fibonacciho posloupností rozepsanou po 1/2 hodinách (v našem případě započítáváme i umírající bakterii - viz ilustrační příklad), stačí realizovat pomocí dvou proměnných (pole) a spočíst pro příslušný počet hodin a výsledek násobit počtem bakterií na počátku.

 0     1
 1     2 =  3    po 1 hod
 3     5 =  8    po 2 hod
 8    13 = 21    po 3 hod
21    34 = 55    po 4 hod	násobeno počátečním počtem bakterií
...
          

Příklad zdrojového kódu:

#include <stdio.h> int Bakterie(int zije, int cas) { if(cas > 0) { if(zije) return (Bakterie(1, cas - 1) + Bakterie(0, cas - 1)); else return Bakterie(1, cas - 1); } else return 1; } int main(void){ int cas, pocet; scanf("%d %d", &pocet, &cas); printf("%d", pocet * Bakterie(1, cas * 2)); return 0; }

Kam vedou všechny cesty

Nejkratší cestu nalezneme tak, že zjistíme cestu z obou měst do Říma a najdeme společná města, kterými tyto cesty procházejí. Když potom máme jít z města A do města B, vydáme se z města A do Říma, ale v prvním městě, které má cesta z města A společné s cestou z města B do Říma, odbočíme a půjdeme do města B. Samozřejmě, nemají-li cesty z obou měst do Říma žádné společné město, pak nastane nejhorší možný případ a budeme muset projít Římem.

Příklad zdrojového kódu:

#include <stdio.h> #include <math.h> int main(void) { int z, h, r[26], i, j, log[26], li; const int R = 'R' - 65; scanf("%d %d\n", &z, &h); for (i = 0; i < z; i++) { int potomek, rodic; rodic = getchar() - 65; while (getchar()!=' '); potomek = getchar() - 65; while (getchar()!='\n'); r[potomek] = rodic; } for (i = 0; i < h; i++) { int odkud, kam, dOdkud, dKam; odkud = getchar() - 65; while (getchar()!=' '); kam = getchar() - 65; while (getchar()!='\n'); dOdkud = odkud; while (1) { putchar(dOdkud + 65); dKam = kam; li = 1; log[0] = kam; while (dKam != dOdkud && dKam != R) log[li++] = dKam = r[dKam]; if (dKam == dOdkud) { for (j = li-2; j >= 0; j--) putchar(log[j] + 65); break; } else { dOdkud = r[dOdkud]; } } putchar('\n'); } getchar(); return 0; }

Koza

Způsob řešení je patrný z následujícího obrázku:

Znázornění řešení - koza

Příklad zdrojového kódu:

import java.util.Scanner; public class Koza { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int r1 = sc.nextInt(); int r2 = sc.nextInt(); double pom = (double)r2/(2*(double)r1); double b = 2*Math.acos(pom); double a = 2*(Math.PI-b); double sOhrady = Math.PI*r1*r1; double sp1 = (((r1*r1)/2)*(a-Math.sin(a))); double sp2 = (((r2*r2)/2)*(b-Math.sin(b))); double sSpaseno = sp1+sp2; if(sOhrady/2<=sSpaseno){ System.out.println("Koza je napasena"); } else { System.out.println("Koza ma hlad"); } } }

Loďka

Pro skupinu do tří lidí (včetně) je strategie převezení jasná. Pro čtyřčlennou skupinu máme na výběr ze dvou možností. Lidi označíme a-d vzestupně podle časů a konečné časy označíme t1, respektive t2.
Strategie 1:

a d
a
a c
a
a b

t1 = 2a + b + c + d
          
Strategie 2:
a b
a
c d
b
a b

t2 = a + 3b + d
          
Kterou z těchto dvou strategií vybrat, rozhodneme podle konkrétních časů t.
t1 = t2
2a + b + c + d = a + 3b + d
a + c = 2b
c = 2b - a
          
Pokud tedy bude čas třetího člověka větší než rozdíl dvojnásobku času druhého a času prvního, je výhodnější použít strategii 2. V opačném případě je výhodnější první strategie.
Na začátku vložíme všechny časy do pole, které je nutné následně seřadit. Označíme-li jednotlivé časy podle jejich indexů v poli (0,1,2...n-1), pak budeme tvořit vždy tyto čtveřice: 0, 1, n-2, n-1. Zjistíme, která strategie je pro každou takovou skupinu výhodnější a tu použijeme (v obou strategiích ovšem vynecháváme poslední krok, takže první dva lidé s nejmenšími časy (tj. nejrychlejší) zůstanou na výchozí straně řeky). Po převezení dvou nejpomalejších lidí aplikujeme postup na další dva poslední v poli, dokud nám nezbudou 2 nebo 3 nejrychlejší na počáteční straně řeky. Ty už jednoduše převezeme.

Příklad zdrojového kódu:

program lodka; var a:array [1..100] of word; n,i,j,v,x:word; begin v:=0; readln(n); for i:=1 to n do readln(a[i]); for i:=1 to (n-1) do begin for j:=1 to (n-i) do if a[j]>a[j+1] then begin x:=a[j+1]; a[j+1]:=a[j]; a[j]:=x; end; end; while n>3 do begin if (a[2]<= (a[n-1]+a[1]) div 2) then v:=v+a[n]+2*a[2]+a[1] else v:=v+a[n]+a[n-1]+2*a[1]; n:=n-2; end; if odd(n)=true then v:=v+a[2]+a[1]+a[3] else v:=v+a[2]; writeln(v); readln; end.

Peter se stěhuje

Načteme počet domů, vytvoříme příslušně velké pole a uložíme do něj čísla domů, která následují na vstupu. Toto pole seřadíme a určíme z něho medián (tj. pocet_prvku_pole/2), u lichého čísla se zaokrouhlí nahoru a dostaneme medián, u sudého dostaneme „nižší medián“, ale v případě sudého počtu domů budou vzdálenosti obou „mediánů“ stejné). Následně jen spočítáme součet rozdílů prvků nalevo a napravo od mediánu a vypíšeme.

Příklad zdrojového kódu:

import java.util.*; public class Stehovani { public static void main(String [] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int [] p=new int [n]; for(int I=0;I<n;I++) p[I]=sc.nextInt(); int nejmensi=p[0]; int nejvetsi=p[0]; for(int I=1;I<n;I++) { if(p[I]<nejmensi) nejmensi=p[I]; if(p[I]>nejvetsi) nejvetsi=p[I]; } int nejkratsi=0; int soucet=0; int vzd=0; for(int I=0;I<n;I++) nejkratsi+=p[I]; for(int I=1;I<=nejvetsi;I++) { for(int i=0;i<n;i++) { vzd=I-p[i]; if(vzd<0) vzd=-vzd; soucet+=vzd; } if(soucet<nejkratsi) nejkratsi=soucet; soucet=0; } System.out.print(nejkratsi); } }

Tělocvikářův problém

Nejdříve najdeme žáka, který má být úplně na konci řady (nejmenší) a pak zjistíme jestli žák, který má být hned před ním, je před ním (klidně mezi nimi může být několik žáků), potom zjišťujeme jestli třetí žák od konce je před druhým a tak pořád, dokud nezjistíme že x-tý žák od konce (na pořadníku) není před (x-1)-tým žákem od konce (na pořadníku). Žáci, kteří jsou na pořadníku na x-tém a vyšším místě postupně vystoupí tak, že první vystoupí x-tý a poslední ten, co má být úplně první v řadě.
Například:

PŘED       PO               1.VÝSTUP        2. VÝSTUP
John       Paul             George          Paul
Paul       George           John            George
George     John             Paul            John
Ringo      Ringo            Ringo           Ringo
          

Příklad zdrojového kódu:

program Telocvikar; var a,b:array [1..200] of string; k,l,m,n,i:word; c,d,e:string; j:boolean; begin readln(n); m:=n; for i:=1 to n do readln(a[i]); for i:=1 to n do readln(b[i]); while m>1 do begin c:=b[m]; d:=b[m-1]; for i:=1 to n do begin if (a[i]=c) or (a[i]=d) then if a[i]=c then j:=true else j:=false; if (a[i]=c) or (a[i]=d) then break else continue; end; if j=true then begin for k:=i to n do begin if a[k]=d then begin e:=a[k]; writeln(e); for l:=k-1 downto 1 do a[l+1]:=a[l]; a[1]:=e; end; end; end; m:=m-1; end; readln; end.

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

Příklady zdrojových kódů jsou vybrány z odevzdaných soutěžních úloh či řešení testerů úloh.

Cizinec

Vytvoříme typické slovníkové uspořádání (dvojrozměrné pole pro n dvojjazyčných výrazů). provedeme řazení podle cizojazyčných výrazů (pro velký objem dat – Quick sort). Čtená cizojazyčná slova vyhledáváme ve slovníku sekvenčně (pro velký objem dat - binární vyhledávání). V případě, že slovo nalezneme, provedeme výpis jeho anglického ekvivalentu, tj. slova na stejném indexu v poli. v opačném případě vypíšeme řetězec „eh“.

Příklad zdrojového kódu:

import java.util.Scanner; public class Cizinec { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[] radka; String[][] slovnik = new String[5000][2]; int citac = 0; while (true) { radka = sc.nextLine().split(" "); if (radka.length == 1) { break; } slovnik[citac][0] = radka[0]; slovnik[citac][1] = radka[1]; citac++; } while (sc.hasNextLine()) { radka[0] = sc.nextLine(); if (radka[0].length() == 0) { break; } boolean nalezeno = false; for (int i = 0; i < citac; i++) { if (slovnik[i][1].equals(radka[0])) { System.out.println(slovnik[i][0]); nalezeno = true; break; } } if (!nalezeno) { System.out.println("eh"); } } } }

Oblázky

Pro strategii hry při variantě - "prohrává ten, na koho zbude poslední odebrání oblázku" - platí:

 x = (p - 1) mod (n +1)

 kde:
 p ... počet oblázků před příslušným tahem ve hře
 n ... největší počet oblázků, který je dovolen odebrat jedním tahem
 x ... počet odebraných oblázků v příslušném tahu, aby zůstala zachována možnost výhry
          
Pro první tah stačí otestovat, zda x = 0, neboť v tom případě je hra pro začínajícího prohraná (pokud protihráč už neudělá v další hře nějaký chybný tah) a tudíž necháme táhnout Lojzu, v opačném případě x udává počet oblázků, které je nutno odebrat.

Příklad zdrojového kódu:

import java.util.*; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int p = sc.nextInt(); int n = sc.nextInt(); int x = (p-1) % (n+1); if (x!=0) System.out.println (x); else System.out.println ("Lojza"); } }

Převozníkův úkol

Břehům přiřadíme logickou hodnotu. Všichni účastníci mají na začátku stejnou hodnotu břehu. Vstupní kombinaci (uloženou v řetězci) ověřujeme postupně tak, že při jednotlivých převozech (změna hodnoty) kontrolujeme stav na břehu (březích), kde není převozník (jen tam jsou totiž možné kolize, tj. sežrání).

Příklad zdrojového kódu:

import java.util.Scanner; public class Prevoznik { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String radek = sc.nextLine(); boolean p = true; boolean z = true; boolean k = true; boolean v = true; for (int i = 0; i < radek.length(); i++) { if (radek.charAt(i) == 'p') { p = !p; } if (radek.charAt(i) == 'p' && (i + 1 < radek.length()) && radek.charAt(i + 1) != 'p') { i++; if (radek.charAt(i) == 'z') { z = !z; } else if (radek.charAt(i) == 'k') { k = !k; } else if (radek.charAt(i) == 'v') { v = !v; } } if (p) { if ((!z && !k) || (!k && !v)) { System.out.println("dojde k sezrani"); return; } } else { if ((z && k) || (k && v)) { System.out.println("dojde k sezrani"); return; } } } System.out.println("spravny postup"); } }

Sekvence čísel

Výpočtem v zadání popsaným způsobem:

Délky cyklu všech čísel mezi - reprezentace dvěma cykly do sebe vnořenými s uchováním maxima.

Např.:
1 4
1 4 8

4 2 1 = 3
3 10 5 16 8 4 2 1 = 8 - tj. maximum!
2 1 = 2
          

Příklad zdrojového kódu:

import java.util.Scanner; public class SekvenceCisel { public static int delkaCyklu(int cislo) { int delka = 1; while (true) { if (cislo == 1) { return delka; } else { if (cislo % 2 == 0) { cislo /= 2; } else { cislo *= 3; cislo++; } delka++; } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int i = sc.nextInt(); int j = sc.nextInt(); boolean prohozeno = false; if (i > j) { int pomocna = i; i = j; j = pomocna; prohozeno = true; } int maxHodnota = delkaCyklu(i); int hodnota; for (int citac = i + 1; citac <= j; citac++) { hodnota = delkaCyklu(citac); if (hodnota > maxHodnota) { maxHodnota = hodnota; } } if (!prohozeno) { System.out.println("" + i + " " + j + " " + maxHodnota); } else { System.out.println("" + j + " " + i + " " + maxHodnota); } } }