- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Príklady 2. kola zimnej časti 22. ročníka KSP
Milí riešitelia!
Táto veta pravdivá je: KSP skrýva rôzne taje. Dávno každý vie, že riešit ho je kúzelné... A tak deti neváhajte, príklady nám posielajte. Termín je 5. január 2005, keď príde, do obálky ich vložte hneď. A nezabudnite na známky za 15 korún, nech dostanete od nás odozvu skorú.
KSPáci
1. Odvážny Marek
(15 bodov)
"Nie! Tá nie je ani omylom najlepšia," povedal Marek Mirkovi a zároveň dodal: "Stavím sa s tebou o mrežovník, že nájdem súvislú podpostupnosť, ktorú keď sčítam a z výsledku spravím absolútnu hodnotu, budem bližšie k 7 ako ty s tou tvojou."
Kedže Marek je strašná "lama" a nechce byť Mirkovi dlžný ďalší mrežovník (už teraz mu dlží dva), pomôžte mu a vyriešte úlohu za neho.
Úloha
Je daná postupnosť N celých čísel a kladné číslo T. Nájdite súvislú podpostupnosť takú, že keď označíme jej súčet S, bude rozdiel |T-|S|| najmenší možný.
Príklad
Vstup
N=13, T=12
postupnosť: 47 100 -1 -9 8 -7 6 -5 4 -3 2 -1 0
Výstup
-1 -9
2. Ojedinelý prípad
(15 bodov)
Neviem, či viete, ale Mirko je dosť ojedinelý prípad, on je totiž strašne lakomý (dokonca sa nepodelí ani s diskom). Ale aby si to o ňom jeho kamaráti nemysleli, rozhodol sa ich na svoje narodeniny pozvať do kina. Každý kamarát má požiadavky, koho musí pozvať s ním. Mirko by ich chcel pozvať čo najmenej (aby ušetril), ale chce, aby všetci pozvaní boli spokojní.
Úloha
Je daných N Mirkových kamarátov, a ku každému zoznam ľudí, ktorých chce, aby boli v kine s ním. Vypíšte, koho musí Mirko pozvať, tak aby s každým pozvaným pozval aj všetkých ľudí z jeho zoznamu, a zároveň aby bol počet pozvaných ľudí kladný (musí pozvať aspoň jedného človeka) a minimálny možný. Pre zjednodušenie sú mená nahradené číslami od 1 po N, a zoznamy sú zadané ako M usporiadných dvojíc (ai,bi), ktoré predstavujú, že človek ai chce v kine človeka bi.
Príklad
Vstup
N=6 M=7
(1, 2), (2, 1), (3, 4),
(4, 5), (5, 6), (6, 4), (2, 3)
Výstup
4 5 6
3. OEIN GONIATH
(15 bodov)
Temná noc. Záblesk na oblohe. Len mohutný dub sa čnie do noci. Majestátne konáre sa kolíšu vo vetre. Ďalši záblesk. Oči pútnika padnú na predmet pod stromom. Tma. Pútnik podíde bližšie. Vyčkáva, čo bude ďalej. O chvíľu sa rozhodne podísť ešte bližšie k nádhernému starému stromu. Konečne si začína uvedomovať zvuk hromu a hučanie vetra. A v tom aj niečo iné. Nejaké šuchotanie. Ďalší záblesk. Pútnik zbadá, čo leží pod stromom. Je to stará kniha. Listy sú celkom zožltnuté, ale vyžaruje z nej rovnaká sila ako zo samotného dubu. Zrazu ho premkne zvláštny pocit. Niečo ho núti ísť ku knihe napriek tomu, že má obrovský strach. Pútnikovi sa chvejú ruky. Nakláňa sa k nej. Vtom zo stromu vyletia havrany, na krídlach nesúc zvuk hromu, čo zaznel z diaľky. Pútnik si to však už nevšíma a otvára knihu. Je v nej strašné tajomstvo. Pravda o živote a smrti...
"ETH GO DIVADH!", takto káže kniha. "Priveď druidov k čiare života, LOINE TÁ CAILIDH. Nech každý z nich postaví sa na ňu a silami štyrmi strom svoj povolá. Silou zeme, SORGAEIL TAAMH, silou vody, SORGAEIL UISCE, silou ohňa, SORGAEIL TEINE a silou vzduchu, SORGAEIL ANAIL. Sily štyri sú medzi druidom s stromom jeho, len kým strom jeho voľnú cestu rásť má, OTEITH AD TA RAHM. Odpovedz človek, DREAT REFOIBH, zo stromov ktoré až do diaľneho neba porastú a naopak, druidov ktorých sily štyri opustia. Odpovedz dobre a večný život, WICCA A TÚ ARGAN, bude ti daný. Zmýľ sa však a v muky pekelné uvedieš sa navždy!"
Úloha
Na vstupe je zadaný počet druidov N. Všetci stoja na x-ovej osi a každy má zadanú svoju pozíciu a smer, ktorým rastie jeho strom. Smer je zadaný v stupňoch proti smeru hodinových ručičiek od kladnej x-ovej osi. Všetky stromy rastú rovnakou rýchlosťou. Keď strom narazí do iného stromu, jeho druida opustí sila a strom prestane rásť. Ak sa zrazia vrcholky dvoch stromov, ďalej porastie ten, ktorý vyrastá zo zeme viac vľavo. Stromy sú očíslované od 1 do N v poradí, v akom sú uvedené na vstupe. Vypíšte čísla stromov, ktoré porastú až do neba, t.j. nikdy neprestanú rásť.
Príklad
Vstup
N=6
(x=0, smer=105), (x=40, smer=40),
(x=20, smer=30), (x=10, smer=75),
(x=30, smer=135), (x=50, smer=75)
Výstup
1 4 6
4. O 47. hyperpriestorovej dimenzii
(15 bodov)
V 47. hyperpriestorovej dimenzii práve dokončili cestnú sieť, ktorú budovali veľmi veľa rokov. Kedysi dávno boli všetky mestá tejto dimenzie od seba izolované. Všemocný Pán dimenzie vtedy rozhodol, že každý rok dá postaviť práve jednu cestu. Navyše táto nová cesta musí pripojiť k existujúcej cestnej sieti nové mesto. A keďže v 47. hyperpriestorovej dimenzii platia celkom odlišné zákony, niektoré cesty majú zápornú dĺžku.
Teraz sú už všetky mestá spojené, no ľudia aj tak nie sú spokojní. Cesta medzi niektorými mestami totiž trvá veľmi dlho. Pán dimenzie sa rozhodol, že odteraz budú nové cesty spájať tie mestá, medzi ktorými trvá cesta najdlhšie
Úloha
Je daná cestná sieť s N mestami a N-1 cestami. Najprv je na vstupe prirodzené číslo N, potom N-1 ciest. Každá cesta je určená tromi číslami a, b, l, kde a, b je dvojica miest, medzi ktorými vedie cesta a l je dĺžka tejto cesty. Dĺžka cesty môže byť aj záporná. Vašou úlohou je nájsť dĺžku najdlhšej trasy medzi dvoma mestami.
Príklad
Vstup
N=6
1 2 4
2 3 2
2 4 -3
4 6 8
4 5 0
Výstup
9
(Trasa 1 -- 2 -- 4 -- 6.)
5. Otvor sa, sezam!
(15+ bodov)
Kdesi v ďalekom Oriente odohral sa raz nasledujúci príbeh: Jedného slnečného dňa vydal sa Alibaba na trh. Ako sa tak prechádza po trhu, zrazu mu malý zlodej uchmatne peňaženku a poďho kade ľahšie! Alibaba neváhal a bežal za ním. No zlodej vybehol z mesta a vbehol do akejsi jaskyne. Alibaba vbehol za ním, no po pár metroch sa chodba delila na dve vetvy. Čo mal chudák robiť, jednu z nich si vybral a vydal sa ňou. Chodba po chvíli končila a zlodeja nikde.
Na druhý deň zamieril Alibaba opäť na trh -- kúpiť si novú peňaženku. No len čo si ju kúpil, už mu s ňou známy zlodej utekal preč. Tentokrát si Alibaba v jaskyni vybral druhú cestu, no aj tá končila stenou a zlodeja ani teraz nechytil.
Keď takto Alibaba prišiel už o šiestu peňaženku, začalo mu to vŕtať v hlave. Vrátil sa do jaskyne a poriadne ju preskúmal. Nakreslená je na obrázku.
Ako tak stál na konci jednej z chodieb, zrazu začul dupot nôh. A len čo sa stihol skryť za neďaleký výčnelok skaly, pribehol jeho starý známy. No to, že chodba končí, ho nijako nezastavilo. Vykríkol "otvor sa, sezam" -- a div sa svete, stena sa otvorila a zlodej spokojne prebehol do druhej chodby.
Alibaba sa zamyslel. Z tohto by sa predsa dali vytĺcť slušné peniaze! Na druhý deň už volal do televízie, že vie prechádzať cez steny. Do hodiny stál pred jaskyňou celý štáb. Jaskyňu dôkladne preskúmali a mohlo sa začať s prechádzaním cez stenu. No Alibaba nechcel, aby niekto videl, ako to robí. Preto navrhol nasledujúci postup:
"Ja vôjdem do jaskyne a zaleziem do jednej z tých dvoch chodieb. Chvíľu po mne prídete vy s kamerou, stanete si na rázcestie a zakričíte, z ktorej strany mám prísť. A ja z nej naozaj prídem."
Ako povedal, tak spravili. A keď celý tento pokus zopakovali tridsaťkrát a zakaždým Alibaba vyšiel zo správnej strany, štáb žasol. Toto bola bomba, ktorá pôjde do televíznych novín.
Tu by náš príbeh mohol končiť... Nebyť toho, že sa o tom celom dozvedeli dvaja zamestnanci konkurenčnej televízie. A tí si povedali: Veď na tom predsa nič nie je. Spravíme aj my také pokusy, celé to natočíme a v štúdiu potom vystriháme tie pokusy, ktoré sa nepodarili. Ako si povedali, tak spravili. A v ten večer obe televízie odvysielali na chlp podobné príspevky. A z divákov nik neuveril, že Alibaba naozaj vedel prechádzať cez steny. The end.
To, čo práve predviedol Alibaba, bol takzvaný bezznalostný dôkaz. Dokázal presvedčiť štáb, že prechádza cez steny, lebo odpovedal na ich výzvy -- ale pritom sa nik nedozvedel nič o tom, ako to vlastne robí.
Formálne, bezznalostný dôkaz je postup komunikácie medzi dvomi stranami. Jeden z nich (P -- Paľo Prover) chce druhému (V -- Vlado Verifier) dokázať platnosť nejakého, väčšinou matematického, tvrdenia -- ale nechce prezradiť vôbec nič iné. Bezznalostný dôkaz musí mať tri vlastnosti:
- Funkčnosť: Ak tvrdenie platí a P dodržuje dohodnutý postup, V mu uverí.
- Správnosť: Ak tvrdenie neplatí, podvodník tváriaci sa ako P V (skoro nikdy) nepresvedčí, aj keby podvádzal a nedodržiaval dohodnutý postup.
- Bezznalostnosť: Ak tvrdenie platí, V (ani nik počúvajúci komunikáciu) sa o ňom nedozvie nič iné.
Načo sú takéto bezznalostné dôkazy dobré? Uveďme jeden príklad za všetky: Prihlasujete sa na vzdialený počítač. Aby vás "pustil dnu", musíte ho presvedčiť, že poznáte heslo. Ale nechcete mu toto heslo jednoducho povedať -- čo, ak vás niekto odpočúva? To, čo potrebujete, je práve bezznalostný dôkaz. Počítač na druhom konci kábla presvedčíte, že heslo poznáte, ale nik iný sa o vašom hesle nesmie vôbec nič dozvedieť.
Ukážme si príklad serióznejšieho dôkazu ako bol ten Alibabov. Paľo má veľký graf G (s N vrcholmi, očíslovanými od 1 do N), ktorý si kedysi zostrojil a vďaka tomu pozná jednu hamiltonovskú kružnicu v tomto grafe. (Hamiltonovská kružnica je kružnica prechádzajúca cez všetky vrcholy, cez každý práve raz. Nie je známy algoritmus, ktorý by v polynomiálnom čase zistil, či daný graf takúto kružnicu obsahuje.) Chcel by Vladovi dokázať, že v grafe G sa takáto kružnica nachádza -- ale zároveň chce, aby zostal jediný, kto ju pozná.
Čo ale má Paľo robiť? Zjavne nemôže Vladovi kružnicu len tak ukázať. Riešenie je napríklad nasledujúce:
Paľo náhodne označí vrcholy svojho grafu číslami od N+1 do 2N. Do jedného súboru spíše
priradenie nových čísel starým. Teraz pre každú hranu zostrojí súbor, ktorý bude obsahovať nové
čísla jej vrcholov. Každý z týchto súborov zašifruje iným heslom a všetky ich
zverejní.
Vlado si teraz môže vybrať jednu z dvoch možností:
(Podobne ako keď si kameraman volil, odkiaľ má Alibaba vyjsť.)
- Chce vidieť, že Paľo naozaj zverejnil to, čo mal. Vtedy mu Paľo prezradí všetky heslá, Vlado si dešifruje súbory a skontroluje, že je to naozaj graf G.
- Chce vidieť hamiltonovskú kružnicu. Vtedy mu Paľo prezradí heslá len pre hrany, ktoré ju tvoria a Vlado si overí, že naozaj ide o kružnicu s N vrcholmi.
Toto celé opakujú, kým Vlado nie je presvedčený, povedzme tridsaťkrát. Funkčnosť tohto postupu je evidentná -- Paľo Vlada presvedčí.
Ako je to so správnosťou? Predstavme si, že Peter (Paľovo zlé dvojča), chce Vlada presvedčiť, že pozná hamiltonovskú kružnicu v G, hoci to nie je pravda. V každom kole má najviac 50% šancu, že Vlada oklame -- buď správne vyrobí zašifrované súbory (ale nepozná kružnicu), alebo vyrobí iný graf, v ktorom kružnicu pozná. Po 30 kolách je ale šanca, že stále Vlada oklamal, už len 2-30.
A bezznalostnosť? Tu si pomôžeme argumentom, ktorý sa bude podobať na to, čo spravila konkurenčná televízia. Predstavme si, že by si nezávislý pozorovatel N zapisoval všetko, čo si P a V pošlú. Dostane takto postupnosť trojíc: (Paľom zverejnené súbory, Vladova voľba, Paľova odpoveď). My však bez akýchkoľvek vedomostí o hamiltonovskej kružnici v G vieme vygenerovať postupnosť trojíc, ktorá bude tejto na nerozoznanie podobná. Preto celá komunikácia, ktorá medzi nimi prebehla, neobsahuje žiadne informácie o našej kružnici.
Úloha
- Poriadne napíšte, ako by sme takúto postupnosť generovali.
- Paľo má dva grafy a chce dokázať, že nie sú izomorfné. Navrhnite bezznalostný dôkaz a stručne zdôvodnite, že má požadované vlastnosti.
- Paľo má dva grafy a chce dokázať, že sú izomorfné. Navrhnite bezznalostný dôkaz a stručne zdôvodnite, že má požadované vlastnosti.
V úlohách b a c predpokladajte, že Paľove výpočty môžu trvať ľubovoľne dlho (t.j. vie
skúšať všetky možnosti), ale Vlado má k dispozícii len polynomiálny čas od veľkosti grafov
(t.j. jeho výpočty musia byť efektívne).
(V súčasnosti nevieme efektívne rozhodnúť, či sú dané dva grafy izomorfné.)
Hint k úlohe b: Ako by ste dokázali farboslepému človeku, že dve kartičky sú rôznych farieb?
© KSP, 28. november 2004
