Soutěž dětí a mládeže v programování – 21. ročník
Krajské kolo 2006/2007
Ú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 9 bodů vyhrazeno na ohodnocení funkčnosti programu, jeho shody se zadáním a efektivity 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í úloh.
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).
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.
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.
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.