Matematická olympiáda – kategorie P

Zadání úloh ústředního kola (1. soutěžní den) 49. ročníku

Všeobecné pokyny

Na řešení úloh máte 5 hodin čistého času.

Řešení každého příkladu musí obsahovat:

• Popis řešení, to znamená slovní popis použitého algoritmu, argumenty zdůvodňující jeho správnost (případně důkaz správnosti algoritmu), diskusi o efektivitě vašeho řešení (časová a paměťová složitost). Slovní popis řešení musí být jasný a srozumitelný i bez nahlédnutí do samotného zápisu algoritmu (do programu).
• Program. V úlohách P-III-1 a P-III-2 je třeba uvést dostatečně podrobný zápis algoritmu, nejlépe ve tvaru zdrojového textu nejdůležitějších částí programu v jazyku Pascal nebo C. Ze zápisu můžete vynechat jednoduché operace jako vstupy, výstupy, implementaci jednoduchých matematických vztahů apod. V úloze P-III-3 uveďte místo programu schéma navrženého registrového stroje.

P-III-1 Jednosměrky

V centru města je N důležitých křižovatek očíslovaných od 1 do N, které jsou pospojovány M cestami. Cestou rozumíme asfaltový koberec spojující dvě konkrétní křižovatky. Mezi libovolnými dvěma křižovatkami může vést nejvýše jedna cesta. Všechny cesty jsou obousměrné a na každou křižovatku se lze po těchto cestách dostat ze všech ostatních křižovatek, tzn. pro libovolnou dvojici křižovatek i a j, i<>j, existují křižovatky a₁, a₂, ..., a_k takové, že a₁=i, a_k=j a pro i=1,2,...,k-1 vede mezi křižovatkami a_i a a_i+1 cesta. Pro účely této úlohy budeme křižovatkou označovat i místo, do něhož vede jen jediná cesta (případně dvě cesty).

V rámci zvyšování dopravní bezpečnosti se městská rada rozhodla co nejvíce cest "zjednosměrnit". To znamená, že pokud mezi křižovatkami i a j existuje cesta, po "zjednosměrnění od i k j" (označujeme i->j) bude po této cestě povoleno jet z křižovatky i na křižovatku j, ale ne naopak. Městská rada má jedinou podmínku: z každé křižovatky musí být možné dojet na všechny ostatní křižovatky při dodržení přikázaného směru jízdy.

Soutěžní úloha

Je dán počet křižovatek N a počet cest M. Dále je dáno takových M dvojic křižovatek {i,j}, i<>j, že mezi křižovatkami i a j vede cesta. Napište program, který vypíše všechny "zjednosměrněné" cesty a jejich povolený směr jízdy tak, aby byl počet zbývajících obousměrných cest minimální. Jestliže existuje více možných řešení, vypište jedno libovolné z nich.

Příklad

Vstup:
N = 8, M = 10
{1,2}
{2,3}
{2,8}
{3,4}
{3,8}
{4,5}
{4,7}
{5,6}
{5,7}
{6,7}

Výstup:
2->3
3->8
8->2
4->5
5->6
6->7
7->4
5->7

(Jiným možným řešením je přesměrovat {5,7} na 7->5.)

P-III-2 Volby

V jisté zemi právě skončily volby. Každý volič v nich hlasoval pro jednoho z navržených kandidátů. Za poslance místního shromáždění jsou zvoleni všichni kandidáti, pro které hlasovala více než jedna k-tina všech voličů. Všimněte si, že v takovýchto volbách je možné zvolit nejvýše k-1 kandidátů (možná jich ale bude zvoleno méně). Máte k dispozici výsledky hlasování jednotlivých voličů a máte co nejrychleji zjistit, kteří kandidáti byli zvoleni do zastupitelstva.

Soutěžní úloha

Voleb se zúčastnilo N voličů očíslovaných od 1 do N a M (M<=N) kandidátů očíslovaných od 1 do M (někteří kandidáti však nemuseli získat ani jeden hlas). Výsledky hlasování jsou uloženy v poli a, přičemž platí, že volič i (1<=i<=N) hlasoval pro kandidáta číslo a[i]. Obsah tohoto pole nesmíte měnit. Dále máte dáno číslo k>=2 (velmi malé v porovnání s N).

Napište program, který vypíše čísla všech kandidátů, pro něž hlasovalo více než N/k voličů.

Poznámka: Čísla M a N mohou být velmi velká. Snažte se proto, aby váš program pracoval co nejefektivněji a aby používal co nejméně paměti.

Příklad

Vstup:
N=11, k=3, M=7
A=(1,2,3,2,1,1,7,2,3,2,1)

Výstup:
Zvoleni jsou kandidáti 1, 2.

Vstup:
N=8, k=4, M=4
A=(1,2,3,3,4,2,4,1)

Výstup:
Nebyl zvolen žádný kandidát.

P-III-3 Minského registrové stroje

(Oproti domácímu kolu se studijní text liší příkladem sestavení Minského stroje z bloků.)

Minského registrový stroj je jednoduché výpočetní zařízení. K dispozici má několik registrů označených R₀, R₁, R₂,..., přičemž v každém registru může být uloženo jedno libovolně velké nezáporné celé číslo.

Minského registrový stroj může mít jeden nebo více vstupů, jejichž hodnoty jsou na začátku výpočtu uloženy v registrech R₁,...,R_k, kde k je počet těchto vstupů. Ostatní registry jsou na začátku výpočtu inicializovány na hodnotu nula. Po skončení výpočtu Minského registrového stroje je výsledkem hodnota uložená v registru R₀.

