PilsProg 2010

Výsledky kvalifikace

PříjmeníJménoSplněných úlohČasFinále
JuraszekAdam6250,522postupuje do finále
TesařKarel6328,404postupuje do finále
HlásekFilip6411,839postupuje do finále
KaletaJuda6467,666postupuje do finále
BílýMichael6705,773postupuje do finále
KováříkKarel6774,701postupuje do finále
AmbrožJan6881,718postupuje do finále
HübschOndřej6920,088postupuje do finále
ZikmundMartin6936,228postupuje do finále
BilanskýMichal6954,712postupuje do finále
JelenJakub6955,492postupuje do finále
FaltínTomáš61 958,118postupuje do finále
GazimagomedovIljas62 054,841postupuje do finále
HlomLadislav62 115,129postupuje do finále
ChládekTomáš62 623,737postupuje do finále
ZetorPavol4352,502
KulhanJakub378,816
KodýdkováDana3443,481
ThurnvaldMatěj31 102,856
VazačTomáč29,338
ČernáčMartin230,737
SmitkaJan233,826
JirásekPetr280,552
PopuleLukáš157,087
TurčínJiří1171,253
HolečekMartin1451,714
KopečekMiroslav1482,716
NguyenDuc Anh1774,520

Výsledky finále

PříjmeníJménoSplněných úlohČas
BilanskýMichal45,511
KaletaJuda46,853
HlásekFilip47,527
HübschOndřej36,610
JuraszekAdam39,029
KováříkKarel22,686
TesařKarel23,016
ZikmundMartin23,982
JelenJakub24,719
FaltínTomáš 25,759
ChládekTomáš26,033
AmbrožJan26,185
GazimagomedovIljas13,312
BílýMichael00,000
HlomLadislav00,000

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

Poznámka:
Finalista Michael Bílý se finálové soutěže nezúčastnil.

Ilustrační úlohy:

NázevOznačeníÚspěšných řešitelů
AxB070439
Pascalův trojúhelník070314
AplusB080511
Největší ze tří celých čísel08066

Kvalifikační úlohy:

NázevOznačeníÚspěšných řešitelů
Osm královen101518
Mravenec101427
Letiště101319
Jedlíci101220
Jaký je to den?101117
Antilopy a gepard101027

Finálové úlohy:

NázevOznačeníÚspěšných řešitelů
Přepřahání vlaků102011
Psaníčko10218
Silueta10228
Žebříček jazyků10236

A jaké bylo finále?

Finále začíná ...

Harmonogram PilsProg 2010

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.

Osm královen

Šachovnici vytvoříme jako pole logických hodnot (8x8). Po načtení pozice první dámy v poli (defaultně false) označíme jako true ohrožené čtverce podle pravidel šachu včetně pozice dámy samotné. Zapíšeme patřičný údaj o dámě do statického pole o délce osm, reprezentující osm sloupců a data v něm pak řádek dámy v příslušném sloupci. Tato dvě pole následně zleva po sloupcích procházíme a snažíme se v každém najít přípustné pole pro dámu. V kladném případě vytvoříme kopii šachovnice i zadání, do obou polí pak novou dámu a její vlastnosti zapíšeme. Pokud nastane situace, kdy ve sloupci nelze najít přípustnou pozici pro dámu, data jsou ztracena a vracíme se do předchozí fáze, která ji vyvolala a která má starší data. Tam se pokusíme najít jiné možné vhodné místo pro dámu a neuspějeme-li, opět se vracíme. Pokud se nám nepodaří nalézt volný sloupec, je šachovnice plná, je proveden výpis a opět se vracíme, abychom nalezli i zbylá řešení.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> short sachovnice[8]; // rozmisteni dle sloupcu, hodnota v poli oznacuje, na kterem RADKU je dama short jeDamaOhrozena(int sloupec) // radek si zjistime { int radek = sachovnice[sloupec]; // zjistime si radek int i; for(i = 1; i <= sloupec; i++) { int predchozi = sachovnice[sloupec-i]; // projdeme vsechny predchozi radky if(predchozi == radek // damy jsou na stejnem sloupci! || predchozi == (radek-i) // v predchozim radku je dama vlevo || predchozi == (radek+i) // v predchozim radku je dama "pod" ) return 1; // pak nastala kolize! } return 0; } int main() { // najdeme vsech 92 reseni, pak ale vypiseme jen ty, ktere obsahuji v souradnice[startX-1] hodnotu startY-1 // nakonec musime vysledky vypsat v obracenem poradi int startX, startY; scanf("%d %d", &startY, &startX); // Y=sloupec, X=sloupec int pocet = 0; sachovnice[0] = -1; // -1 protože se vždy provede do ... while, které ji vždy zvýší int sloupec = 0; while(sloupec >= 0) { do { sachovnice[sloupec]++; } while(sachovnice[sloupec] < 8 && jeDamaOhrozena(sloupec)); if(sachovnice[sloupec] < 8) // našli jsme další možnost pro sloupec { if(sloupec < 7) // ještě nemáme celou šachovnici { sachovnice[++sloupec] = -1; // připravíme si další řádek } else if(sachovnice[startX-1] == (startY-1)) // nalezeno řešení { pocet++; if(pocet < 10) printf(" "); printf("%d ", pocet); int r; for(r = 0; r < 8; r++) { printf("%d ", sachovnice[r]+1); } printf("\n"); } } else // dámy jsou ohroženy, musíme se vrátit { sloupec--; } } return 0; }

