Soutěž dětí a mládeže v programování – 17. ročník krajské kolo 2002/2003
Ú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ž 6 bodů je 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í úloh 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.
Číselné permutace jsou vzájemně odlišná rozmístění čísel 1 až n do n-prvkových množin tak, aby se žádné číslo neopakovalo. Například pro n=3 je výsledek 123, 132, 213, 231, 312, 321. Napište program generující (a vypisující) permutace pro n od jedné do devíti. Číslo n bude voleno uživatelem. Po vypsání všech permutací program oznámí jejich celkový počet.
Máte textový soubor. Nalezněte v něm nejdelší řetězec znaků, který se alespoň jednou opakuje. Tento řetězec znaků v sobě může obsahovat znak mezery, ale nesmí obsahovat znak konce řádku. Dále není dovoleno, aby koncová část prvního řetězce patřila do počáteční části druhého řetězce. (Např. pro soubor obsahující 123412341234 není správné řešení řetězec 12341234, protože se prostřední část překrývá.) Délka textu je maximálně 3000 řádků, délka řádku může být maximálně 2400 znaků. Při porovnávání řetězců rozlišujte velká a malá písmena (tj. například řetězce Text a text nejsou shodné).
Dále zjistěte počet a místa všech výskytu nalezeného řetězce znaků. Místo výskytu určete číslem řádku a pozicí prvního znaku řetězce v řádku.
Zajistěte uživatelsky pohodlný výběr souboru.
Příklad 1.
Soubor: test1.txt
<BOF> xaaabaaacaa ac <EOF>
Ukázka správného řešení:
Program zpracoval soubor: test1.txt Nalezený řetězec: "aaa" délka 3 1.výskyt: řádek 1 pozice 2 2.výskyt: řádek 1 pozice 6
Chybné řešení:
Program zpracoval soubor: test1.txt Nalezený řetězec: "aaac" délka 4 1.výskyt: řádek 1 pozice 6 2.výskyt: řádek 1 pozice 10
Vysvětlení: druhý výskyt řetězce je rozdělen mezi řádky č. 1 a č. 2, tudíž obsahuje znak konce řádku.
Příklad 2.
Soubor: test2.txt
<BOF> Tento text v sobě obsahuje text pro ukázku správného vyhledávání části textu v souboru. Text, který má sice stejná písmena, ale některá jsou velká a některá jsou malá, není správné řešení problému našeho vyhledávání největšího textového řetězce. <EOF>
Ukázka správného řešení:
Program zpracoval soubor: test2.txt Nalezený řetězec: "ho vyhledávání" délka 14 1.výskyt: řádek 2 pozice 8 2.výskyt: řádek 5 pozice 34
Napište program, který na obrazovce vykreslí uživatelem zadaný obrázek a poté jej ze zvoleného bodu vyplní. Obrázky budou dvoubarevné a uložené ve formátu BMP. Můžete předpokládat, že obrázek nebude větší než 600×400 pixelů. Pro samotné vyplnění obrázku nesmíte používat existující funkce, jako Fill, FloodFill, ale musíte navrhnout a implementovat vlastní algoritmus. Naopak pro načtení obrázku ve formátu BMP můžete použít funkce dostupné ve standardních knihovnách vámi použitého jazyka.
Program musí umět zpracovávat obrázky v níže popsaném formátu. Jedná se o podmnožinu formátu BMP verze 3.
Soubor s obrázkem se skládá z hlavičky, za kterou následují data obrázku. Struktura hlavičky je popsána v tabulce 1. Údaje v hlavičce jsou ukládány jako 16bitová (WORD) a 32bitová (DWORD) slova. Jednotlivé bajty ve slovech jsou zapsány od toho nejméně významného.
Tabulka 1. Struktura hlavičky formátu BMP
| Velikost | Popis |
|---|---|
| WORD | Identifikace formátu, obsahuje řetězec "BM" |
| DWORD | Velikost souboru v bajtech |
| DWORD | Nepoužito |
| DWORD | Offset začátku rastrových dat, obsahuje hodnotu 62 |
| DWORD | Velikost informační hlavičky, obsahuje hodnotu 40 |
| DWORD | Šířka obrázku v pixelech |
| DWORD | Výška obrázku v pixelech |
| WORD | Počet rovin obrázku, obsahuje hodnotu 1 |
| WORD | Barevná hloubka obrázku, obsahuje hodnotu 1 |
| DWORD | Způsob komprimace, obsahuje hodnotu 0 (= žádná komprimace) |
| DWORD | Velikost obrázku v bajtech, hodnota se používá, pokud je použita komprimace |
| DWORD | Horizontální rozlišení v pixelech na metr |
| DWORD | Vertikální rozlišení v pixelech na metr |
| DWORD | Počet barev použitých v obrázku, obsahuje hodnotu 2 |
| DWORD | Počet důležitých barev, obsahuje hodnotu 2 nebo 0 |
| BYTE | Modrá složka barvy popředí |
| BYTE | Zelená složka barvy popředí |
| BYTE | Červená složka barvy popředí |
| BYTE | Nepoužito, obsahuje hodnotu 0 |
| BYTE | Modrá složka barvy pozadí |
| BYTE | Zelená složka barvy pozadí |
| BYTE | Červená složka barvy pozadí |
| BYTE | Nepoužito, obsahuje hodnotu 0 |
Data obrázku jsou ukládána po jednotlivých řádcích zleva doprava, řádky pak odshora dolů. Jednomu bodu obrázku odpovídá jeden bit. Pokud bit obsahuje hodnotu 0, zobrazuje se barvou popředí. Pokud bit obsahuje hodnotu 1, zobrazuje se barvou pozadí.
Osm bitů je vždy uloženo v jednom bajtu. Jednotlivé bity se mapují na body obrázku zleva doprava od nejvýznamnějšího bitu. Není-li šířka obrázku násobkem čísla 32, jsou data každého řádku obrázku zarovnána na nejbližší vyšší násobek 32 bitů. Přebytečné výplňové bity se ignorují.