Řešení každého příkladu musí obsahovat:
K. O. Lektor je sběratel náhrdelníků. Náhrdelníky se liší počtem, pořadím a druhy použitých drahokamů. Jeho finanční zdroje nejsou neomezené, proto by se chtěl vyhnout tomu, aby kupoval více kusů stejného typu náhrdelníku. Vymyslel tedy kódování, které funguje takto: každému druhu drahokamů přiřadil písmeno abecedy a tyto kódy zapsal v pořadí, v jakém se nacházejí na náhrdelníku, počínaje libovolným z nich. Dále si pořídil stroj, který pro zadaný kód zjistí, zda již má příslušný náhrdelník ve sbírce.
Obchodníci s náhrdelníky si samozřejmě rychle povšimli slabiny tohoto systému -- pokud náhrdelník pootočili, případně obrátili, kód se změnil a K. O. Lektor si tak nakoupil několik duplikátů -- například náhrdelník ABCA si koupil i jako AABC a ACBA. Chtěl by tedy svůj stroj vylepšit tak, aby tuto situaci rozeznal. Napište program implementující toto vylepšení.
Program dostane na vstupu několik kódů náhrdelníků x1,...,xN (1≤ N≤ 1.000.000) a měl by pro každý z nich vypsat, zda si ho má K. O. Lektor koupit nebo ne tak, aby získal každý typ náhrdelníků právě jednou. Pokud je náhrdelník xi různý od všech náhrdelníků x1,...,xi-1 (včetně rotací a zrcadlení), program odpoví „Kup to”, v opačném případě odpoví „Podvod”.
Program může využívat starý stroj jako „černou skříňku”, která si pamatuje množinu kódů náhrdelníků (na počátku práce množinu prázdnou) a je schopna do této množiny kódy přidávat (zavoláním procedury Pridej) a zjišťovat, jestli stroj již nějaký kód zná (zavoláním funkce UzMam, která vrací true (1 v C), pokud někdy předtím byla zavolána procedure Pridej pro stejný kód):
int UzMam (const char *kod); /* v C */
void Pridej (const char *kod);
function UzMam (var kod:string):boolean; { v Pascalu }
procedure Pridej (var kod:string);
K. O. Lektor má na váš program následující požadavky: Paměťová složitost nesmí záviset na počtu testovaných náhrdelníků. Časová složitost by měla být co nejnižší, přičemž volání funkce starého stroje počítáme jako operace běžící v lineárním čase. Ze dvou programů o stejné časové složitosti pak považuje za lepší ten, který funkce starého stroje volá méněkrát.
ABCA Kup to
ACBA Podvod
AABC Podvod
Magické observatoře (MO) nedávno otevřely nový areál v Horních Mokřadech. Podnebí v Horních Mokřadech je bohužel poměrně deštivé, a tak se vedení MO rozhodlo, že propojí všechny budovy v areálu nadzemními krytými mosty. Vedení MO samozřejmě chce, aby si dodatečné stavební úpravy vyžádaly co nejmenší náklady. Proto požaduje, aby celková délka mostů, které propojí budovy v areálu, byla co nejmenší. Navíc, kvůli vlivu energetických zón v okolí Horních Mokřad, musí všechny mosty vést severojižně.
Vaším úkolem je vytvořit algoritmus, který pro zadanou mapu areálu MO navrhne nejlepší možné propojení budov severojižními mosty. Pokud všechny budovy nelze navzájem propojit, pak algoritmus vypíše vhodnou zprávu.
Na vstupu algoritmus obdrží mapu areálu MO jako čtvercovou síť o N řádcích a M sloupcích. Budovy v areálu jsou reprezentovány znaky x, volná prostranství tečkami. Budova je maximální oblast tvořená políčky x, která se mezi sebou dotýkají hranami. Vaším úkolem je navrhnout propojení budov severojižními (na mapě svislými) mosty tak, aby mezi každými dvěma budovami existovala cesta používající pouze políček x a mostů: Mezi dvěma políčky x lze přejít, pokud sousedí hranou, mosty lze používat pouze v severojižním směru, tj. seshora dolů nebo zdola nahoru v jejich směru na mapě.
Při (popisu) řešení této úlohy se soustřeďte na efektivní nalezení optimálního propojení mezi budovami a zdůvodnění správnosti navrženého algoritmu.
..xxxxx. .......x ...x...x .x.x.... .xxx..xx
Areál je tvořen čtyřmi budovami (na následujícím obrázku jsou jejich políčka označena čísly 1 až 4; všimněte si, že políčka s čísly 1 a 2 tvoří dvě různé budovy):
..11111. .......2 ...3...2 .3.3.... .333..44
Optimální řešení úlohy pro zadanou mapu je propojit dvojici budov 1 a 3 mostem délky jedna, dvojici budov 2 a 4 rovněž mostem délky jedna a budovy 1 a 4 mostem délky tři:
..11111. ...|..|2 ...3..|2 .3.3..|| .333..44
Protože mosty lze používat pouze severojižně, nemůžeme z mostu spojujícího budovy 1 a 4 přejít do budovy 2 a je třeba vybudovat i most mezi budovami 2 a 4.
Pro M=6 a N=5 uvažme následující mapu areálu:
xxxxxx x....x x.xx.x x....x xxxxxx
Areál je tvořen dvěma budovami a k jejich propojení stačí vybudovat jeden most délky 1:
xxxxxx x.|..x x.xx.x x....x xxxxxx
Pro M=5 a N=4 uvažme následující mapu areálu:
xxx.. ..... xxx.. ...xx
Areál je tvořen třemi budovami. Protože budovu v pravém dolním rohu nelze spojit s žádnou jinou budovou mostem, všechny budovy nelze vzájemně propojit.
P-III-3 ALÍK
Sestrojte program pro stroj ALIK, který spočte dvojkový logaritmus zadaného nenulového
čísla x, tedy pozici nejlevější jedničky v x. Pozice bitů rostou zprava doleva,
nejnižší řád je na pozici 0.
Aritmeticko-logický integerový kalkulátor (zkráceně ALIK) je počítací stroj pracující s W-bitovými celými čísly v rozsahu 0 až 2W-1 včetně; kdykoliv budeme hovořit o číslech, půjde o tato čísla. Budeme je obvykle zapisovat ve dvojkové soustavě polotučnými číslicemi a vždy si na začátek dvojkového zápisu doplníme příslušný počet nul, aby číslic (bitů) bylo právě W. Většinou také nebudeme rozlišovat mezi číslem a jeho dvojkovým zápisem, takže i-tým bitem čísla budeme rozumět i-tý bit jeho dvojkového zápisu (bity číslujeme zprava doleva od 0 do W-1).
Paměť stroje je tvořena 26 registry pojmenovanými a až z. Každý registr vždy obsahuje jedno číslo.
ALIK se řídí programem, což je posloupnost přiřazovacích příkazů typu registr:=výraz, přičemž výraz může obsahovat konstanty (čísla zapsaná ve dvojkové soustavě), registry, závorky a následující operátory (velká písmena značí podvýrazy, v pravém sloupci jsou priority operátorů):
| A + B | sečte čísla A a B. Pokud je výsledek větší než 2W-1, číslice vyšších řádů odřízne. Jinými slovy, počítá součet modulo 2W. | 4 |
| A - B | odečte od čísla A číslo B. Pokud je A < B, spočte 2W + A - B, čili rozdíl modulo 2W. | 4 |
| A * B | vynásobí dvě čísla, výsledek opět modulo 2W. | 6 |
| A / B | vydělí číslo A číslem B dělení nulou dá vždy výsledek 0. | 6 |
| A % B | vrátí zbytek po dělení čísla A číslem B, čili A - A*(A % B) pokud je B=0, je výsledek roven A. | 6 |
| NOT A | spočte bitovou negaci čísla A, což je číslo, jehož i-tý bit je 0 právě tehdy, je-li i-tý bit čísla A roven 1, a naopak. | 9 |
| A AND B | bitové operace: | |
| A OR B | Vyhodnocují se tak, že se i-tý bit výsledku spočte z i-tého bitu čísla A a | |
| A XOR B | i-tého bitu čísla B podle následujících tabulek: | |
| 0 AND 0 = 0 0 OR 0 = 0 0 XOR 0 = 0 | ||
| 0 AND 1 = 0 0 OR 1 = 1 0 XOR 1 = 1 | ||
| 1 AND 0 = 0 1 OR 0 = 1 1 XOR 0 = 1 | ||
| 1 AND 1 = 1 1 OR 1 = 1 1 XOR 1 = 0 | ||
| A << B | posune číslo A o B bitů doleva, čili doplní na jeho konec B nul a odřízne prvních B bitů, aby byl výsledek opět W-bitový. | 2 |
| A >> B | posune číslo A o B bitů doprava, čili doplní na jeho začátek B nul a odřízne posledních B bitů, aby byl výsledek opět W-bitový. | 2 |
| a+b*c+d = (a+(b*c))+d | zde zafungují priority operátorů |
| 0101 + 1110 = 0011 | nejvyšší bit výsledku 10011 se již oříznul |
| 0001 - 1111 = 0010 | odčítáme modulo 16=10000 |
| 0101 AND 0011 = 0001 | takto funguje and |
| 0101 OR 0011 = 0111 | takto or |
| 0101 XOR 0011 = 0110 | a takto xor |
| (1 << 11) - 1 = 1000 - 1 = 0111 | jak vyrobit pomocí << posloupnost jedniček |
| a OR NOT a = 1111 | jak získat z čehokoliv samé jedničky |
Často budeme potřebovat, aby program mohl pracovat s většími čísly, než je číslo na vstupu, takže budeme rozlišovat velikost vstupu N (tj. počet bitů potřebných k zápisu vstupní hodnoty) a velikost W registrů a mezivýsledků, kterou si při psaní programu sami určíme. Pokud bychom ovšem povolili exponenciálně velká čísla (tedy W=2N), mohli bychom cokoliv spočíst v konstantním čase - stačilo by do jedné dlouhatánské konstanty uvedené v programu zakódovat všechny možné výsledky programu pro všechny hodnoty vstupu. Tak dlouhé registry lze však stěží považovat za realistické, proto přijměme omezení, že W musí být polynomiální ve velikosti vstupu, čili že existuje konstanta k taková, že pro každé N je W <= Nk.
Ne vždy si ovšem vystačíme s jedním programem, který funguje pro všechny velikosti vstupu - mnohdy potřebujeme podle N měnit hodnoty pomocných konstant v programu, někdy také nějakou operaci opakovat vícekrát v závislosti na velikosti vstupu. Povolíme si tedy programy zapisovat obecněji, a to tak, že uvedeme seznam pravidel, jež nám pro každé N vytvoří program, který počítá správně pro všechny vstupy velikosti N. [Formálně bychom tato pravidla mohli zavést třeba jako programy v nějakém klasickém programovacím jazyce. My si ale formalismus odpustíme a budeme je popisovat slovně.]
Při řešení úloh budeme chtít, aby časová složitost vygenerovaných programů, tedy jejich délka v závislosti na N, byla co nejmenší. Mezi stejně rychlými programy je pak lepší ten, který si vystačí s kratšími čísly, čili s menším W (to je analogie prostorové složitosti). Podobně jako u klasických programů ovšem budeme v obou případech přehlížet multiplikativní konstanty.
Zmiňme ale ještě konvence, které budeme používat při psaní všech ukázkových programů:
V levém sloupci naleznete jednotlivé příkazy, v pravém sloupci obecný tvar
spočítané hodnoty pro libovolné N. Pokud se nějaká číslice
nebo skupina číslic opakuje vícekrát, značíme opakování exponentem, tedy
08 je osm nul, (01)3 je zkratka za 010101. Velkými písmeny značíme
blíže neurčené skupiny bitů.
| x=A10i | |
| a := x-1 | a=A01i |
| b := x AND a | b=A00i |
Zbývá tedy vyřešit, jak z nuly udělat požadovanou jedničku a z nenuly nulu. K tomu si zavedeme operaci r := if(s,t,u), která bude realizovat podmínku: pokud s<>0, přiřadí r:=t, jinak r:=u. Provedeme to jednoduchým trikem: rozšíříme si registry o jeden pomocný bit vlevo, nastavíme v r tento bit na jedničku a sledujeme, zda se zmenšením vzniklého čísla o jedničku tento bit změní na nulu nebo ne:
| v := s OR 10N | v=1 s |
| v := v - 1 | v=1r' (je-li r<>0), jinak 01N |
| v := v AND 10N | v=10N nebo 00N |
| v := v >> N | v=0N1 nebo 0N0 |
| v := v - 1 | v=0N+1 nebo 1N+1 |
| r := (u AND v) OR (t AND NOT v) | r=t nebo u |
| y := if(b,0,1) | y=0 nebo 1 |
Ještě si ukažme, jak bude probíhat výpočet pro dva konkrétní 8-bitové vstupy (tehdy je N=8 a W=9):
| x=001011000 x=000100000 | |
| a := x-1 | a=001010111 a=000011111 |
| b := x AND a | b=001010000 b=000000000 |
| v := b OR 100000000 | v=101010000 v=100000000 |
| v := v - 1 | v=101001111 v=011111111 |
| v := v AND 100000000 | v=100000000 v=000000000 |
| v := v >> 8 | v=000000001 v=000000000 |
| v := v - 1 | v=000000000 v=111111111 |
| y := (000000001 AND v) OR (000000000 AND NOT v) | y=000000000 y=000000001 |
Paritu tedy vypočteme na logaritmický počet příkazů pracujících s N-bitovými čísly takto:
| p := x >> N/2 | p=horních N/2 bitů x |
| q := x AND 1N/2 | q=dolních N/2 bitů x |
| x := p XOR q | x=N/2-bitové číslo s paritou jako původní x |
| x := (x >> N/4 ) XOR (x AND 1N/4) | x=N/4-bitové ... (můžeme psát zkráceně) |
| ... | |
| x := (x >> 1) XOR (x AND 1) | x=1-bitové ... |
| y := x | y=x (už jen zkopírovat výsledek) |
| x=00110110 | |
| p := x >> 4 | p=99990011 |
| q := x AND 1111 | q=99990110 |
| x := p XOR q | x=99990101 |
| x := (x >> 2) XOR (x AND 11) | x=99999900 |
| x := (x >> 1) XOR (x AND 1) | x=99999990 |
| y := x | y=00000000 |
| x=0i1j0k | ||
| a | := x and (x-1) | a=0i1j-100k (viz Příklad 1) |
| b | := x + a | b=0i0j-110k |
| y | := x / b | b=0i0k1j |
Zde jsme využili toho, že dělení mocninou dvojky je možné použít jako bitový posun doprava, ovšem zadaný místo počtu bitů, o které se má posouvat, číslem majícím 1 na pozici, která se má po posunu objevit úplně vpravo.