Zadání soutěžních úloh

Kategorie starší žáci a mládež

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.

Permutace – koeficient 1

Čí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.

Nejdelší opakující se řetězec – koeficient 3

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

Vyplňování obrázku – koeficient 2

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.

Popis grafického formátu

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í.

Určení plochy k vyplnění

Vybarvení ze zvoleného bodu se chápe jako vyplnění největší souvislé plochy, která má barvu pozadí. Tato souvislá plocha přitom musí obsahovat zvolený bod. Aby byl bod součástí plochy musí s jiným bodem této plochy sousedit nahoře, dole, nalevo nebo napravo.

Střední průmyslová škola strojní a elektrotechnická a Vyšší odborná škola, Liberec