Soutěž dětí a mládeže v programování – 21. ročník
Krajské kolo 2006/2007
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.
funkčnost | 1 bod | Uživatel si bude moci vybrat výstupní soubor |
1 bod | Uživatel bude moci zadat horní mez | |
1 bod | Program v rozumném čase (během několika sekund) a spravně najde 35 dvojic do intervalu 1 000 | |
1 bod | Program v rozumném čase (do půl minuty) a spravně najde 1224 dvojic do intervalu 100 000 | |
1 bod | Program v rozumném čase (do minuty) a spravně najde 58980 dvojic do intervalu 10 000 000 | |
1 bod | Program v rozumném čase (do 10 minut) a spravně najde 3424506 dvojic do intervalu 1 000 000 000 | |
efektivita | 2 body | Pro prohledávaní je použito Eratosthenovo síto |
1 bod | Při použítí síta se neberou v uváhu sudá čísla (ušetření paměti) | |
dokumentace | 1 bod | komentáře, přehlednost, výstižné názvy proměnných, … |
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é! |
funkčnost | 0.5 bodu | program lze ovládat interaktivně |
0.5 bodu | program 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 bod | program zvládne zobrazit a sestavit panorama z několika (3-5)
velkých (800×600) fotografií – T02
| |
1 bod | program zvládne zobrazit a sestavit panorama z mnoha (10-20)
velkých fotografií v rozumném čase (do 5 minut) –
T04
| |
1 bod | program pozná nejednoznačné fotografie (lze je navázat různými
způsoby – například obrázek šachovnice) – T05 | |
1 bod | program vyřadí nepatřičné nebo nenavazující fotografie
– programu se předají fotografie z adresářů T03
a T06 najednou | |
efektivita | 3 body | použití některého blokového porovnávání (tedy neporovnává se postupně pixel po pixelu) |
dokumentace | 1 bod | komentáře, přehlednost, výstižné názvy proměnných, uživatelská dokumentace, … |
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.
funkčnost | 0.5 bodu | circle.txt – délka plotu je 1634.40559056491[a]
|
0.5 bodu | ctyrlistek.txt – délka plotu je
1714.62542328197[a]
| |
0.5 bodu | odznak.txt – délka plotu je
1495.15070332929[a] | |
0.5 bodu | random.txt – délka plotu je
1466.20791542744[a] | |
1 bod | circle2.txt – délka plotu je 1635.05308430257[b]
| |
1 bod | ctyrlistek2.txt – délka plotu je
1716.68566619288[b]
| |
1 bod | odznak2.txt – délka plotu je
1502.03071973784[b] | |
1 bod | random2.txt – délka plotu je
1561.97712479836[b] | |
1 bod | Program 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 body | Ergonomie 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.) | |
dokumentace | 1 bod | dokumentace, 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. |