Matematická olympiáda – kategorie P

Zadání úloh domácího kola 47. ročníku

Kategorie P matematické olympiády je zaměřena na algoritmizaci a programování. Je určena studentům všech ročníků středních škol.

Řešení každého příkladu musí obsahovat popis použitého algoritmu, zdůvodnění jeho správnosti a diskusi o efektivitě zvoleného řešení (tzn. posouzení časových a paměťových nároků programu). V praktických úlohách P-I-2 a P-I-3 je třeba k řešení připojit odladěný program zapsaný v jazyce Pascal nebo C. Program se odevzdává v písemné formě (jeho výpis je tedy součástí řešení) i na disketě, aby bylo možné v případě nejasností otestovat jeho funkčnost. Slovní popis řešení ovšem musí být jasný a srozumitelný i bez toho, že by bylo třeba nahlédnout do zdrojového textu programu. V úloze P-I-1 se odladěný program nutně nepožaduje, stačí místo něj uvést dostatečně podrobný slovní zápis algoritmu nebo neodladěný zdrojový text nejdůležitějších částí programu. V úloze P-I-4 místo výsledného programu nakreslíte schémata navržených kombinačních sítí.

P-I-1 Večírek

Na večírku se sešlo několik hostů. Víme, kteří z nich se vzájemně znají a kteří ne. Vztah "znát se" uvažujeme zásadně jako symetrický, tzn. o libovolné dvojici lidí platí, že buď se navzájem znají, nebo ani jeden z dvojice nezná toho druhého. Hostitel chce posadit každého hosta buď v hale, nebo v obývacím pokoji. Navrhněte algoritmus, který určí, kolika způsoby může hostitel rozmístit své hosty do obou místností tak, aby se v rámci každé místnosti všichni navzájem znali.

Vstupem algoritmu (programu) je počet hostů N, N <= 100, a dále seznam těch dvojic hostů, kteří se spolu znají. Pro jednodušší zadávání vstupních dat si jednotlivé hosty označíme celými čísly od 1 do N, takže na vstupu bude zadán seznam dvojic čísel. Výsledkem bude jediné číslo udávající počet možných rozdělení hostů.

Příklad

Je-li N=4 a znají se pouze dvojice (1,2) a (3,4), má hostitel dvě možnosti: buď usadí hosty 1 a 2 do haly a hosty 3 a 4 do obývacího pokoje, nebo naopak hosté 1 a 2 budou sedět v obývacím pokoji a hosté 3 a 4 v hale. Výsledkem bude tedy číslo 2.

Příklad

Výrobce nabízí N kusů výrobků známých hmotností. Zákazník k němu přijel pro zboží s nákladním autem o dané nosnosti C. Hmotnosti všech výrobků i nosnost auta jsou zadány v kilogramech a jsou celočíselné. Zákazník chce na auto naložit výrobky tak, aby byla nosnost auta plně využita. Napište program, který zjistí, zda je to možné. Program musí pracovat dostatečně rychle a být tedy reálně použitelný i pro velké počty nabízených výrobků (řádově stovky).

Program bude číst všechna vstupní data z textového souboru NAKLAD.IN. Na prvním řádku souboru je uvedeno jedno kladné celé číslo C představující nosnost auta, C <= 10000. Druhý řádek obsahuje jediné kladné celé číslo N určující počet nabízených výrobků, N <= 1000. Následující řádky souboru NAKLAD.IN obsahují N kladných celých čísel - hmotností jednotlivých výrobků (menších než 10000).

Do výstupního souboru NAKLAD.OUT program zapíše jediný řádek s výsledkem výpočtu. Výsledkem bude slovo ANO, pokud je možné vybrat z nabídky takovou skupinu výrobků, aby byl součet jejich hmotností roven přesně C. V opačném případě program napíše do výstupního souboru slovo NE.

Příklad vstupního a odpovídajícího výstupního souboru

NAKLAD.IN

1000 5 300 800 100 550 100

NAKLAD.OUT

ANO Výsledkem je odpověď ANO, neboť auto o nosnosti 1000 kg přesně zaplníme, pokud naložíme výrobek o hmotnosti 800 kg a oba nabízené výrobky o hmotnostech 100 kg.

P-I-3 Okna

Na počítači máme nainstalován operační systém MO-P-Windows pracující v grafickém rozlišení 300 x 200 bodů. Momentálně máme spuštěno několik aplikací a na obrazovce je zobrazeno jejich N oken. Každé okno je obdélníkové (příp. čtvercové), známe přesné umístění a velikost jednotlivých oken. Okna se mohou na obrazovce částečně nebo úplně překrývat.