Mravenec

Mravencův pohyb se skládá z jednoduché posloupnosti kroků, kterou mravenec neustále opakuje. Mravenec učiní jeden krok vzhůru, i kroků vpravo, i kroků dolů, jeden krok vpravo, (i + 1) kroků vzhůru a (i + 1) kroků vlevo, kde i=2j, j je pořadové číslo právě prováděné posloupnosti kroků (na začátku j=0). Úkolem je pro daný čas zjistit, na jaké souřadnici (sloupec, řádka) se mravenec nachází.
Protože je vstupní čas shora ohraničen číslem 2.109, vyřešení úlohy hrubou silou nepřipadá v úvahu, neboť vytvoření matice o 2.109 prvcích nepovede k časově rozumnému řešení. Avšak vzhledem k pravidelnému pohybu mravence existuje vztah x=f(t) a z= f(t), kde (x, z) jsou souřadnice mravence v čase t. Při svém pohybu mravenec postupně opisuje čtverce a velikost čtverce, který mravenec během svého pohybu opisuje je vždy alespoň jednou jeho souřadnicí. Tuto velikost zjistíme tak, že nalezneme nejmenší možné celé číslo i takové, že jeho druhá mocnina je větší než čas t. Číslo i však obsahuje rozměr čtverce, který mravenec právě opisuje, ale pro výpočet počtu kroků, které mravenec učinil před vstupem do aktuálního čtverce, budeme potřebovat rozměr předchozího čtverce, tedy číslo (i – 1). Pokud odečteme od času t druhou mocninu čísla (i – 1), získáme počet kroků, které mravenec učinil od začátku opisování nového čtverce. Tento počet kroků označíme k. Pokud je počet kroků k roven číslu i, tak jsou výsledné mravencovy souřadnice (i, i), pokud je k menší než i, tak souřadnice jsou (k, i) a pokud je k větší než i, tak souřadnice jsou (i, i).

Příklad zdrojového kódu:
program mravenec_1014; var vstup,predchozictverec,zbytek,n:longint; odmocnina:real; vysledky:array[1..1000] of record x,y:longint; end; begin readln(vstup); n:=0; while vstup<>0 do begin inc(n); { citac } odmocnina:=sqrt(vstup-1); predchozictverec:=trunc(odmocnina); { nejmensi druha mocnina, had je nekde o jednu dal } zbytek:=vstup-(predchozictverec*predchozictverec); { kolik nam zbyva poli na mravence } if predchozictverec mod 2 = 1 then { ted sudy radek, x roste } if (zbytek-predchozictverec-1)>0 then { prejeli jsme radek a musime klesat } begin vysledky[n].x:=predchozictverec+1; zbytek:=zbytek-predchozictverec-1; vysledky[n].y:=predchozictverec+1-zbytek end else { neprejeli jsme } begin vysledky[n].y:=predchozictverec+1; vysledky[n].x:=zbytek end else { lichy radek, x klesa } if (zbytek-predchozictverec-1)>0 then { prejeli jsme radek a musime jet rovne od zadu } begin vysledky[n].y:=predchozictverec+1; zbytek:=zbytek-predchozictverec-1; vysledky[n].x:=predchozictverec+1-zbytek end else { neprejeli jsme } begin vysledky[n].x:=predchozictverec+1; vysledky[n].y:=zbytek end; readln(vstup) end; for zbytek:=1 to n-1 do writeln(vysledky[zbytek].x,' ',vysledky[zbytek].y); if n<>0 then write(vysledky[n].x,' ',vysledky[n].y) end.

