Výsledky soutěže PilsProg 2010

Výsledky kvalifikace

Příjmení Jméno Splněných úloh Čas
 Juraszek Adam 6 250,522postupuje do finále
 Tesař Karel 6 328,404postupuje do finále
 Hlásek Filip 6 411,839postupuje do finále
 Kaleta Juda 6 467,666postupuje do finále
 Bílý Michael 6 705,773postupuje do finále
 Kovářík Karel 6 774,701postupuje do finále
 Ambrož Jan 6 881,718postupuje do finále
 Hübsch Ondřej 6 920,088postupuje do finále
 Zikmund Martin 6 936,228postupuje do finále
 Bilanský Michal 6 954,712postupuje do finále
 Jelen Jakub 6 955,492postupuje do finále
 Faltín Tomáš  6 1 958,118postupuje do finále
 Gazimagomedov Iljas 6 2 054,841postupuje do finále
 Hlom Ladislav 6 2 115,129postupuje do finále
 Chládek Tomáš 6 2 623,737postupuje do finále
 zetor pavol 4 352,502
 Kulhan Jakub 3 78,816
 Kodýdková Dana 3 443,481
 Thurnvald Matěj 3 1 102,856
 Vazač Tomáč 2 9,338
 Černáč Martin 2 30,737
 Smitka Jan 2 33,826
 Jirásek Petr 2 80,552
 Popule Lukáš 1 57,087
 Turčín Jiří 1 171,253
 Holeček Martin 1 451,714
 Kopeček Miroslav 1 482,716
 Nguyen Duc Anh 1 774,520

Výsledky finále

Příjmení Jméno Splněných úloh Čas
 Bilanský Michal 4 5,511
 Kaleta Juda 4 6,853
 Hlásek Filip 4 7,527
 Hübsch Ondřej 3 6,610
 Juraszek Adam 3 9,029
 Kovářík Karel 2 2,686
 Tesař Karel 2 3,016
 Zikmund Martin 2 3,982
 Jelen Jakub 2 4,719
 Faltín Tomáš  2 5,759
 Chládek Tomáš 2 6,033
 Ambrož Jan 2 6,185
 Gazimagomedov Iljas 1 3,312
 Bílý Michael 0 0,000
 Hlom Ladislav 0 0,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ázev Označení Zveřejněno Úspěšných řešitelů Zadání
AxB 0704 2009-01-15 09:54:19 39 Zadání
Pascalův trojúhelník 0703 2009-01-15 09:54:34 14 Zadání
AplusB 0805 2010-04-09 14:55:41 11 Zadání
Největší ze tří celých čísel 0806 2010-04-09 14:55:43 6 Zadání

Kvalifikační úlohy:

Název Označení Zveřejněno Úspěšných řešitelů Zadání
Osm královen 1015 2010-01-29 13:58:26 18 Zadání
Mravenec 1014 2010-01-29 13:58:33 27 Zadání
Letiště 1013 2010-01-29 13:58:34 19 Zadání
Jedlíci 1012 2010-01-29 13:58:35 20 Zadání
Jaký je to den? 1011 2010-01-29 13:58:36 17 Zadání
Antilopy a gepard 1010 2010-01-29 13:58:37 27 Zadání

Finálové úlohy:

Název Označení Zveřejněno Úspěšných řešitelů Zadání
Přepřahání vlaků 1020 2010-04-10 09:04:49 11 Zadání
Psaníčko 1021 2010-04-10 09:04:51 8 Zadání
Silueta 1022 2010-04-10 09:04:53 8 Zadání
Žebříček jazyků 1023 2010-04-10 09:04:55 6 Zadání

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

M E N U

Vytvořil PilsProgTým © 2007.