Chceme spustit další aplikaci, která potřebuje zobrazit jedno nové okno. Známe velikost nového okna a požadujeme, aby na obrazovce nezakrylo ani část žádného z oken, která jsou tam již zobrazena. Napište program, jenž pro nové okno najde vhodné umístění na obrazovce, nebo případně oznámí, že dostatečně velké volné místo neexistuje.

Program čte vstupní data z textového souboru OKNA.IN. Na prvním řádku souboru je zadán počet již zobrazených oken N. Následuje N řádků specifikujících velikost a umístění jednotlivých oken. Pro každé z oken jsou zadána čtyři celá čísla x1, y1, x2, y2 představující souřadnice bodu na obrazovce [x1,y1], který tvoří levý horní roh okna, a bodu [x2,y2], v němž leží pravý dolní roh okna. Souřadnice bodů na obrazovce se zadávají tak, že bod v levém horním rohu celé obrazovky má souřadnice [0,0] a bod v pravém dolním rohu má souřadnice [299,199]. První souřadnice nějakého bodu na obrazovce znamená vodorovnou vzdálenost tohoto bodu od levého okraje obrazovky, druhá souřadnice určuje svislou vzdálenost bodu od horního okraje obrazovky. Poslední řádek vstupního souboru OKNA.IN obsahuje dvě celá čísla určující velikost nově umisťovaného okna (nejprve šířka, pak výška okna). Oba rozměry nového okna jsou vyjádřeny počtem bodů v používaném grafickém zobrazení.

Výsledek výpočtu programu zapíše na jeden řádek do výstupního textového souboru OKNA.OUT. Výsledkem bude buď dvojice čísel, která znamená souřadnice levého horního rohu nalezeného přípustného umístění pro nové okno (libovolného jednoho umístění, je-li více možností), nebo slovo NELZE, pokud takovéto okno nelze na obrazovku umístit. Požadavek, aby se nové okno nepřekrývalo s žádným z ostatních oken znamená, že žádný hraniční bod nového okna nesmí ležet v jiném okně ani na jeho hranici.

Příklad vstupního a odpovídajícího výstupního souboru

OKNA.IN

2 10 10 280 30 20 20 40 180 30 160

OKNA.OUT

41 31 Úloha popsaná uvedeným vstupním souborem má více řešení, vyhovují například také dvojice souřadnic levého horního rohu nového okna [60,35] nebo [270,40]. Naopak nevyhovuje umístění [60,30], neboť horní hranice nového okna by se překrývala s dolní hranicí prvního z uvedených oken. Nevyhovuje ani umístění [270,41], neboť dolní hranice nového okna by se o jeden bod nevešla na obrazovku.

P-I-4 Kombinační sítě

Abeceda je konečná neprázdná množina symbolů, s nimiž kombinační síť pracuje. Obsahuje vždy speciální symbol @ (prázdný symbol).

Základním stavebním prvkem kombinačních sítí jsou kombinační hradla (dále jen hradla). Každé z nich má dva vstupy a jeden výstup a je jednoznačně určeno svou přechodovou funkcí. Ta každé kombinaci možných hodnot na vstupech hradla (což jsou některé ze symbolů abecedy) jednoznačně přiřazuje hodnotu na výstupu. Symbol @ je funkcí přiřazen právě tehdy, když je přítomen tentýž symbol na kterémkoliv ze vstupů hradla.

Kombinační síť se skládá ze vstupů I1 až In, výstupů O1 až Om a hradel H1 až Hk. Každý ze vstupů hradla Hi je přímo připojen na některý ze vstupů sítě Ii nebo na výstup nějakého hradla Hj, j < i (v síti tedy nemohou vzniknout cykly), případně na něj může být trvale připojen libovolný ze symbolů abecedy (konstanta). Stejným způsobem jsou připojeny i výstupy sítě.

Výpočet kombinační sítě probíhá v taktech. V nultém taktu jsou na všech vstupech sítě vstupní data a na výstupech všech hradel symboly @. V každém dalším taktu se nastaví výstupy všech hradel podle toho, jaké hodnoty byly na jejich vstupech v taktu předchozím. Tímto způsobem se pokračuje tak dlouho, dokud na alespoň jednom z výstupů sítě je symbol @. Poté se výpočet sítě zastaví a její výstupy obsahují výsledek výpočtu.