Letiště

Nejprve spočteme vzájemné vzdálenosti letišť a označíme všechna letiště jako „nespojená“. Vybereme si jedno letiště, od kterého začneme, toto letiště označíme jako „spojené“.
Najdeme dvojice letišť (A, B) takové, že Letiště A je „spojené“, letiště B je „nespojené“ a nalezneme dvojici, jejíž vzdálenost je nejmenší ze všech nalezených, tuto vzdálenost přičteme k délce použité trasy a letiště B prohlásíme za „spojené“. Tento postup opakujme tak dlouho, dokud nebudou všechna letiště „spojena“.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> #include <math.h> #define FOR(i,n) for(i=0;i<n;i++) #define MAXN 101 #define L(a,b) sqrt((xs[a]-xs[b])*(xs[a]-xs[b])+(ys[a]-ys[b])*(ys[a]-ys[b])) double xs[MAXN],ys[MAXN],best[MAXN],sum=0; int used[MAXN]; int main(int argc, char *argv[]){ int N,i,j,b; scanf("%d",&N); FOR(i,N) scanf("%lf%lf",xs+i,ys+i); FOR(i,N) used[i]=0; used[0]=1; FOR(i,N) best[i]=L(0,i); FOR(j,N-1){ b=-1; FOR(i,N) if(!used[i]&&(b==-1||best[i]<best[b])) b=i; used[b]=1; sum+=best[b]; FOR(i,N) if(!used[i]&&L(b,i)<best[i]) best[i]=L(b,i); } printf("%.2f\n",sum); return 0; }

Jedlíci

1. Způsob:
Aplikujeme abstraktní datovou strukturu fronta. Vypíšeme nasycené jedlíky. Řazením do fronty (pouze hladové) a obsluhou fronty odebíráme a vypisujeme najezené, hladové je nutno seřadit podle zbylého hladu.

2. Způsob:
Sečteme velikosti hladu všech jedlíků a vypíšeme již nasycené jedlíky.
a) Pokud je počet chuťovek větší nebo roven součtu velikosti hladu jedlíků, nají se všichni v pořadí vzestupně podle jejich velikosti hladu, zbytek chuťovek určíme rozdílem mezi počátečním počtem chuťovek a součtem velikostí jejich hladu.
b) Pokud je počet chuťovek menší než součet velikostí jejich hladu, vydělíme počet chuťovek počtem jedlíků a výsledek porovnáme s velikostmi hladu jednotlivých jedlíků, ti s menší či rovnou velikostí hladu se nají v pořadí podle velikosti svého hladu. Ti, co mají větší hlad se nenajedli a zbylá velikost hladu je dána rozdílem s podílem. Seřadíme sestupně dle zbylé velikosti hladu.
c) Pokud je chuťovek méně než jedlíků, odečteme 1 z hladu počtu prvních jedlíků (počet jedlíků=počtu chuťovek) a všechny seřadíme sestupně dle velikosti hladu.
Pozn. Ve všech případech bylo nutno pro řazení použít stabilní metodu řazení.

Příklad zdrojového kódu:

