Táto úloha je teoretická. Ako svoje riešenie odovzdaj pdf súbor, v ktorom bude tvoje riešenie aj so zdôvodnením, prečo je správne. Po konci kola ti riešenie opraví vedúci, a napíše ti komentár – povie ti kde si spravil(a) chyby, prípadne ti poradí, ako vieš svoje riešenia zlepšiť.
Ak máš hocijaké otázky k tejto úlohe, napíš Štepimu na [email protected]
Bolo raz jedno kráľovstvo a v ňom vládol kráľ. Vládnutie v takej veľkej krajine ale bolo veľmi namáhavé, tak si zohnal ministrov, ktorým dával robiť prácu zaňho. Po čase toho ale aj tí ministri začali mať príliš veľa roboty, a tak si aj oni zohnali ďalších úradníkov, ktorým by mohli dávať robiť časť svojej roboty. Ako sa kráľovstvo rozrastalo, úradníci si postupne zháňali ďalších podriadených. (Každý úradník môže byť priamy podriadený iba jedného úradníka.)
Kráľ má teraz problém, že vôbec nevie ani, kto všetko sú vlastne jeho úradníci. Rád by o nich niečo zistil, ale komunikovať vie iba so svojimi ministrami. Všeobecne každý úradník spraví to, čo mu šéf povie, ale komunikovať vie iba so šéfom alebo priamymi podriadenými.
V každej úlohe chce kráľ zistiť nejakú informáciu. Vymysli, ako to má urobiť, teda čo sa má spýtať a čo má povedať svojim podriadeným, aby zistil to, čo ho zaujíma.
Navyše to skús vymyslieť tak, aby kráľ zistil, čo chce vedieť, čo najefektívnejšie. Keď sa jeden úradník niečo pýta druhého, zaberie to nejaký čas, takže môže trvať dlho, kým sa konečne kráľ dozvie odpoveď. Snaž sa teda, aby bolo dokopy treba čo najmenej pýtaní.
a. Kráľ by chcel v prvom rade vedieť, koľko má vlastne úradníkov. Ako to má zistiť?
b. Kráľ by chcel niečo odkázať všetkým svojim úradníkom, ale kým sa k nim tento odkaz dostane, môže to celkom trvať, lebo odkaz musí prejsť cez viacero úradníkov medzi nimi. Kráľ by chcel vedieť, koľko bude musieť čakať, a teda by ho zaujímalo, ako ďaleko je od neho najvzdialenejší úradník (teda cez koľkých podriadených sa k nemu odkaz musí dostať). Ako to má zistiť?
c. Niekedy potrebuje úradník poslať správu inému úradníkovi. To funguje tak, že ju pošle svojmu šéfovi alebo podriadenému, ten ju pošle zas niekomu ďalšiemu, a tak ďalej, až kým sa správa nedostane k adresátovi.
Mohlo by nás teda zaujímať, ako ďaleko sú od seba nejakí dvaja úradníci, teda cez koľko aspoň ľudí musí prejsť správa, ktorú posiela jeden druhému.
Ako vie kráľ zistiť, ako ďaleko sú dvaja najvzdialenejší úradníci?
d. Do kráľovstva prišla vojna a aj úradníci sú v ohrození. Keď nejakého úradníka zajmú vojaci, tak jeho podriadení už nebudú vedieť komunikovať s jeho nadriadenými.
Povieme, že úradník $U$ je posol pre nejakú dvojicu iných úradníkov $A$ a $B$, keď na to, aby si $A$ a $B$ mohli poslať správu, musí tá správa prejsť aj cez úradníka $U$.
Kráľa by zaujímalo, ktorý úradník je posol pre najviac rôznych dvojíc. Ako to má zistiť?