Soutěž dětí a mládeže v programování – 21. ročník
Krajské kolo 2006/2007
Napište program, který pro všechny roky 2001–2100 zobrazí přehledně do tabulky, kolik je v kterém roce pátků třináctého. Dále vypište kolik bylo v letech 2001-2100 pátků třináctého celkem.
Snažte se napsat co nejefektivnější program, přitom předpokládejte, že knihovní funkce Vašeho programovacího jazyka pro práci s datem nejsou příliš efektivní – lépe tedy bude hodnocen program, který datumové funkce nebude používat. Nezapomeňte do komentáře dopsat, jak program vlastně funguje.
Malá nápověda: 1.1.2001 bylo pondělí. Pro ty co nevědí, jak je to s přestupnými roky: Přestupný je každý rok, jehož letopočet je dělitelný čtyřmi, pokud zároveň není dělitelný stem (navíc jsou přestupné i roky dělitelné číslem 400, ale takový se v našem zadání nevyskytuje).
| funkčnost | 1 bod | přehledné zobrazení |
| 2 body | správné uvedení počtu pátků 13. u nepřestupných roků 2001 (2), 2059 (1) a 2099 (3) | |
| 1 bod | správné číslo pro přestupné roky 2004 (2), 2040 (3) a 2080 (2) | |
| 1 bod | správné číslo pro rok 2100 (1) | |
| 1 bod | správně vypsaný součet za roky 2001-2100 (172) | |
| efektivita | 2 body | nepoužívá datumové funkce |
| 1 bod | řešení, které neprochází všechny měsíce všech roků (např. vycházející z toho, že kolik pátků 13. je v roce, lze určit z toho, jakým dnem v týdnu rok začíná a zda je přestupný) | |
| dokumentace | 1 bod | komentáře, přehlednost, výstižné názvy proměnných, … |
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, … |
Napište program simulující život kolonie buněk. Kolonie má vždy tvar obdélníku, který je rozdělen na M × N polí. Pole obsahuje buď jednu živou, nebo jednu mrtvou buňku. Počáteční obsazení kolonie je dáno vstupním souborem, jehož formát je popsán dále.
Život kolonie probíhá po jednotlivých krocích. Během kroku se mění obsah každého pole v závislosti na tom, co obsahovala sousední pole na konci předchozího kroku. Každé pole (s výjimkou polí na okraji kolonie) má přitom osm sousedních polí. Přechod mezi jednotlivými stavy kolonie je přitom dán následujícími jednoduchými pravidly:
Živá buňka, která má méně jak dva živé sousedy, umírá, protože je osamocená.
Živá buňka, která má více jak tři živé sousedy, umírá, protože má malý prostor k životu.
Živá buňka, která má dva nebo tři živé sousedy, se nemění a zůstane živá i pro další generaci.
Mrtvá buňka, která má přesně tři živé sousedy, je nahrazena novou živou buňkou.
Mrtvá buňka, která nemá tři živé sousedy, zůstane i nadále mrtvá.
Program umožní načtení počátečního stavu kolonie ze souboru a poté provede simulaci zadaného počtu kroků života kolonie. Simulaci života půjde krokovat, nebo spustit jako animaci.
Program musí zvládat práci s koloniemi až do rozměrů 60 × 20.
Formát kolonie je textový soubor. Znak tečky
‚.‘ odpovídá mrtvé buňce, znak písmene
‚O‘ živé buňce. Na jedné řádce textového souboru je
zapsána vždy jedna řádka kolonie. Jako znak konce řádky může být
použita libovolná kombinace znaků CR, LF nebo CR+LF.
| funkčnost | 1 bod | program načte kolonii ze zadaného souboru a správně ji zobrazí |
| 1 bod | simulaci lze krokovat | |
| 1 bod | simulace se automaticky animuje a zastaví se po zadaném počtu kroků | |
| 1 bod | test1.txt – první dva obrazce se nemění
a druhé dva osiculují mezi dvěma stavy pro libovolný počet kroků | |
| 1 bod | test2.txt – po 30 krocích zbudou na
obrazovce dva malé ovály | |
| 1 bod | test3.txt – po 22 krocích zůstane zobrazen
jen čtverec 2×2 | |
| 1 bod | test4.txt – při delším běhu se
„loď“ pořád pohybuje tam a zpět | |
| 1 bod | test5.txt – po 45 krocích kolonie umírá | |
| efektivita | 1 bod | pole pro uchování kolonie má ze všech stran volný pruh, aby se nemusely speciálně ošetřovat krajní buňky |
| 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 si vyfotil ceduli s nápisy na několik fotografií. Jednotlivé fotografie převedl programem OCR na text. Z takto vzniklých textových souborů – fragmentů je třeba sestavit celý původní text.
Platí zde:
každý fragment je v samostatném souboru;
fragmenty nemusí být zadány ve správném pořadí;
každé dva navazující fragmenty se překrývají alespoň deseti znaky;
máme-li seřazené fragmenty A,B,C, překrývá se A s B, B s C, ale nepřekrývá se A s C;
předěl může být uprostřed věty i slova;
fragmenty i původní text nemusí dávat smysl.
Napište program, který seřadí a spojí fragmenty do výstupního textu. Vstupní i výstupní soubory lze zadat na příkazovém řádku. Vstupní i výstupní soubory lze zadat interaktivně. Program vyřadí případné nenavazující soubory fragmentů.
Prostudujte si ukázkový program a připojené ukázkové fragmenty.
| funkčnost | 1 bod | program zvládne malý několikafragmentový soubor (Test
01) - zadání z příkazového řádku |
| 1 bod | program zvládne malý několikafragmentový soubor (Test
01) - zadání interaktivní | |
| 2 body | program zvládne velký několikafragmentový
soubor (Test 04); 2 body do 1 minuty, 1 bod do 3 minut | |
| 3 body | program zvládně velký soubor (Test 05) s mnoha fragmenty v rozumném
čase (5min); 3 do 3 minut, 2 body do 5 minut, 1 bod do 10 minut
| |
| 1 bod | program zvládně velký soubor (Test 06) s mnoha fragmenty v rozumném
čase (30min) | |
| 1 bod | program pozná nejednoznačné fragmenty (lze je navázat různými
způsoby) – vyzkoušet na Test 03
| |
| dokumentace | 1 bod | komentáře, přehlednost, výstižné názvy proměnných, … |