import java.util.Scanner; public class Jedlici { static int j; static int ch; static String[] k; static int[] l; /** * @param args */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); j = sc.nextInt(); ch = sc.nextInt(); k = new String[j]; l = new int[j]; int n = 0; for (int i = 0; i < j; i++) { k[i] = sc.next(); l[i] = sc.nextInt(); n += checkSyty(i); } int x = 0; for (; ch > 0 && isHungry(); x++) { if (l[x % j] > 0) { l[x % j]--; ch--; } n += checkSyty(x); } if (j == n) { System.out.println("Vsichni nasyceni!"); if (ch > 0) { System.out.println("Zbyle chutovky: " + ch); } } else if (isHungry()) { System.out.println("Hlad ma:"); for (int i = 30; i > 0; i--) { for (int y = x; y < x + j; y++) { if (l[y % j] == i) { System.out.println(k[y % j] + " " + l[y % j]); } } } } } private static int checkSyty(int x) { if (l[x % j] == 0) { System.out.println(k[x % j]); l[x % j]--; return 1; } return 0; } static boolean isHungry() { for (int i = 0; i < j; i++) { if (l[i] > 0) { return true; } } return false; } }

Jaký je to den?

Řešení tkví v aplikaci daných omezení (posuny dat), pravidel (stanovení počtu dní v únoru a přestupnosti roků) a ve validaci zadaného data.
Určíme počet dní v únoru podle přestupnosti roku a provedeme validaci zadaného data.
Vytvoříme konstantu - jaký den byl v roce 1800
a) Před 1800 - spočteme první den v požadovaném roce i s přestupnými roky a případný posun dní v roce 1752
b) od 1800 se cyklus opakuje každých 400 let

  - spočteme první den v požadovaném roce i s přestupnými roky
  - přičteme dny v měsíci - v roce 1752 uplatníme posun dní
  - přičteme dnešní datum
  - mod 7
          

Příklad zdrojového kódu:

