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


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.

Hodnocení

funkčnost1 bodnačtení čísla n
1 bodkontrola, zda je n v rozsahu 1 až 9
0,5 boduvypíše správně permutace pro n=1 (permutace je 1)
0,5 boduvypíše správně permutace pro n=2 (permutace jsou 2)
0,5 boduvypíše správně permutace pro n=3 (permutací je 6)
0,5 boduvypíše správně permutace pro n=4 (permutací je 24)
0,5 boduvypíše správně permutace pro n=8 (permutací je 40320)
0,5 boduvypíše správně permutace pro n=9 (permutací je 362880)
1 bodvýpis počtu permutací
efektivita3 bodyefektivní použití rekurze
dokumentace0,5 bodukomentáře nebo popis činnosti
0,25 bodupřehledný zdrojový text
0,25 boduvýstižné názvy proměnných

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

Hodnocení

funkčnost1 bodfunkční uživatelský výběr textového souboru
1 bodSprávné nalezení nejdelšího řetězce v souboru test1.txt:
Nalezený řetězec : " kvalifikovanílektoři" , delka: 21
1.výskyt: řádek 8 pozice 156
2.výskyt: řádek 12 pozice 321
1 bodSprávné nalezení nejdelšího řetězce v souboru test2.txt:
Nalezený řetězec : "TotalTimeoutMultiplier := 0; // Specifies the
multiplier, in milliseconds, " , delka: 75
1.výskyt: řádek 4 pozice 37
2.výskyt: řádek 4 pozice 472
3.výskyt: řádek 4 pozice 494
4.výskyt: řádek 452 pozice 22
5.výskyt: řádek 478 pozice 21
6.výskyt: řádek 493 pozice 11
7.výskyt: řádek 499 pozice 12
1 bodSprávné nalezení nejdelšího řetězce v souboru test3.txt:
Nalezený řetězec : "{$IFDEF PICTURE}and((PtrPic=nil)or((PtrPic<>nil)and((PtrPic^.F and pfEdi) = 0))){$ENDIF PICTURE}" , delka: 97
1.výskyt: řádek 1664 pozice 1
2.výskyt: řádek 2581 pozice 1
1 bodSprávné nalezení nejdelšího řetězce v souboru test4.txt:
Nalezený řetězec : "Zkouska na znak konce" , delka: 21
1.výskyt: řádek 1 pozice 1
2.výskyt: řádek 2 pozice 1
1 bodSprávné nalezení nejdelšího řetězce v souboru test5.txt:
Nalezený řetězec : "0123456789ABCDEFGHIJKLMOPQRSTUVWXYZ" , delka: 36
Řetězec se vyskytuje na všech řádcích 1–1000
efektivita1 bodsoubor se celý načte do paměti, do nějaké dynamické struktury (StringList, seznam řetězců apod.)
1 bodpři hledání v rámci jednoho řádku se vyhonocování zkrátí na konci o délku aktuálně nalezeného nejdelšího řetězce
1 bodz hledání jsou vyřazeny řádky, které jsou kratší než aktuálně nalezený nejdelší řetězec
dokumentace0,5 bodukomentáře nebo popis činnosti
0,25 bodupřehledný zdrojový text
0,25 boduvýstižné názvy proměnných

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

VelikostPopis
WORDIdentifikace formátu, obsahuje řetězec "BM"
DWORDVelikost souboru v bajtech
DWORDNepoužito
DWORDOffset začátku rastrových dat, obsahuje hodnotu 62
DWORDVelikost informační hlavičky, obsahuje hodnotu 40
DWORDŠířka obrázku v pixelech
DWORDVýška obrázku v pixelech
WORDPočet rovin obrázku, obsahuje hodnotu 1
WORDBarevná hloubka obrázku, obsahuje hodnotu 1
DWORDZpůsob komprimace, obsahuje hodnotu 0 (= žádná komprimace)
DWORDVelikost obrázku v bajtech, hodnota se používá, pokud je použita komprimace
DWORDHorizontální rozlišení v pixelech na metr
DWORDVertikální rozlišení v pixelech na metr
DWORDPočet barev použitých v obrázku, obsahuje hodnotu 2
DWORDPočet důležitých barev, obsahuje hodnotu 2 nebo 0
BYTEModrá složka barvy popředí
BYTEZelená složka barvy popředí
BYTEČervená složka barvy popředí
BYTENepoužito, obsahuje hodnotu 0
BYTEModrá složka barvy pozadí
BYTEZelená složka barvy pozadí
BYTEČervená složka barvy pozadí
BYTENepouž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.

Hodnocení

funkčnost0,5 bodusoubor s obrázkem jde zadat pohodlně pomocí dialogu pro výběr souboru
0,5 bodujde zadat souřadnice bodu vybarvování
0,5 bodumísto vybarvení jde zadat pohodlně myší
0,5 bodusprávně se zobrazí všechny ukázkové obrázky
0,5 boduobrázek barvy.bmp se zobrazí jako žluté písmeno „B“ na modrém pozadí
0,5 boduprogram správně vybarví horní bříško písmene B; například z bodu (110, 56)
1 bodprogram správně vybarví obrázek spirala.bmp z bodu (150,200)
1 bodprogram správně vybarví obrázek slunicko.bmp z bodu (381,147)
1 bodprogram správně vybarví jen jeden z obdélníků na obrázku obdelniky.bmp (tj. barva neproteče po diagonále)
efektivita1 bodbody k vyplnění se ukládají do fronty/zásobníku, nepoužívá se rekurzivní volání
1 bodvybarvování neprobíhá po jednotlivých bodech, ale po úsečkách
1 bodinteligentnější algoritmus vybarvování – např. se u každého bodu ukládá informace o tom, jakým směrem se má pokračovat ve vyplňování
dokumentace0,5 bodukomentáře nebo popis činnosti
0,25 bodupřehledný zdrojový text
0,25 boduvýstižné názvy proměnných