Zadání 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

Úlohy můžete řešit v libovolném pořadí a samozřejmě je nemusíte vyřešit všechny. Za každou úlohu můžete dostat maximálně 10 bodů, z nichž je většinou 9 bodů vyhrazeno na ohodnocení funkčnosti programu, jeho shody se zadáním a efektivity a jeden bod na dokumentaci a přehlednost zdrojového kódu. Body získané za každou úlohu se ještě násobí koeficientem, který odráží složitost úlohy.

Na řešení úlohy máte 4 hodiny čistého času.

Před zahájením soutěže vám pořadatel oznámí, kde najdete testovací soubory a vzorová řešení úloh.

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.

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.

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é!

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.