Hodnocení soutěžních úloh

Kategorie mládež

Soutěž dětí a mládeže v programování – 21. ročník

Krajské kolo 2006/2007

12.–14. dubna 2007

Binární hodiny

Koeficient 1

Napište program, který bude zobrazovat digitální hodiny (HH:MM:SS) v binárním tvaru a to tak, že každou číslici bude reprezentovat právě jedna čtveřice binárních symbolů, např. 0/1, svítí/nesvítí, atd.

Pro snadnější čitelnost hodin program doplňte o zobrazení času v klasickém digitálním tvaru HH:MM:SS

Program bude ukazovat tzv. systémový čas počítače v režimu 24 hodin.

Hodnocení

funkčnost2 bodyProgram ukazuje aktuální systémový čas
5 bodůProgram správně ukazuje jednotlivé číslice, tj. správně zobrazuje číslice 0 - 9 v binárním kódu
2 bodyProgram zvládá překreslovat čas po jedné sekundě
dokumentace1 bodkomentáře, přehlednost, výstižné názvy proměnných, …

Prvočísla

Koeficient 2

Prvočísla jsou všechna čísla větší než jedna, která jsou beze zbytku dělitelná pouze jedničkou a sama sebou. Mezi taková čísla patří například 2, 3, 5, 7, 11, …

Napište program, který do uživatelem zadaného souboru vypíše všechny dvojice prvočísel, které se mezi sebou liší o dvě (například 3—5, 5—7, 11—13, …) a na obrazovku zobrazí počet takovýchto dvojic. Horní mez prohledávání je zadána uživatelem. Každá dvojice prvočísel bude ve výstupním souboru uložena na samostatném řádku a čísla budou oddělena mezerou.

Hodnocení

funkčnost1 bodUživatel si bude moci vybrat výstupní soubor
1 bodUživatel bude moci zadat horní mez
1 bodProgram v rozumném čase (během několika sekund) a spravně najde 35 dvojic do intervalu 1 000
1 bodProgram v rozumném čase (do půl minuty) a spravně najde 1224 dvojic do intervalu 100 000
1 bodProgram v rozumném čase (do minuty) a spravně najde 58980 dvojic do intervalu 10 000 000
1 bodProgram v rozumném čase (do 10 minut) a spravně najde 3424506 dvojic do intervalu 1 000 000 000
efektivita2 bodyPro prohledávaní je použito Eratosthenovo síto
1 bodPři použítí síta se neberou v uváhu sudá čísla (ušetření paměti)
dokumentace1 bodkomentáře, přehlednost, výstižné názvy proměnných, …

Skládání panoramat

Koeficient 3

Pan Pompo je filuta. vždy nás ohromí něčím novým. Tentokrát se zabývá fotografií. Nafotil několik fotografií své zahrádky (to je ta s mrkví, vzpomínáte). Doma by si rád pověsil na zeď panorama složené z těchto fotografií.

Pro vstupní fotografie platí:

  • navazují na sebe pouze vodorovně;

  • všechny jsou stejně vysoké – maximálně 1000 pixelů;

  • všechny jsou vertikálně zarovnány – žádná není výš nebo níž než ostatní;

  • nemusí být ve správném pořadí a jsou různě široké – maximálně 1000 pixelů;

  • překrývají se o 5 až 15 pixelů, překrytí může být u různých dvojic fotografií různé;

  • máme-li seřazené fotografie označeny A, B, C, navazují na sebe dvojice obrázků A/B a B/C; obrázky A a C se nepřekrývají;

  • překrytí je u obrázků jednoznačné, obrázky je možné navázat jen jedním způsobem;

  • je použit formát BMP – truecolor, bez palety barev, nekomprimovaný (popis je dále).

Napište program, který seřadí a spojí fotografie do výsledného panoramatického obrázku a ten uloží. Vstupní i výstupní soubory obrázků lze zadat interaktivně, v jakémkoliv pořadí, soubory mohou být v různých adresářích. Program zobrazí všechny vstupní obrázky i výstupní panoramatický obrázek.

Pokud se v souboru vyskytují nenavazujícící fotografie, upozorněte na tento stav uživatele. Panorama v takovém případě nesestavujte.

