Soutěž dětí a mládeže v programování – 19. ročník
Krajské kolo 2004/2005
Ú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 6 bodů vyhrazeno na ohodnocení funkčnosti programu a jeho shody se zadáním, 3 body na efektivitu 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í pro některé z úloh.
Vytvořte program, který vygeneruje statické HTML stránky s malou a velkou násobilkou.
Úkolem je sestavit program, který vygeneruje následujících 41 stránek HTML:
stránku index.htm, která bude sloužit jako úvodní stránka;
pro každé číslo NN = 01, …, 20
stránky malaNN.htm s malou násobilkou (násobky od jedné do deseti) a
velkaNN.htm s velkou
násobilkou (násobky od jedenácti do dvaceti) – celkem 40
statických stránek (stránky mohou mít případně příponu .html); stránka
velka07.htm tak například bude obsahovat následující tabulku:
7 × 11 = 77
7 × 12 = 84
7 × 13 = 91
7 × 14 = 98
7 × 15 = 105
7 × 16 = 112
7 × 17 = 119
7 × 18 = 126
7 × 19 = 133
7 × 20 = 140
Stránky by měly obsahovat pouze validní HTML nebo XHTML kód dle standardů W3C. Platné standardy HTML 4.01 a XHTML 1.0 najdete mezi soubory se zadáním.
Postupně v programu implementujte následující funkce:
vygenerování 41 stránek s násobilkou;
přidání hypertextových odkazů mezi stránkami;
uživatel si může zvolit číslo (1–20), pro které se má stránka s násobilkou generovat;
uživatel si může zvolit, zda se mají generovat obě násobilky, nebo jen malá, nebo jen velká;
uživatel si může zvolit adresář, kam se mají soubory vygenerovat;
uživatel si může zvolit barvu pozadí, textu a odkazů;
uživatel si může uložit nastavení předchozích voleb do zvoleného souboru a později je zase využít.
Vytvořte program, který bude analyzovat volitelný vstupní soubor a výsledek analýzy uloží do zvoleného souboru v předepsaném formátu.
Každý řádek vstupního souboru obsahuje jednu položku v následujícím formátu:
datum_a_čas URL návratový_kód přenesená_data
Řádky jsou uloženy v chronologickém pořadí. URL je textový řetězec neobsahující mezery. Návratový kód je celočíselná hodnota z intervalu 100–599. Velikost přenesených dat je udávána v bajtech a jedná se o celé číslo.
Cílem analýzy vstupních dat je pro volitelné časové rozlišení (minuta, hodina nebo den) spočítat kolikrát se jednotlivý návratový kód vyskytl a kolik dat se pro něj přeneslo.
Výsledky analýzy program uloží do uživatelem zvoleného souboru v následujícím formátu:
datum_a_čas_začátku_intervalu návratový_kód počet_výskytů přenesená_data
Výstup analýzy pak může vypadat následovně:
2005-02-15 00:00:00 200 543 534240 2005-02-15 00:00:00 404 24 2343 2005-02-16 00:00:00 200 2345 9544320
Vaším úkolem je napsat program, který bude zobrazovat data z CSV souboru jako graf. Vstupní soubor bude mít formát:
"popisek1","hodnota1" "popisek2","hodnota2" ...
Uvozovky jsou nepovinné, pokud se čárka nevyskytuje uvnitř popisku či hodnoty. Popiskem může být libovolný text neobsahující uvozovky. Hodnota bude vždy nezáporné číslo, případná desetinná část se odděluje tečkou. Soubor může obsahovat maximálně 100 položek.
Hodnoty se zobrazují na svislé ose (Y), popisky na vodorovné (X). U obou os zvolte vhodně měřítko, v případě nedostatku místa pro popisky na ose X můžete některé vynechat. Rozsah osy s hodnotami (Y) volte vždy od 0, maximální hodnotu zaokrouhlete směrem nahoru tak, aby zobrazená čísla obsahovala nejvýše dvě nenulové číslice (například je-li maximální hodnota v souboru 12345, bude mít osa Y rozsah od 0 do 13000).
Pro splnění úkolu je třeba správně zobrazit spojnicový graf a obě osy včetně popisů, navíc bude bodována schopnost programu zobrazit stejná data jako sloupcový graf.
Vaším úkolem je napsat program, který najde nejkratší cestu koněm na šachovnici, kde jsou některá pole ohrožována nepřátelskými střelci, a interaktivně ji zobrazí.
Program dostane na vstup šachovnici o rozměrech N řádků a M sloupců. Na této šachovnici je označeno startovní pole, cílové pole a na některých polích jsou nepřátelští střelci. Každý z těchto střelců ohrožuje pole, na kterém stojí, a obě diagonály (klasický šachový střelec). Navíc startovní ani cílové pole ohroženo není.
Program najde nejkratší cestu koněm (klasický šachový kůň) ze startovního políčka do cílového tak, aby kůň ani jednou nevkročil na pole, které by bylo ohrožené kterýmkoliv střelcem. Nalezenou cestu poté program interaktivně zobrazí, tj. vykreslí danou šachovnici se střelci a umožní odkrokování nalezené nejkratší cesty. Navíc program vypíše délku (počet tahů) nalezené cesty. V případě, že cesta ze startovního do cílového pole neexistuje, program to ohlásí.
Vstupem je soubor, který si uživatel vybere při spuštění programu. Tento soubor bude obsahovat na prvním řádku dvě čísla oddělená mezerou, a to N a M. Dalších M řádek bude popisovat M řádek šachovnice, každá se bude skládat z N znaků, kde
S značí startovní pole;
K značí cílové pole;
* značí střelce;
. značí volné pole šachovnice.
Startovní i cílové pole je právě jedno.
Maximální velikost šachovnice je 26 × 26, takže políčka šachovnice můžete označovat běžným způsobem A1 až Z26, kde písmenko značí řádek (nejspodnější je A) a číslo sloupec (nejlevější je 1).
Následuje příklad souboru obsahujícího šachovnici s nejkratší cestou délky šest:
8 8 ........ .....*.. Z....... ........ ........ ........ ..*...K. ........