| Datum cvičení | ID | Body | Popis |
|---|---|---|---|
| 4. října | Zac | Začátek cvičení. Úkoly začnou být vypisovány někdy na začátku listopadu. | |
| 1. listopadu | Prvc | 1 | Napište program, který rozloží zadané číslo na prvočinitele (pro 84 by měl vypsat "84=2^2*3*7"). |
| Fact | 1 | Napište program, který pro zadané N spočte, kolik nul je na konci čísla N!. Pozor na to, že N! může mít stovky cifer a nevejde se tedy do žádného celočíselného typu! Můžete předpokládat, že N se vejde do typu longint.
| |
| Fdig | 2 | Napište program, který pro zadané N zjistí, jaká je poslední nenulová cifra čísla N!. Pokud to nebude zřejmé, měli byste dokázat, že Váš program funguje správně. Pozor na to, že N! může mít stovky cifer a nevejde se tedy do žádného celočíselného typu! Můžete opět předpokládat, že N se vejde do longintu.
| |
| 3Mat | 1 | Na třech hromádkách se nachází (a,b,c) sirek. Hrají dva hráči, pravidelně se střídají. Hráč na tahu si vybere hromádku a odebere z ní libovolný nenulový počet sirek. Prohrává hráč, který už nemůže táhnout [(0,0,0) sirek]. Vymyslete strategii pro začínajícího hráče, aby vyhrál, kdykoliv je to možné, a dokažte to o ní. | |
| KMin | 1-4 | Napište program hledající v zadané posloupnosti N přirozených čísel K-té nejmenší číslo. Řešení v čase O(N*K): 1 bod. Řešení v čase O(N*log K): 2 body. Řešení v čase O(N): 4 body. | |
| 8. listopadu | SSum | 1-4 | Na vstupu dostanete posloupnost N čísel a ještě číslo K. Máte zjistit, zda se v zadané posloupnosti vyskytuje souvislá podposloupnost (interval), jejíž součet by byl roven zadanému číslu K. Kvadratické řešení: 1 bod. Řešení v čase O(N * log N): 2 body. Lineární řešení: 4 body. |
| Usek | 1-5 | Napište program, který dostane na vstupu posloupnost N čísel a vypíše délku nejdelší souvislé podposloupnosti, která má nezáporný součet svých členů. Kvadratické řešení: 1 bod. Řešení v čase O(N * log N): 3 body. Lineární řešení: 5 bodů. | |
| 15. listopadu | BVyh | 2 | První písemka, jejíž cílem byla implementace binárního vyhledávání v Pascalu. |
| Rost | 1-2 | Napište program, který dostane na vstupu posloupnost N čísel a vypíše nejdelší rostoucí podposloupnosti (nemusí být souvislá). Použijte k tomu jeden z algoritmů popsaných na cvičení. Za kvadratický dostanete jeden bod, za O(N log N) dostanete body dva. | |
| 23. listopadu | Petr | 1 | Na zahradě je N záhonů, na jeden celý záhon se dá vysadit buď mrkev, nebo petržel. Nicméně petržel se nesmí vyskytovat na dvou sousedních záhonech. Napište program, který pro zadané N vypíše všechna možná osázení N záhonů. |
| Zvse | 1 | Posloupnost, která se skládá ze znaků '(' a ')' nazveme dobře uzávorkovanou, pokud je
| |
| Zpoc | 1 | Posloupnost, která se skládá ze znaků '(' a ')' nazveme dobře uzávorkovanou, pokud je
| |
| Pods | 1 | Na vstupu dostanete N celých čísel s1,s2,...,sN a celé číslo K. Vaším úkolem je vypsat VŠECHNY podposloupnosti si1,si2,...,sik takové, že součet jejích prvků je právě K. | |
| Podp | 3 | Na vstupu dostanete N tentokrát nezáporných čísel s1,s2,...,sN a nezáporné číslo K. Vaším úkolem je v čase O(N*K) spočítat, KOLIK existuje podposloupností si1,si2,...,sik takových, že součet jejich prvků je právě K. Tyto podposloupnosti nevypisujte (to byste v čase O(N*K) nestihli), vypište jen jejich počet. Příklad: Pro N=3, posloupnost 1, 1, 1 a K=2 je správný výsledek 3 (jsou to podposloupnosti 11 12; 11 13; 12 13). | |
| 30. listopadu | Psmk | 2+2 | Hodinová písemka na vypsání všech permutací a všech posloupností, které v součtu dají dané číslo. |
| 13. prosince | Zbyt | 1-3 | Na vstupu dostanete k různých prvočísel p1,...,pk a dále čísla n1<p1,n2<p2,...,nk<pk. Máte vypočítat takové číslo N, že N je menší než součin všech zadaných prvočísel a zbytek po dělení čísla N prvočíslem pi je ni pro každé i. Jinak řešeno máte převést číslo zadané pomocí zbytkových tříd do desítkového zápisu. Body dostanete podle časové složitosti. |
| Blud | 2 | Na vstupu dostanete bludiště velikosti N x M. Každé políčko bludiště je buď volné, zeď, start, nebo cíl. Start a cíl je vždy právě jeden. Vaším úkolem je najít a vypsat nejkratší cestu ze startu do cíle. Hýbat se můžete v jednom kroku dolů, nahoru, doleva nebo doprava. Časová složitost celého algoritmu musí být O(N*M). | |
| 20. prosince | Následující úlohy jsou testové obtížnosti, zkuste si je alespoň rozmyslet. | ||
| TNas | 2 | V souboru je uloženo nespecifikované množství dlouhých čísel (max. 50 cifer na číslo). Každé je uloženo na jednom řádku. Úkolem je vynásobit je všechny. Je zaručeno, že výsledné číslo nebude mít více než 1000 cifer. | |
| TDes | 2 | Veškerá data se načítají ze souboru. Máme šachovnici MxN a figurku z kouzelného šachu. Ta figurka chodí v lichém tahu jako střelec a v sudém jako věž. Na šachovnici jsou nějaká zakázaná políčka, je udáno startovní a cílové políčko šachovnice a úkol je najít nejkratší cestu (pokud není, tak vypsat hlášku, že to nejde) a vypsat ji. | |
| TKal | 2 | Pracovní cyklus muže je 2x ranní, 2x odpolední, 2x noční, 2x volno. Pracovní cyklus ženy je 5x ranní, 2x volno. Udělejte kalendář pro zloděje, milence, milenku a přítele (obou). | |
| TMor | 2 | Napište program pro převod z a do morseovky (program musí umět oba převody). Z klávesnice načtěte, zda se bude převádět z nebo do morseovky, ale vlastní vstup čtěte ze souboru a výsledek vypisujte do jiného souboru. Pokud neznáte morseovku, můžete si vymyslet vlastní variantu. | |
| Tooo | 2 | Na vstupu je textový soubor z písmenek anglicke abecedy a n≤13. Máte tento soubor přepsat do jiného tak, že zachová úpravu (mezery, entery) a pokud nějaké slovo obsahuje sudý výskyt znaku 'o' (počítáno od začátku souboru) a některé z následujících n slov neobsahuje 'a', tak se jeho znaky mají nahradit hvezdickami '*'. | |
| TLat | 2 | Vypsat do souboru všechny možné latinské čtverce řádu N≤10. Latinský čtverec je matice typu N x N, v níž v každém sloupci, řádku a na obou úhlopříčkách jsou různa čísla od 1 do N. | |
| TCif | 2 | Je zadaná posloupnost až 8 cifer a číslo X. Úkolem je vypsat (do souboru) všechny možnosti jak vložit mezi cifry znaménka (+-*/) nebo NIC, tak aby se vzniklý výraz rovnal X. Na prioritu +-/* se nehraje, počítá se odleva (např. pro vstup 5 0 5 0, X=100, je řešení například 50+50). | |
| TSif | 2 | Monte Christova šifra. Máte mřížku (matici) 2N x 2N, ve které je vyříznuto N otvorů. Do nich po řádcích vpisujete písmena textu, který chcete zašifrovat. Když zaplníte všechny otvory, matici pootočíte o devadesát stupňů a jedete znova (tudíž je jasné, že matice musí být volena tak, aby se otvory nepřekrývaly po pootočení, že :). Takto pokračujete, dokud neotočíte matici potřetí. Pokud je text delší a nevešel se celý, jedete další blok textu stejným způsobem. Napište šifrátor a dešifrátor daného textu. (Při psaní uvažujte optimalizaci pro dlouhé úseky textu, například Babičku:) | |
| 10. ledna | LabT | 2 | Test v labu, ulohy na fox.matfyz.cz/test. |
| Jméno | Úkoly | Zápočťák | Zápočet | ||
|---|---|---|---|---|---|
| Odevzdané | Bodů celkem | Specifikace | Hodnocení | ||
Pokud byste něco potřebovali, napište mi na fox {zavináč} ucw {tečka} cz.