Prostudujte si ukázkový program a připojené ukázkové fotografie.

Zjednodušený popis formátu BMP

Soubor se skládá ze dvou částí – z hlavičky a oblasti dat.

Popis hlavičky

Hlavička má velikost 54 bajtů a obsahuje údaje o obrázku.

Číslování bajtů začíná od nuly a hodnoty jsou v hexadecimálním (decimálním) tvaru.

AdresaPříklad datPopis
00000000(00): 42 4D identifikace souboru obsahuje vždy znaky "BM" (66) (77)
00000002(02): E2 04 00 00 00 00 00 00 pro nás nevýznamné
0000000A(10): 36 00 00 00 posun oblasti dat od začátku souboru (většinou (54) bytů)
0000000E(14): 28 00 00 00 pro nás nevýznamné
00000012(18): 11 00 00 00 šířka obrázku v pixelech (zde (17) pixelů)
00000016(22): 17 00 00 00 výška obrázku v pixelech (zde (23) pixelů)
0000001A(26): 01 00 18 00 00 00 pro nás nevýznamné
00000020(32): 00 00 AC 04 00 00 00 00 pro nás nevýznamné
00000028(40): 00 00 00 00 00 00 00 00 pro nás nevýznamné
00000030(48): 00 00 00 00 00 00 pro nás nevýznamné

Popis oblasti dat

Oblast dat určuje barvy jednotlivých pixelů. Velikost oblasti dat odpovídá počtu pixelů obrázku. Začíná se v levém dolním rohu obrázku po řádcích. Barva pixelu je určena hodnotami 3 bajtů. Každý bajt vyjadřuje jednu barvu v tomto pořadí: BGR (modrá, zelená, červená). Každý řádek v souboru musí mít velikost v bajtech dělitelnou čtyřmi beze zbytku, proto je na konec každého řádku přidána výplň 0-3 bajty s hodnotou nula.

AdresaPříklad datPopis
00000036(0054): FF FF FF barva pixelu (zde bílá) červená=zelená=modrá=FF(255)
00000039(0057): FF FF FF barva pixelu (zde bílá)
0000003C(0060): FF FF FF barva pixelu (zde bílá)
… vynecháno …
00000066(0102): AA FF 55 barva pixelu (zde modrozelená) červená=55(85),zelená=FF(255),modrá=AA(170)
00000069(0105): 00 výplň (zde jeden nulový byte, 17*3+1=52 => 52 je dělitelné 4mi)
0000006A(0106): 00 00 00 barva pixelu (zde černá) červená=zelená=modrá=00(00)
0000006D(0109): 00 00 00 barva pixelu (zde černá)
00000070(0112): 00 00 00 barva pixelu (zde černá)
… vynecháno …
0000009A(0154): AA FF 55 barva pixelu (zde modrozelená) červená=55(85),zelená=FF(255),modrá=AA(170)
0000009D(0157): 00 výplň (zde jeden nulový byte, 17*3+1=52 => 52 je dělitelné 4mi)
… vynecháno …
000004DE(1246): AA FF 55 barva pixelu (zde modrozelená) červená=55(85),zelená=FF(255),modrá=AA(170)
000004E1(1249): 00 výplň (zde jeden nulový byte, 17*3+1=52 => 52 je dělitelné 4mi); poslední obrazový řádek je zarovnán také!

Hodnocení

funkčnost0.5 boduprogram lze ovládat interaktivně
0.5 boduprogram zvládne zobrazit vstupní fotografie (až do velikosti 1000×1000) – ukázkové fotografie v adresářích T01 a T06
1 bod program zvládne zobrazit a sestavit panorama z několika (3-5) malých (40×30) fotografií – T01
1 bodprogram zvládne zobrazit a sestavit panorama z několika (3-5) velkých (800×600) fotografií – T02
1 bodprogram zvládne zobrazit a sestavit panorama z mnoha (10-20) velkých fotografií v rozumném čase (do 5 minut) – T04
1 bodprogram pozná nejednoznačné fotografie (lze je navázat různými způsoby – například obrázek šachovnice) – T05
1 bodprogram vyřadí nepatřičné nebo nenavazující fotografie – programu se předají fotografie z adresářů T03 a T06 najednou
efektivita3 bodypoužití některého blokového porovnávání (tedy neporovnává se postupně pixel po pixelu)
dokumentace1 bodkomentáře, přehlednost, výstižné názvy proměnných, uživatelská dokumentace, …

