- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Príklady 2. kola letnej časti 20. ročníka KSP
Milé deti,Školský rok sa nám pomaly chýli ku koncu, nás už trápia skúšky, niektorých z vás práve týrajú na maturách... a všetci spolu sa tešíme na prázdniny. Nebojte sa, nie je to už ďaleko. Už vás od prázdnin delí len jedna séria KSP. Tak hor sa do riešenia!
Svoje riešenia nám posielajte do 23. júna 2003 a nezabudnite priložiť známky v hodnote 15 Sk,-. Ešte by sme chceli upozorniť hlavne riešiteľov z GJH, že riešenia, ktoré sa ku nám nedostanú načas, nebudú opravené.
KSPáci
1. O doplnení postupnosti
(15 bodov)
Všetci určite poznáte úlohu z IQ-testu: Daných je prvých N členov postupnosti, doplňte ďalší. Už ste ich určite riešili toľko, že vás nudia. Dobre viete, že je niekoľko málo typov takýchto úloh a tie sa do omrzenia opakujú. Tak ste sa rozhodli napísať si program, ktorý ich bude vedieť riešiť za vás. Program by vlastne mal k daným číslam a1 až aN nájsť nejakú funkciu f takú, aby ai=f(i) a potom spočítať hodnotu f(n+1). Tým zbehlejším v matematike je jasné, že takých funkcií je nekonečne veľa. Preto by váš program mal predpokladať, že f je polynóm (Funkcia f(x) je polynóm, ak ju môžeme písať v tvare f(x)=p0 + p1x + ... + pnxn pre vhodné n a pi, pričom pn<>0. Číslo n voláme stupeň polynómu.) najmenšieho možného stupňa.
Úloha
Na vstupe je daný počet čísel N a N celých čísel a1, ..., aN. Nájdite vyššie uvedeným popisom určenú hodnotu aN+1.
Príklad
Vstup
N=4, postupnosť: 1 4 9 16
N=5, postupnosť: 7 7 7 7 7
N=4, postupnosť: 1 3 6 10
Výstup
25
7
15
2. Opäť o metre
(15 bodov)
Nebolo to ani tak ďaleko v budúcnosti, čo v Bratislave dostavali metro. Celý špás bol náramne drahý, deti pár rokov nedostávali vreckové, ich rodičia výplaty, chlieb bol na prídel, ale nakoniec bolo metro hotové. V meste sa nachádzalo niekoľko zástavok a medzi niektorými zástavkami viedlo dvojo koľajníc, po ktorých mohli chodiť súpravy. Ak medzi dvoma zastávkami viedli koľajnice, tak potom po jednej chodili vlakové súpravy tam (a nijako inakšie) a po druhej chodili späť (a nijako inakšie). Tak sa predišlo takmer všetkým možným nehodám.
O metro mali záujem dve spoločnosti: Dopravný podnik Bratislava a Klub (ne)Spokojných Pasažierov. Aby sa predišlo hádkam a sporom, vymyslelo mestské zastupiteľstvo nasledovné riešenie: Pre každú dvojicu zástavok, medzi ktorými viedli koľajnice, bude jedna spoločnosť zabezpečovať dopravu v jednom a druhá v druhom smere. Ďalšou podmienkou bolo, že žiadna spoločnosť nesmie prevádzkovať metro tak, aby sa iba použitím jej úsekov trate dalo voziť dookola (t.j. nasadnúť na nejakej zastávke na metro a po čase sa na ňu vrátiť späť).
Spoločnosti si rozdelili koľajnice a začali prevádzkovať metro. Neustále ponúkali rôzne zľavy, aby odlákali zákazníkov od konkurencie. Časom ceny klesli už tak, že samotné cestovanie bolo zadarmo. Aby spoločnosti ako-tak pokryli náklady, platilo sa už iba za to, keď človek prestúpil zo súpravy od jednej spoločnosti do súpravy od druhej spoločnosti. Tento poplatok bol vždy rovnaký a navyše pri prvom nastupovaní, ani pri poslednom vystupovaní sa neplatilo nič.
Mestom razom prebleskla fáma, že sa dá cestovať úplne zadarmo. Medzi niektorými miestami to šlo, ale nie medzi všetkými. V jedno krásne ráno sa Kleofáš veľmi ponáhlal na skúšku. Nutne musel zvoliť najkratšiu cestu, no chcel prestupovať čo najmenej, aby nemusel veľa platiť. Bol by veľmi rád, keby ste mu poradili.
Úloha
Na vstupe je daný počet zastávok N >= 2 a počet dvojíc zastávok M, medzi ktorými vedú koľajnice. Nasleduje popis M smerov, ktoré prevádzkuje KSP. Na i+1-vom riadku sú čísla ai, bi, ci, čo značí, že KSP prevádzkuje metro v smere zo zastávky ai do bi a trasa má dĺžku ci. (Samozrejme DPB prevádzkuje trasu rovnakej dĺžky z bi do ai.) Kleofáš nastupuje na zastávke 1 a škola je na zastávke N.
Nájdite takú najkratšiu trasu zo zastávky 1 do zastávky N, kde musí Kleofáš prestupovať najmenejkrát od jednej spoločnosti k druhej.
Príklad
Vstup
N=6, M=8
1 5 6 4 5 4 5 3 11 1 4 8 4 2 9 6 2 5 4 3 5 6 3 7
Výstup
Najkratšia cesta: 1 --> 4 --> 2 --> 6.
Kleofáš na nej musí prestúpiť 1 krát.
(Ešte prichádza do úvahy trasa cez zastávky 1 --> 5 --> 4 --> 3 --> 6, ale na tejto ceste by musel Kleofáš prestúpiť trikrát.)
3. O vyberaní mýta
(15 bodov)
V celom Rakúsko-Uhorsku sa kedysi dávno vyberalo mýto -- poplatok za vstup do mesta alebo prechod cez most. Napríklad od ľudí prichádzajúcich z Rače vyberali mýto na mýtnici na Račianskom mýte. Keď pred 150 rokmi postavili most cez Dunaj (v súčasnosti Starý most), tak tiež nezabudli postaviť na oboch jeho stranách mýtnice (Mimochodom, stoja tam dodnes.), kde vyberali mýto pre zmenu od Petržalčanov. Peniažky sa len tak sypali do štátnej kasy...
Predstavte si, že ste cisársky radca Františka Jozefa a máte mu poradiť, kde by sa mali postaviť mýtnice a vyberať mýto. Pochopiteľne bolo by mrhaním stavať mýtnice na tých miestach, ktoré sa dajú obísť inou cestou. Úloha je to teda neľahká.
Máte po ruke mapu cestnej siete krajiny pozostávajúcu pre jednoduchosť z križovatiek a ciest medzi nimi. Mýtnicu sa oplatí postaviť na také križovatky, ktoré sa nedajú obísť. Križovatka K sa nedá obísť, ak existujú dve iné križovatky A, B také, že ľubovoľná trasa medzi nimi prechádza cez K. (Ak niekto chce ísť z A do B, určite prejde mýtnicou K, čím zaručí istý zisk štátnej kase.)
Na vstupe je daný počet križovatiek N (očíslovaných 1,2,...,N) a počet ciest M medzi nimi. Ďalej nasleduje M dvojíc čísel križovatiek popisujúcich cesty; cesty sú obojsmerné a nepretínajúce seba ani iné cesty. Vypíšte všetky miesta, kde sa má postaviť mýtnica.
Príklad
Vstup
N=8, M=10
(1 2), (2 3), (3 1), (3 4), (4 5), (5 3), (5 6), (6 7), (7 8), (8 6)
Výstup
Mýtnice postaviť na križovatkách 3, 5 a 6.
(Ak chceme ísť z 1 do 4, tak musíme prejsť cez 3. Ak chceme ísť 4 do 6, tak musíme ísť cez 5. Ak chceme ísť z 5 do 7, tak musíme ísť cez 6.)
4. Ospalý čarodej
(15 bodov)
Život je plný stereotypov. Jedným z najklasickejších je starý čarodej. Dňom i nocou sa venuje výskumu mágie, ktorá je nad úrovňou nás – prostých ľudí. Je v podstate milý a príjemný, kým mu neprekážate, nič po ňom nechcete a nevyrušujete ho od práce. V opačnom prípade vie byť naozaj veľmi nepríjemný.
Žiť v jednom dome s takýmto čarodejom nie je žiadna radosť. Vždy keď si sadáte, musíte sa poriadne pozrieť kam, lebo napríklad prisadnutý bazilišok vie byť veľmi nepríjemný a ak rozsadnete pavúka, čarodeja naštvete, lebo určite práve potreboval nejakého živého. Po dome sa povaľuje neuveriteľná kopa rôznych kníh, zvitkov, fľaštičiek s rôznofarbnými tekutinami a ponožiek. A to už nehovorím o tom, čo sa stane, ak niektorú z fľaštičiek rozbijete alebo božechráň sa z nej napijete.
Dalan, Belsambarov tovariš, dnes oslavuje svoje sedemnáste narodeniny. Keď zoberieme do úvahy všetky spomínané nepríjemnosti, ktoré sa môžu človeku v takom dome pritrafiť, je to až prekvapivé. Náladu mu však dnes kazí nová nepríjemnosť, ktorá ho čaká. Belsambar totiž začal rozprávať zo sna. A čo je horšie, občas sa mu zo spánku podarí vykúzliť šváby. Dalan potom musí tráviť celé hodiny tým, že ich musí naháňať a zabíjať. Keby aspoň vedel, koľko ich je!
Úloha
Napíšte program, ktorý mu pomôže. Na vstup Daran zadá zaklínadlo, ktoré vyčaruje švába. Potom bude zadávať všetko čo Belsambar počas noci narozpráva (pozor, môže toho byť veľmi veľa!) Program by mal na konci vypísať, koľko švábov Belsambar vykúzlil. (Švába vykúzli vždy, keď dopovie zaklínadlo. Jednotlivé výskyty zaklínadla v mrmlaní sa môžu prekrývať.)
Príklad
Vstup
zaklínadlo: budsvabbud
reč:
uaaahskuskamikrofonubud svabbudnebudlabutsakras akrakspkspkspkspmusimri esitbudsvabbudsvabbudne dostanetejestblllllllll
Výstup
3
5. O celulárnych automatoch IV
(15 bodov)
Pripomeňme si, čím vás tento rok trápime. Ak si to pamätáte z predchádzajúcich sérií, môžete rovno preskočiť až k odseku "Úloha".
Celulárny automat je poskladaný z množstva rovnakých krabičiek. Každá krabička môže byť v jednom z konečne veľa stavov. Každú sekundu sa každá krabička pozrie na svoj stav a na stav okolitých krabičiek a podľa nich (a ničoho iného!) sa rozhodne, v akom stave odteraz bude. Všetky krabičky teda naraz zmenia svoje stavy na nové. Zmenu stavu krabičky v závislosti od získaných informácií vieme popísať predpisom, ktorý budeme volať prechodová funkcia. Táto funkcia je vlastne akýsi jednoduchý program, ktorý krabička vykonáva. Všetky krabičky budú vykonávať ten istý program.
Naďalej sa budeme zaoberať jednoduchou situáciou – naša sústava automatov bude tvorená N rovnakými automatmi, uloženými v jednom rade. Každý automat má teda 2 susedov, až na krajné dva, ktoré majú len jedného. Zavedieme špeciálny stav $ ktorý vidia krajné automaty ako stav ich chýbajúceho suseda. (Dohodnime sa, že automat nemôže nadobudnúť tento stav a teda sa tváriť, že tam nie je.)
Kvôli šetreniu miestom a zároveň lepšej prehľadnosti budeme časť prechodovej funkcie: "Ak môj ľavý sused je v stave U, ja som v stave V a môj pravý sused je v stave W, zmením stav na X" zapisovať zjednodušene UVW --> X. Stavy automatov v konkrétnej sekunde budeme zapisovať ako jeden reťazec, t.j. napr. zápis $A011AB$ znamená, že naša sústava má 6 automatov, najľavejší automat je v stave A, jeho sused je v stave 0, atď. Znaky $ predstavujú stavy, ktoré vidia krajné automaty. Tento zápis zdôrazňuje, že na prechodovú funkciu sa môžeme dívať ako na sadu prepisovacích pravidiel – každú sekundu si pre každý automat nájdeme to pravidlo prechodovej funkcie, ktoré "naň pasuje" a potom podľa týchto pravidiel všetkým automatom naraz zmeníme stavy.
Príklad
Nech sú na začiatku všetky automaty v stave 0, iba ľavý krajný v stave 2. Napíšme program, po ktorého skončení budú párne automaty v stave 0, nepárne v stave 1. Uvedomme si, že problém je v tom, že program musí fungovať bez ohľadu na to, koľko automatov budeme mať. Pritom žiaden automat nemá dosť pamäte na to, aby si pamätal svoje poradové číslo, lebo to môže byť ľubovoľne veľké.
Riešenie môže vyzerať nasledovne: stav 2 bude akýsi "signál", ktorý si budú automaty posielať doprava a bude "ofarbovať" automaty, po ktorých prechádza, striedavo 1 a 0.
V programe teda použijeme 3 stavy: 0, 1 a 2.
Prechodová funkcia bude vyzerať nasledovne:
$2x --> 1 pre x z množiny {0,$}, (prvý automat má mať stav 0)
20x --> 2 pre x z množiny {0,$}, (signál ide doprava)
x2y --> z pre x z množiny {0,1},
z=1-x, y z množiny {0,$}, (prišiel signál, zmením stav na opačný ako má sused)
x2$ --> z pre x z množiny {0,1}, z=1-x, (prišli sme na koniec)
xyz --> y pre všetky ostatné trojice stavov, (inak sa nič nedeje)
Ukážeme si výpočet našej sústavy na vstupe 20000 (t.j. 5 máme automatov):
$20000$ ==> $12000$ ==> $10200$ ==> $10120$ ==> $10102$ ==> $10101$
a v tomto stave už naša sústava zostane.
Úloha
Predstavme si, že každý automat je malý vojačik. Všetky sú v stave 0 (čakám) a prechodová funkcia je taká, že sa nič nedeje. V niektorom takte zmeníme ľavému krajnému stav na 1 (ideme strieľať). Chceme, aby o niekoľko (čo najmenej) taktov prešli všetky automaty naraz do stavu S (strieľam). Určte (konečnú!) množinu stavov automatu a napíšte prechodovú funkciu tak, aby všetci vojačici naraz vystrelili.
Nezabudnite, že pri písaní prechodovej funkcie neviete, koľko vašich automatov vedľa seba naskladáme. Sústava zložená z ľubovoľného počtu vašich automatov by mala fungovať podľa zadania. Ak sa vám úlohu nepodarí úplne vyriešiť, napíšte aspoň riešenie, ktoré bude fungovať v prípade, že počet vojačikov je mocnina dvoch.
Pri návrhu prechodovej funkcie vám môže (a nemusí) pomôcť program, simulujúci sústavu vašich automatov. Ak si aj takýto program napíšete, neposielajte nám ho. Ako riešenie stačí poriadne popísaná množina stavov a prechodová funkcia vášho automatu. Ak to pomôže prehľadnosti vášho riešenia, stavy nemusíte značiť iba písmenami, napr. L47' je skvelý názov pre stav.
(c) 26. máj 2003 webmaster