Podle toho, jak probíhá výpočet, je možné síť rozdělit do hladin. Do i-té hladiny zařadíme ta hradla, která v i-tém taktu mají na svém výstupu platnou hodnotu (tedy jiný symbol abecedy než @) a o krok dříve ještě tuto podmínku nesplňovala. Výpočet tedy bude probíhat tolik taktů, kolik má síť hladin.

Navrhnout kombinační síť řešící danou úlohu znamená zvolit abecedu, popsat přechodové funkce všech použitých hradel (například tabulkou) a určit propojení sítě (tj. vzájemné propojení hradel, vstupů a výstupů). Při návrhu sítě se snažíme dosáhnout co nejrychlejšího výpočtu, což znamená minimalizovat počet hladin sítě.

Kombinační sítě můžeme pro větší přehlednost znázorňovat graficky - jednotlivá hradla jsou reprezentována obdélníčky (nahoře jsou zakresleny vstupy, dole výstup), přičemž hradla v téže hladině se umisťují vedle sebe. Uvnitř každého obdélníčku je označení příslušné přechodové funkce. Nad všemi hladinami jsou zakresleny vstupy sítě, zcela dole pak výstupy sítě.

Příklad

Navrhněte kombinační síť s N vstupy, které mohou nabývat hodnot 0 nebo 1, a s jedním výstupem. Na výstupu bude 0 právě tehdy, je-li počet jedniček na vstupech sudý, jinak bude na výstupu sítě hodnota 1.

Řešení

Předpokládejme, že N je mocnina dvou. V opačném případě doplníme fiktivní vstupy mající stále hodnotu 0 - tím výsledek neovlivníme. Definujeme hradlo XOR s následující přechodovou funkcí:

XORY
01
X001
110

Toto hradlo řeší zadanou úlohu pro 2 vstupy. Nyní předpokládejme, že úlohu již umíme řešit pro 2k vstupů a chceme ji vyřešit pro počet dvojnásobný, tedy pro 2k+1 vstupů. Vstupy snadno rozdělíme do dvou stejně velkých částí (je jedno, jakým způsobem - pro názornost například na prvních 2k a zbytek). Nyní označíme A výsledek řešení úlohy pro první část a B pro druhou. Pokud byl v obou polovinách sudý počet jedničkových vstupů (A=B=0) nebo v obou lichý (A=B=1), má výsledek být 0, jinak 1. To je ovšem přesně ten výsledek, jaký dává přechodová funkce hradla XOR pro vstupy A, B. Pro 8 vstupů tedy bude síť vypadat takto:

12345678
XORXORXORXOR
XORXOR
XOR
Výstup

Tímto způsobem zkonstruovaná kombinační síť má přibližně log2(N) hladin, tudíž časová složitost výpočtu je O(log N).

Soutěžní úloha

  1. Navrhněte kombinační síť s abecedou {0,1,2,3,4,5,6,7,8,9,@}, N vstupy a dvěma výstupy, která nalezne minimální (výstup A) a maximální (výstup B) z hodnot na vstupech.

    Příklad: Je-li N=4 a na jednotlivých vstupech sítě jsou zadány hodnoty 6, 3, 7, 3, musí mít výstup A hodnotu 3 a výstup B hodnotu 7.

  2. Navrhněte kombinační síť s abecedou {0,1,@}, 2k-1 vstupy očíslovanými přirozenými čísly 0 až 2k-2 a k výstupy. Výstupy sítě budou po ukončení výpočtu obsahovat ve dvojkové soustavě zapsané nejmenší z čísel vstupů, na nichž je hodnota 1. Pokud budou na všech vstupech sítě nuly, všechny výstupy dostanou hodnotu 1 (tato kombinace jako jediná neodpovídá žádnému číslu vstupu).

    Příklad: Pro k=3 bude mít kombinační síť 7 vstupů a 3 výstupy. Vstupy jsou označeny čísly 0, 1, 2, 3, 4, 5, 6. Pokud na jednotlivé vstupy zadáme hodnoty (po řadě podle čísel vstupů) 0, 0, 0, 1, 0, 1, 1, musí výstupy sítě nabýt hodnot po řadě 0, 1, 1. Hodnota 1 je totiž na vstupech číslo 3, 5 a 6, nejmenším z těchto čísel je 3 a zápis čísla 3 ve dvojkové soustavě zní 011. Na každém z výstupů se objeví jedna cifra tohoto dvojkového zápisu (se zachováním pořadí cifer).