Každý Minského registrový stroj je řízen pevně daným programem. V programu se mohou vyskytovat tyto příkazy:

• Zvýšení hodnoty v daném registru o 1.
• Snížení hodnoty v daném registru o 1 (pokud je v registru nula, hodnota se nezmění).
• Test na nulu zjistí, zda je v daném registru nula.

Registr je určen svým číslem. Číslo registru je v příkazu vždy pevně zadáno, není tedy možné k určení registru použít obsah jiného registru.

Programy budeme zakreslovat do schémat, přičemž zvýšení hodnoty registru R_i budeme značit obdélníkem s nápisem R_i++, snížení hodnoty registru R_i budeme značit obdélníkem s nápisem R_i--, test na nulu v registru R_i značíme oválem s nápisem R_i?. Začátek programu označujeme písmenem Z v kroužku a konec programu písmenem K v kroužku (program může mít i více konců, ale jen jeden začátek). Jednotlivé příkazy jsou pospojovány šipkami, které určují tok řízení programu. Z obdélníka vychází vždy jediná šipka. Z oválu vycházejí dvě šipky, přičemž jedna z nich je označena nulou (po ní pokračuje výpočet tehdy, když byla v testovaném registru nula, v opačném případě výpočet sleduje druhou šipku). Jestliže v programu za sebou následuje několik příkazů zvýšení, snížení a výpočtu hodnoty funkce, můžeme je napsat pod sebe do jednoho obdélníku.

Použití bloků

Při kreslení složitějších schémat se nám může stát, že některé části potřebujeme použít vícekrát. Abychom se vyhnuli opakovanému kreslení stejných skupin příkazů, budeme je seskupovat do bloků. Blok je skupina příkazů s jedním určeným počátečním příkazem a s jednou nebo více výstupními šipkami. Každý blok musíme nejprve definovat, tj. nakreslit příslušnou skupinu příkazů. Definovaný blok potom můžeme použít na libovolném místě při kreslení schématu registrového stroje (případně při definování jiných bloků). Blok značíme obdélníkem s vepsaným jménem bloku, z tohoto obdélníka vychází příslušný počet šipek. V definici bloku můžeme některé registry označit proměnnými. Za tyto proměnné se dosadí konkrétní registry až na místě, kde se blok použije (v tom případě napíšeme do obdélníka za jméno bloku do závorek registry, které se mají dosadit za jednotlivé proměnné). Proměnným, za které nedosadíme žádný registr, se nakonec přiřadí nepoužité registry (každá kopie proměnné má vlastní registr). Použití bloků nejlépe objasní příklad.

Příklad

Sestrojte stroj, který bude mít na vstupu číslo n (uložené v registru R₁) a který vypočítá součet druhých mocnin čísel od 0 do n (výsledný součet uloží do registru R₀).

Řešení

Nejprve nadefinujeme blok ADD(x,y), který k registru x přičte obsah registru y (obsah registru y se přitom zachová). Tento blok bude používat jeden pomocný registr p, kterému není explicitně přiřazen žádný konkrétní registr. Bude mít dvě výstupní šipky: jestliže je v registru y nula, použije se šipka A, v opačném případě použijeme šipku B.

Náš registrový stroj bude pracovat následovně: K obsahu registru R₀ (který je na začátku nulový) budeme postupně přičítat n², (n-1)², ..., 1². V registru R₁ bude vždy uloženo číslo x, jehož druhou mocninu právě přičítáme. Jestliže x=0, končíme (větev A bloku ADD(R₂,R₁)). V opačném případě pomocí ADD(R₂,R₁) zkopírujeme obsah R₁ do R₂ (obsah R₂ byl předtím nulový) a pomocí cyklu a dalšího bloku ADD přičítáme do R₀ x-krát číslo x. (Všimněte si, že v R₂ je po proběhnutí tohoto cyklu opět nula.) Tento postup opakujeme, přičemž snižujeme obsah R₁ o jedničku.

Soutěžní úloha

Konečná množina nezáporných celých čísel M = {c₁,c₂,...,c_n} se dá jednoznačně zakódovat do jednoho nezáporného celého čísla m takto: m = 2^c¹+...+2^c_n. (V množině se může každý prvek nacházet nejvýše jednou, tzn. c_i<> c_j pro i<> j.) Jestliže si představíme zápis čísla m ve dvojkové soustavě, potom číslo c patří do množiny M právě tehdy, když c-tý bit zápisu m je jednička. Bity číslujeme zprava doleva, tj. nejpravější bit má číslo 0, jeho levý soused číslo 1, atd.

Sestrojte Minského registrový stroj, který dostane na vstupu kód m nějaké množiny M a číslo s a zjistí, zda lze číslo s vyjádřit jako součet některých prvků množiny M, tj. zda existuje taková podmnožina M' množiny M, že součet jejích prvků je s. Číslo m je na začátku výpočtu uloženo v registru R₁, číslo s v registru R₂. Po skončení výpočtu musí registr R₀ obsahovat jedničku v případě, že s je součtem některých prvků množiny M a nulu v opačném případě. Součet nula prvků má definitoricky hodnotu nula.

Příklad

Pro hodnoty m = 203 (11001011 v dvojkové soustavě, tzn. M = {0,1,3,6,7}), s = 10 je správný výsledek 1 (10 = 3+7). Pro m=203, s=12 je výsledek 0 (protože 12 nelze získat součtem čísel vybraných z množiny M). Pro m libovolné, s=0 je správný výsledek 1.