Podmínky k získání zápočtu
Informace o zápočtovém programu
Domácí úkoly
Pascalu, nebude-li uvedeno jinak.
integer je dvoubajtový a longint čtyřbajtový.
| ID | Body | Popis | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Posl | 1 | Tohle je jen takové rozehřátí, byl pouze pro první tři (takže další řešení už neberu). Doplňte dalších pět členů posloupnosti 1 11 21 1112 3112 211213 312213. | |||||||||||||||||
| 3Mat | 3 | 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í. | |||||||||||||||||
| 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 | 3 | 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.
| |||||||||||||||||
| Souc | 1 | Napište program, který dostane na vstupu posloupnost N čísel a vypíše, jaký je největší součet prvků libovolné její souvislé podposloupnosti. | |||||||||||||||||
| Rost | 2 | Napište program, který dostane na vstupu posloupnost N čísel a vypíše délku nejdelší rostoucí podposloupnosti (nemusí být souvislá). Program musí být rozumně rychlý, tj. musí fungovat i pro posloupnosti délky desítek tisíc. Pokud bude Váš program fungovat rychleji než v čase O(N^2), dostanete bonus +1 bod. | |||||||||||||||||
| 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): 4 body. Lineární řešení: 5 bodů. | |||||||||||||||||
| Invz | 2 | Napiště program, který pro pole o N prvcích spočte počet inverzí, čili takových prvků, že ai>aj pro i<j. Váš program musí pracovat v lepším než kvadratickém čase. Omezeno do 22.11.2004 včetně. | |||||||||||||||||
| Zbyt | 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. Omezeno do 22.11.2004 včetně. | |||||||||||||||||
| Bala | 1-3 | Je dána posloupnost celých čísel ukončená nulou. Spočítejte délku nejdelšího vybalancovaného úseku (tj. souvislé podposloupnosti takové, že je v ní stejně záporných a kladných čísel). Kvadratické řešení: 1 bod. Řešení v čase O(N * log N): 2 body. Lineární řešení: 3 body. | |||||||||||||||||
| 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ů. | |||||||||||||||||
| Adds | 2-4 | Dostanete N čísel a1,a2,...,aN a ještě další číslo K. Vaším úkolem je najít a vypsat všechny podmnožiny čísel a1,...,aN takové, že jejich součet je K. (Čili jakými všemi možnostmi je možné dostat K jakou součet některých z čísel a1,...,aN,pokud můžete každé použít nanejvýš jednou.) Za řešení v čase O(N * K) dostanete 4 body. | |||||||||||||||||
| Domi | 1-3 | "Povinný" domácí úkol (je to jeden z písemkových příkladů). Dostanete N ≤ 30 dominových kostek, na každé jsou dvě čísla 1..6. Zjistěte, jak nejdelšího "hada" můžete z těchto kostek postavit. Hloupé řešení za 1 bod, za slévání kostiček nebo backtrack nad grafem (vrcholy jsou čísla na kostičkách, kostička je hrana) 3 body. | |||||||||||||||||
| Pyra | 2 | Dostanete číslo N a čísla ai,j, i ≤ 30 a j ≤ i uspořádaná takto:
Váš program musí fungovat v čase O(N^2). Omezeno do 30.11.2004 do 15:40. | |||||||||||||||||
| 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
| |||||||||||||||||
| 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. | |||||||||||||||||
| 3DSa | 2-4 | Na vstupu dostanete čísla N, M a O. Máte zjistit, kolik nejvíc figurek a jakými všemi způsoby se dá rozmístit na prostorovou šachovnici N x M x O políček, pokud se figurky na šachovnici N x M chovají jako dámy a ve třetím rozměru O jako věže. Body budou uděleny podle skutečné doby běhu programu - šachovnici 8 x 8 x 4 by měl 4-bodový program vyřešit během chvilky (řádově vteřiny). | |||||||||||||||||
| 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:) | |||||||||||||||||
| Jméno | Úkoly | Zápočťák | Zápočet | ||
|---|---|---|---|---|---|
| Odevzdané | Bodů celkem | Specifikace | Hodnocení | ||
| Erik Ferčák | Zvse(1), Fact(1), Prvc(1), TKal(2), Souc(1), Petr(1), Domi(1), Rost(2) | 10 | Game of life | Odevzdáno, OK | Ano |
| Filip Kittnar | Prvc(1), Fact(1), Rost(3), Domi(1), Zvse(1), Petr(1), Bala(1), Usek(1) | 10 | Akordy | Odevzdáno, OK | Ano |
| Martin Koníř | Prvc(1), Petr(1), Fdig(2), Test 1 v labu(5), Test 2 v labu(2) | 11 | Vláčky | Odevzdáno, OK | Ano |
| Martin Kontsek | Prvc(1), Fact(1), Petr(1), Domi(1), FDig(3), Souc(1), TMor(2), Test 1 v labu(2), Test 2 v labu(2) | 14 | Kreslítko | Odevzdáno, OK | Ano |
| Filip Kostomlatský | 0 | Mraveniště | Neodevzdáno | Ne | |
| Honza Kotera | Souc(1), Bala(1), Fact(1), Prvc(1), SSum(1), TKal(2), TNas(2), Usek(1) | 10 | Tanky | Odevzdáno, OK | Ano |
| Jana Kravalová | Posl(1), Prvc(1), Fact(1), Fdig(3), Usek(4), Petr(1), Souc(1), Invz(2), Zvse(1), Pyra(2), 3Mat(3), Rost(2), SSum(1), Zpoc(1), TNas(2) | 26 | Tree lib | Odevzdáno, OK | Ano |
| Standa Kuřík | Posl(1), Fact(1), Prvc(1), TCif(2), TMor(2), Zvse(1), TLat(2) | 10 | Pretty-printing | Odevzdáno, OK | Ano |
| Tomáš Kypta | Prvc(1), Fact(1), Fdig(1), Invz(2), Usek(1), 3Mat(3), Bala(1), Souc(1), TNas(2), TLat(2), TMor(2) | 17 | Území | Odevzdáno, OK | Ano |
| Petr Lasák | Prvc(1), Fact(1), Invz(2), Pyra(2), Petr(1), Adds(2), Domi(3), TCif(2), TNas(2) | 16 | Dáma | Odevzdáno, OK | Ano |
| Petr Maixner | 0 | Akordy | Neodevzdáno | Ne | |
| Vladislav Marks | 0 | Žádná | Neodevzdáno | Ne | |
| Radek Mlada | Prvc(1), Fact(1), TCif(2), TNas(2), TKal(2), TSif(2) | 10 | 3D grafy | Odevzdáno, OK | Ano |
| Ondřej Moravčík | 0 | Matovátko | Neodevzdáno | Ne | |
| Pavlína Pecoldová | Posl(1), Prvc(1), TKal(2), Test 1 v labu(3), Test 2 v labu(3) | 10 | Myslím si zvíře | Odevzdáno, OK | Ano |
| Martin Pilát | Prvc(1), Fact(1), Fdig(2), Petr(1+i), SSum(1), TKal(2+πi), TNas(2) | 10 | Špión | Odevzdáno, OK | Ano |
| Honza Preibisch | 0 | Žádná | Neodevzdáno | Ne | |
| Emil Slezák | ZVse(1), TMor(2), Petr(1), Fact(1), FDig(3) | 8 | Pí | Neodevzdáno | Ne |
| Jiří Täuber | Prvc(1), Fact(1), Fdig(2), Souc(1), TNas(2), Test 2 v labu(2), Zvse(1) | 10 | Pišqorky | Odevzdáno, OK | Ano |
| Miroslav Valníček | SSum(4), Prvc(1), Souc(1), Usek(4) | 10 | Kalkulačka | Odevzdáno, OK | Ano |
Pokud byste něco potřebovali, napište mi na fox {zavináč} ucw {tečka} cz.