Jabloňový sad strýčka Pompa

Koeficient 3

Protože jste loni pomohli strýčku Pompovi osázet jeho zahradu mrkví a petrželí, stal se z něj úspěšný zahradník. Proto se rozhodl, že letos rozšíří svojí zahradu – pořídí si jabloňový sad.

Už se dokonce rozhodl, kam vysadí jabloně. Od vás by potřeboval poradit, jak má svůj jabloňový sad oplotit.

Plot si strýček Pompo představuje jako uzavřenou posloupnost rovných úseků natažených vždy mezi dvěma jabloněmi. Plot sám sebe nesmí protínat, uvnitř (nebo na jeho hranici) musí být všechny jabloně a musí být nejkratší možný. Výsledný plot navíc musí oplocovat jediný pozemek, tj. není možné, aby se sad skládal z dvou nebo více nesouvislých kusů.

Vaším prvním úkolem je napsat program, který dostane na vstupu popis strýčkovy zahrady. Po jeho načtení musí váš program spočítat hledaný nejkratší plot. Pak graficky zobrazí polohu všech stromů v zahradě, nakreslí nalezený plot a vypíše jeho délku.

Druhou částí úlohy je, aby program fungoval i interaktivně. Po spuštění načte zahradu, spočte plot, zobrazí sad a čeká na vstupy uživatele. Uživatel může přidávat a odebírat jednotlivé jabloně ze sadu. Po každé takové operaci program přepočte nový nejkratší plot a ihned ho zobrazí.

Popis vstupu: strýček Pompo má připravený popis sadu v následujícím formátu. Na první řádce je jediné celé číslo 3 <= N <= 10000, počet jabloní. Na dalších N řádkách jsou vždy mezerou oddělené souřadnice X a Y jednotlivých jabloní. Každá souřadnice je celé číslo od 0 od 511. Bod [0,0] je vlevo nahoře.

Obrázek 1. Příklad vstupu a oplocení

Příklad vstupu a oplocení

Pozn.: K získání nějakých (více než poloviny) bodů stačí splnit první úkol, pro plný počet je ale potřeba splnit také druhou část úlohy.

Hodnocení

funkčnost0.5 boducircle.txt – délka plotu je 1634.40559056491[a]
0.5 boductyrlistek.txt – délka plotu je 1714.62542328197[a]
0.5 boduodznak.txt – délka plotu je 1495.15070332929[a]
0.5 bodurandom.txt – délka plotu je 1466.20791542744[a]
1 bodcircle2.txt – délka plotu je 1635.05308430257[b]
1 bodctyrlistek2.txt – délka plotu je 1716.68566619288[b]
1 bododznak2.txt – délka plotu je 1502.03071973784[b]
1 bodrandom2.txt – délka plotu je 1561.97712479836[b]
1 bodProgram umožňuje za běhu aplikace přidávat a odebírat stromy. Po každé takové operaci musí program korektně přepočítat plot. Otestujte ručně několika přidáními a odebráními. Pokud to nejde, nedostane soutěžící nic.
2 bodyErgonomie ovládání přidávání/odebírání stromů. (Klikací myšoidní aplikace může dostat plný počet, zadávání souřadnic stromů číslem z klávesnice nedostane nic. Ostatní podle citu někde mezi 0–2 body.)
dokumentace1 boddokumentace, komentáře, přehlednost, výstižné názvy proměnných, …

[a] Plot vypadá jako ve vzorové aplikaci sad a jeho délka se může lišit maximálně o 1 od uvedené hodnoty.

[b] Plot vypadá jako ve vzorové aplikaci sad a jeho délka se může lišit maximálně o 1 od uvedené hodnoty. Výpočet musí trvat nejdéle 3–5 vteřin, jinak se body neudělí. Jedná se především o test efektivity.