PilsProg 2008

Výsledky kvalifikace

Splněných úlohPočet soutěžících
53
41
33
24
12

Pozn.: Jména a příjmení soutěžících byla odstraněna, protože pominul účel zpracování osobních údajů.

Výsledky finále

Splněných úlohPočet finalistů
43
23
12
01

Pozn.: Jména a příjmení finalistů byla odstraněna, protože pominul účel zpracování osobních údajů.

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); } } }