import java.util.Scanner; public class Den { /** * @param args */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (true) { int d = sc.nextInt(); if (d == 0) { break; } int m = sc.nextInt(); int y = sc.nextInt(); if (isValid(y, m, d)) { System.out.println(d + ". " + printMonth(m) + " " + y + ": " + printDay(dayofweek(y, m, d + normalize(y, m, d)))); } else { System.out.println(d+"/"+m+"/"+y+" Chyba!"); } } } private static boolean isValid(int y, int m, int d) { if (m > 12 || m <= 0) { return false; } //podle mesicu switch (m) { case 1: case 3: case 5: case 7: case 8: case 10: case 12: { if (d > 31 || d <= 0) { return false; } break; } case 4: case 6: case 9: case 11: { if (d > 30 || d <= 0) { return false; } break; } case 2: if (d > 29 || d <= 0) { return false; } if (d == 29) { if (y > 1752) { //gregoriansky prestupny if (!((y % 4 == 0) && (y % 100 != 0) || (y % 400 == 0))) { return false; } } else { // juliansky if (y % 4 != 0) { return false; } } } } // diskontinuita if (y == 1752 && m == 9 && d >= 3 && d<=13) { return false; } return true; } public static int normalize(int y, int m, int d) { if (y > 1752 || y == 1752 && m > 9 || y == 1752 && m == 9 && d >= 14) { return 0; } else if (y > 1700 || y == 1700 && m > 2) { return 11; } else if (y > 1500 || y == 1500 && m > 2) { return 10; } else if (y > 1400 || y == 1400 && m > 2) { return 9; } else if (y > 1300 || y == 1300 && m > 2) { return 8; } else if (y > 1100 || y == 1100 && m > 2) { return 7; }else if (y > 1000 || y == 1000 && m > 2) { return 6; }else if (y > 900 || y == 900 && m > 2) { return 5; }else if (y > 700 || y == 700 && m > 2) { return 4; }else if (y > 600 || y == 600 && m > 2) { return 3; }else if (y > 500 || y == 500 && m > 2) { return 2; }else if (y > 300 || y == 300 && m > 2) { return 1; } return 0; } public static String printDay(int d) { return new String[] { "nedele", "pondeli", "utery", "streda", "ctvrtek", "patek", "sobota" }[d]; } public static String printMonth(int m) { return new String[] { "leden", "unor", "brezen", "duben", "kveten", "cerven", "cervenec", "srpen", "zari", "rijen", "listopad", "prosinec" }[m-1]; } public static int dayofweek(int y, int m, int d) /* 0 = Sunday */ { int[] t = new int[] { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 }; y -= (14 - m) / 12; // y -= m < 3; return (y + y / 4 - y / 100 + y / 400 + t[m - 1] + d) % 7; } }

Antilopy a gepard

1. způsob:
Vytvoříme haldu (maximum) pro hmotnost, lovenou antilopu odebereme, další antilopy přidáme (jsou-li nějaké) v odpovídajících dnech a kontrolujeme počet odebrání = počet dní lovu

2. způsob:
Použijeme pole s označením již lovených antilop. Seřadíme podle hmotnosti a postupně v určených dnech přidáváme antilopy, znovu řadíme a kontrolujeme, zda je první z antilop rychlejší pro daný počet dnů.

Příklad zdrojového kódu:

program Gepard; var den:array[1..10] of string; antilopy:array[1..100,1..2] of integer; // 1=hmotnost antilopy, 2=rychlost nejvetsi_hmotnost:array[1..2] of integer; // 1=poradi antilopy, 2=hmotnost rychlost_geparda, pocet_dni, pocet_antilop, i, j, k, vstup, dalsi_antilopy_den:integer; begin den[1]:='prvni'; den[2]:='druhy'; den[3]:='treti'; den[4]:='ctvrty'; den[5]:='paty'; den[6]:='sesty'; den[7]:='sedmy'; den[8]:='osmy'; den[9]:='devaty'; den[10]:='desaty'; read(rychlost_geparda, pocet_dni, pocet_antilop); nejvetsi_hmotnost[1]:=0; nejvetsi_hmotnost[2]:=0; for i:=1 to pocet_antilop do begin read(antilopy[i,1],antilopy[i,2]); if i=pocet_antilop then begin read(dalsi_antilopy_den); if dalsi_antilopy_den>0 then read(vstup); end; if antilopy[i,1]>nejvetsi_hmotnost[2] then begin nejvetsi_hmotnost[1]:=i; nejvetsi_hmotnost[2]:=antilopy[i,1]; end; end; for j:=1 to pocet_dni do begin if j=dalsi_antilopy_den then begin for k:=1 to vstup do begin inc(i); read(antilopy[i,1],antilopy[i,2]); end; pocet_antilop:=pocet_antilop+vstup; for i:=1 to pocet_antilop do begin if antilopy[i,1]>nejvetsi_hmotnost[2] then begin nejvetsi_hmotnost[1]:=i; nejvetsi_hmotnost[2]:=antilopy[i,1]; end; end; read(dalsi_antilopy_den); if dalsi_antilopy_den>0 then read(vstup); end; if rychlost_geparda>=antilopy[nejvetsi_hmotnost[1],2] then begin writeln('Gepard ulovi antilopu ',den[j],' den.'); break; end; if rychlost_geparda<antilopy[nejvetsi_hmotnost[1],2] then begin if j=pocet_dni then begin writeln('Gepard odejde hladovy.'); break; end; antilopy[nejvetsi_hmotnost[1],1]:=0; antilopy[nejvetsi_hmotnost[1],2]:=0; nejvetsi_hmotnost[1]:=0; nejvetsi_hmotnost[2]:=0; for i:=1 to pocet_antilop do begin if antilopy[i,1]>nejvetsi_hmotnost[2] then begin nejvetsi_hmotnost[1]:=i; nejvetsi_hmotnost[2]:=antilopy[i,1]; end; end; end; end; 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ů.

Přepřahání vlaků

1. Řazením
Řadicí algoritmus, který řadí posloupnosti čísel porovnáváním a prohazováním dvou sousedních čísel posloupnosti, je bubble sort (řazení záměnou). Tuto úlohu lze tedy vyřešit tak, že posloupnost seřadíme tímto algoritmem a spočítáme, kolikrát došlo k prohození sousedů. Řazení zastavíme ve chvíli, kdy je posloupnost již seřazena.

2. Spočtením bez řazení
Protože však zadání nepožaduje řazení, ale pouze vypsat kolikrát dojde k prohození, není nutno provádět výměnu, ale pouze spočítat počet prohození.

Příklad zdrojového kódu:

#include <stdio.h> int main(){ int n,L,vlak[51],nn,i,res,zmena,tmp; scanf("%d",&n); for(nn=0;nn<n;nn++){ scanf("%d",&L); for(i=0;i<L;i++) scanf("%d",vlak+i); zmena=1; res=0; while(zmena){ zmena=0; for(i=0;i<L-1;i++){ if(vlak[i]>vlak[i+1]){ res++; tmp=vlak[i]; vlak[i]=vlak[i+1]; vlak[i+1]=tmp; zmena=1; } } } printf("Vlak#%d: Nejmensi pocet otoceni = %d\n",nn+1,res); } return 0; }

Psaníčko

Nakreslený obrázek lze chápat jako graf. Pro řešení úlohy použijeme prohledávání grafu do hloubky. Prohledávání začneme v zadaném počátečním vrcholu grafu. Při průchodu grafem postupně používáme všechny doposud nepoužité hrany. Pokud se dostaneme do vrcholu, ze kterého již nevede žádná hrana a zároveň jsme použili všechny hrany, je tato cesta řešením. Pokud jsou v grafu ještě nějaké nenavštívené hrany, není předchozí cesta řešením.

1. Datová struktura pro ukládání cest, které je potřeba navštívit, může být zásobník nebo fronta. Do této struktury je kromě aktuálního vrcholu potřeba ještě ukládat seznam již navštívených vrcholů. O tom, který další vrchol navštívíme, rozhodneme z dostupných doposud nepoužitých hran.

2. Vzhledem k malému množství hran a vrcholů je možné prohledávání implementovat bez datových struktur pomocí rekurze.

Všechna řešení je nutno seřadit podle jednotlivých vrcholů od nejnižších hodnot k nejvyšším hodnotám.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> typedef struct Hrana { int a; int b; int x; }HRANA; HRANA hrana[8]; int znac[8]; int reseni[9]; void rekurze(int v, int krok) { int i; reseni[krok] = v; if (krok==8) { for (i=0; i<9; i++) printf("%d", reseni[i]); printf("\n"); } else { krok++; for (i=0; i<8; i++) { if (znac[i]==0 && (hrana[i].a==v || hrana[i].b==v)) { znac[i] = 1; int d; if (hrana[i].a==v) d=hrana[i].b; else d=hrana[i].a; rekurze(d, krok); znac[i] = 0; } } } } int main() { int i, n; for (i=0; i<8; i++) znac[i] = 0; hrana[0].a = 1; hrana[0].b = 2; hrana[0].x = 0; hrana[1].a = 1; hrana[1].b = 3; hrana[1].x = 0; hrana[2].a = 1; hrana[2].b = 5; hrana[2].x = 0; hrana[3].a = 2; hrana[3].b = 3; hrana[3].x = 0; hrana[4].a = 2; hrana[4].b = 5; hrana[4].x = 0; hrana[5].a = 3; hrana[5].b = 4; hrana[5].x = 0; hrana[6].a = 3; hrana[6].b = 5; hrana[6].x = 0; hrana[7].a = 4; hrana[7].b = 5; hrana[7].x = 0; scanf("%d", &n); if (n==3 || n==4 || n==5) printf("Reseni neexistuje\n"); else rekurze(n, 0); return 0; }

Silueta

Pro řešení úlohy je potřeba mít k dispozici všechna vstupní data. Trojici celých čísel (Li, Hi, Ri) reprezentující budovu Bi budeme postupně ukládat do tří polí nebo jiné vhodné datové struktury. Počet trojic je shora omezen číslem 5000. Jednotlivé hodnoty jsou celá kladná čísla od 1 do 9999. Po načtení vstupu vytvoříme celočíselnou proměnnou Hmax. Tato proměnná bude sloužit k uložení výšky největší budovy v jednotlivých krocích.
Dále budeme postupně procházet hodnoty souřadnic y od 1 do ymax. Pro každou takto prošlou souřadnici vyhledáme všechny budovy Bi, pro které se tato souřadnice y nachází v intervalu mezi Li a Ri (mezi levou pravou souřadnicí budovy Bi). Ze všech těchto budov Bi vybereme tu s největší výškou Hi a uložíme ji do proměnné Hmax. Tuto výšku porovnáme s nejvyšší výškou z předchozího kroku. Pokud je různá, dochází v siluetě ke změně výšky a našli jsme souřadnice levého počátku vodorovné linky. Takto postupujeme pro všechny souřadnice y a vyhledáme všechny dvojice (y, Hmax), které tvoří řešení problému.

Příklad zdrojového kódu:

program silueta; type Tpole=array[1..10000] of integer; var M:Tpole; l,h,r,poc,i,akt,posl:integer; begin for i:=1 to 10000 do M[i]:=0; poc:=0; //napln pole while NOT EOF do begin readln(l,h,r); for i:=l to (r-1) do begin if(h>M[i]) then M[i]:=h; end; if (r>poc) then poc:=r; end; //for i:=1 to poc do begin // write(M[i],' '); //end; //vypis pri zmene akt:=M[1]; posl:=1; for i:=1 to (poc+1) do begin if(M[i]<>akt) then begin write(posl,' ',akt,' '); posl:=i; akt:=M[i]; end; end; writeln(poc,' 0'); //readln; end.

Žebříček jazyků

1) Dle načtené velikosti mapy vytvoříme dvě stejně velká 2D pole. První je pole znaků (char) a slouží k uložení vstupních dat z mapy. Druhé je pole logických hodnot (boolean) a slouží k zapamatování (označení) míst, které již algoritmus v prvním poli prošel.
2) Počet výskytů každého jazyka je uložen do jiného jednorozměrného pole, na index odpovídající ASCII hodnotě znaku, jímž je tento jazyk na mapě reprezentován (například jazyk „c“ se uloží na 99 index v poli). Tímto jsou z pole sice využity pouze indexy od 97 („a“) do 122 („z“), ale nedochází k přepočtům těchto indexů na indexy nižší.
3) Po načtení velikosti mapy jsou načtena vstupní data do výše zmíněného pole v bodě 1).
4) Algoritmus projde každý prvek ve 2D poli a pokud zjistí, že je v druhém 2D poli stejné místo nastaveno na false, je ono místo označeno na true a je inkrementován v 1D poli počet výskytů tohoto jazyka. Navíc jsou také označeny, pomocí rekurzivně pracující metody, všechna místa v okolí tohoto místa. Takto je rekurzivně označena maximální spojitá oblast s výskytem stejného jazyka.
5) Všechny nenulové výskyty jazyků uložené v 1D poli jsou postupně vkládány do prioritní fronty v sestupném pořadí podle počtu výskytů daného jazyka, popřípadě abecedně, pokud by měly stejný počet výskytů.
6) Prvky jsou z prioritní fronty vypsány na výstup.

