Soutěž dětí a mládeže v programování – 21. ročník
Krajské kolo 2006/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.
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 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.
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.
Soubor se skládá ze dvou částí – z hlavičky a oblasti dat.
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.
Adresa | Příklad dat | Popis |
---|---|---|
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é |
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.
Adresa | Příklad dat | Popis |
---|---|---|
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é! |
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.
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.