Příklad zdrojového kódu:

import java.util.Scanner; public class Jazyky { // radek, sloupec static char[][] mapa; static int[] pocet; /** * @param args */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int pripadu = sc.nextInt(); for (int i = 1; i <= pripadu; i++) { int v = sc.nextInt(); int s = sc.nextInt(); pocet = new int[26]; mapa = new char[v][s]; for (int j = 0; j < v; j++) { mapa[j] = sc.next().toCharArray(); } // mapa hotova for (int j = 97; j <= 123; j++) { int[] pos; while((pos = findInMap((char) j))!= null) { removeComponent((char) j, pos[0], pos[1]); pocet[j-97]++; } } System.out.println("Mapa #"+i); for(int j = 100*100/2; j>0; j--) { for(int k = 0; k<pocet.length; k++) { if(pocet[k]==j) { System.out.println((char)(k+97)+": "+pocet[k]); } } } } } static void removeComponent(char c, int r, int s) { mapa[r][s] = '0'; if (r >= 1) { if (mapa[r - 1][s] == c) { removeComponent(c, r - 1, s); } } if (s >= 1) { if (mapa[r][s - 1] == c) { removeComponent(c, r, s - 1); } } if (r <= mapa.length - 2) { if (mapa[r + 1][s] == c) { removeComponent(c, r + 1, s); } } if (s <= mapa[0].length - 2) { if (mapa[r][s + 1] == c) { removeComponent(c, r, s + 1); } } } static int[] findInMap(char c) { for (int i = 0; i < mapa.length; i++) { for (int j = 0; j < mapa[i].length; j++) { if (mapa[i][j] == c) { return new int[] { i, j }; } } } return null; } }