- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Zadania 2. kola letnej časti 19. ročníka KSP
Milé deťúrence,
a sú tu zadania posledného kola KSP. Svoje riešenia nám posielajte najneskôr do 20. mája. Nezabudnite nám spolu s nimi poslať známky v hodnote 15,- Sk.
Ešte by sme vás radi upozornili, že 10. mája o 13:45 sa uskutoční už 4. ročník internetovej sútaže Internet Problem Solving Contest - IPSC. Ide o online programátorskú sútaž trojčlenných teamov trvajúcu 5 hodín. Všetka komunikácia prebiaha výhradne v angličtine prostredníctvom internetu. Na sútaž sa treba vopred registrovať. Všetky relevantné informácie vrátane minuloročných príkladov, ilustračných príkladov, pravidiel, technických informácií a registračných formulárov nájdete na ipsc.ksp.sk. Preto neváhajte a zapojte sa!
KSPáci
- Ohromný hazard
- O zaľúbenom princovi
- O pobodkovanej kružnici
- O výskumníčkach
- O čiernych krabičkách IV
1. Ohromný hazard
Bezdomovec Fero je starý hazardér. (Peniaze na hazard si zarába pouličným predajom Nota Bene.) Aj toť nedávno sa mu podarilo vyhrať v rulete zopár žetónov. Nie aby bol rád, že túto noc už konečne nemusí spať pod mostom, on sa radšej rozhodol skúsiť ešte štastie pri hracích automatoch.
Nedávno, neviem, či ste to už postrehli, zaviedli do kasín nové hracie automaty. Nó a Feró zamieríl rovnó k nim.(Toto je v pištíkovčine.) Fungujú veľmi jednoducho. Ak do nich vhodíte žetón s hodnotou X korún, tak z automatu vypadne X korún. Ak vhodíte ďalší žetón s hodnotu Y korún, tak vypadne z automatu Y korún. Navyše, ak prechdádzajúci vhodený žetón bol menšej hodnoty ako Y, tak vypadne ďalších Y-X korún. Podobne to funguje aj so všetkými ďalšími žetónmi.
Pochopiteľne Fero má ambície dotiahnuť to spod mosta pokiaľ možno čo najvyššie, preto by rád vyhral čo najviac.
Úloha
Pomôžte Ferovi! Fero ma na začiatku N žetónov v hodnotách Z1, Z2, ... ZN korún. Napíšte program, ktorý načíta tieto čísla, nájde a vypíše také poradie vhadzovania žetónov, aby Ferova výhra bola maximálna. Ak existuje takých poradí viacero, vypíšte ľubovoľné z nich.
Príklad
Vstup
N=5
7 8 1 3 2
Výstup
Jedno možné poradie, pri ktorom získa maximum, je: 2,8,1,3,7. Jeho výhra bude 33 korún.
2. O zaľúbenom princovi
Kde bolo, tam bolo, za siedmimi horami a siedmimi dolami, bolo raz jedno kráľovstvo. Teda, boli tam dve kráľovstvá. Vlastne, no, povedzme, že tam bolo N kráľovstiev, medzi ktorými viedli jednosmerné cesty. V jednom z nich žil princ, a keďže bol práve mier a princ nemohol ísť bojovať, neostalo mu nič iné ako sa zaľúbiť do princeznej. A keď sa už do nej zaľúbil, chcel ju požiadať o ruku. Lenže princezná býva v inom kráľovstve. Lenže zlý čarodej, ktorý chcel princeznú získať pre seba, zaklial každú cestu. Zakliatím získala každá cesta jedno celé (môže byť záporné!) číslo, ktoré udáva, o koľko človek zostarne, keď po nej prejde. Princovi je jedno, ako dlho bude trvať jeho cesta za princeznou, ale chcel by za ňou prísť čo najmladší, aby ho chcela. Zistite, aký najmladší môže prísť princ pred princeznú (teraz má princ 20 rokov).
Ani mágia zlého čarodeja nedokáže vyčarovať večnú mladosť, preto v celej zemi neexistuje okruh, po ktorom keby princ prešiel dookola (t.j. vrátil sa na miesto, odkiaľ po ňom začal ísť), tak by omladol. Navyše sa môže stať, že princ bude mať v priebehu alebo aj na konci záporný vek :).
Úloha
Na prvom riadku vstupu máte zadané čísla N a M. N je počet kráľovstiev, M je počet ciest vedúcich medzi kráľovstvami. Kráľovstvá sú označené číslami 1,2,...,N. Kráľovstvo číslo 1 je domovom princa, v kráľovstve s číslom 2 býva princezná. Na každom z nasledujúcich M riadkov vstupu je trojica čísel. Každá trojica určuje jednu cestu. Prvé číslo trojice určuje z ktorého kráľovstva cesta vychádza, druhé číslo je číslo kráľovstva, do ktorého cesta vedie a tretie číslo udáva o koľko rokov princ zostarne, keď po ceste prejde. Váš program má vypísať najnižší možný vek princa, keď príde za princeznou. Ak sa za princeznou nedá prísť, vyjadrí princovi svoj súcit.
Príklad
Vstup
4 6 1 4 -5 4 3 10 3 1 -2 1 3 2 4 2 2 3 2 -5
Výstup
Princ bude mať po prejdení cesty 17 rokov.
3. O pobodkovanej kružnici
Nebolo to tak dávno, keď si Santo robil úlohu z geometrie. Santo a Banto totiž momentálne hľadajú na Klondike zlato. Hladať zlato sa však dá iba cez deň, lebo v noci je v bani tma. Ono tma tam je aj cez deň, dokonca možno ešte väčšia ako v noci, ale v noci je tma aj mimo bane a Santo a Banto sa boja ísť domov po tme. Preto po večeroch nemajú čo robiť. Banto je lenivý od narodenia, jemu to až tak nevadí. On sa zabaví aj v krčme. Ale Santo je viac uvedomelý a štvalo by ho, keby štvrtinu svojho života (to je čas, kedy je vonku tma a človek nespí) presedel pri barovom pulte. Preto sa prihlásil na diaľkové štúdium a po večeroch rieši úlohy.
A sme naspäť pri tej geometrii. Kto hádal, iste uhádol, že išlo o jednu z úloh na ďiaľkové štúdium. Hm, hm, hm, ako by sa len dala vpísať kružnica do štvorca... Hm, hm... A dá sa to vôbec?' Tieto a podobné myšlienky behali Santovi hlavou asi štyri hodiny, potom sa zrazu objavil nápad spojiť protiľahlé vrcholy a vzápätí sa úloha vyriešila skoro sama. Od toľkej námahy skoro zaspal na stoličke, no nakoniec sa mu podarilo zvaliť sa na posteľ a zaspať tam.
Niekedy vtedy sa vrátil Banto z krčmy a celý veselý si pozrel Santov porysovaný zošit. Banto okrem iného aj rád kreslí, a preto na Santovej tak ťažko vpísanej kružnici vyznačil niekoľko bodov, ktoré mu veľmi pripomínali hviedičky mihajúce sa mu každý večer pred očami. Iste si viete predstaviť Santa, ako mu mizne úsmev z tváre, keď ráno objaví Banta zvaleného cez stoličku a svoju kružničku úplne pobodkovanú. Banto sa zanedlho prebral, no nebol ešte úplne fit. Začal mať blbé otázky typu "Čo je to trojuholník?", "Ako vyzerá rovnostranný trojuholník?", "A ako pravouhlý?", a pod. Predsa si niečo zo včera pamätal... Hneď na to uvidel svoje hviezdičky v Santovom zošite, čo ho inšpirovalo k otázkam: "A je tu nejaký pravouhlý trojuholník? A rovnostranný by sa nenašiel?". Teraz mal Santo taký pocit, že by vraždil a plakal zároveň. Prečo by vraždil, iste všetci tušíte (a je len Bantovo šťastie, že Santo nedržal v ruke sekeru). No a plakal by preto, lebo ani na jedinú otázku nevedel súvisle odpovedať. Preto by chcel poprosiť vás, či by ste mu aspoň s poslednými dvoma nepomohli.
Úloha
Na vstupe je dané číslo N (N>=3) nasledované N dvojicami čísel. Každá dvojica predstavuje súradnice bodu na jednotkovej kružnici (to je taká kružnica s polomerom 1 a stredom v bode [0,0]). Body sú na vstupe dané v poradí, ako sa nachádzajú na kružnici. To znamená, že keby sme prezerali kružnicu po obvode proti smeru hodinových ručičiek, pričom by začali sme v bode [1,0], natrafili by sme na jednotlivé body presne v takom poradí, ako sú na vstupe. Vašou úlohou je zistiť, či medzi bodmi existuje trojica bodov, ktoré tvoria vrcholy
a) pravouhlého trojuholníka
b) rovnostranného trojuholníka.
Príklad
Vstup
N=4
1.0 0.0 0.5 0.866 -1.0 0.0 0.5 -0.866
Výstup
Možno nájsť pravouhlý trojuholník.
Možno nájsť rovnostranný trojuholník.
4. O výskumníčkach
Potom, čo sa výskumníčke Janke podarilo dostať z laboratória, rozhodla sa, že pôjde skúmať niečo zaujímavejšie. Zavolala si kamarátku Janku II a vybrali sa spolu na severný pól skúmať polárneho medveďa Richarda. Cestou rozmýšľali, čo by tak na ňom vlastne mohli skúmať. Po tom čo zavrhli sociálne správanie (s tým už mali skúsenosti z minulosti), rozhodli sa pre genetiku. Zistia štruktúru jeho DNA.
Na severnom póle ale objavili hneď najväčšiu prekážku - zimu. Aby sa stále netriasli, vždy si Janky v prenosnom laboratóriu "nadýchali", až im bolo teplúčko. Ale beda! Občas sa im zarosil aj display ich elektrónkového mikroskopu a tak nemohli odčítať niektoré úseky DNA. Našťastie ale, ako správne výskumníčky, viedla každá z nich vlastný výskum a možno by spojením ich výsledkov predsa len mohli zistiť Richardovu DNA.
Úloha
Na vstupe sú dva reťazce zo znakov A, T, C, G, U, a * - výsledky pozorovaní oboch výskumníčiek. Hviezdička zodpovedá neprečítanému miestu - ľubovoľne dlhému reťazcu génov (aj prázdnemu). Vašou úlohou je napísať program, ktorý zistí najkratšiu postupnosť génov vyhovujúcu obidvom pozorovaniam.
Príklad
Vstup
1. reťazec: *CGAT*CCA*G*
2. reťazec: AT*ATACC*AG*
Výstup
ATCGATACCAG
5. O čiernych krabičkách IV
V kráľovstve pána Kráľa žije veľa podivných tvorov, ale najviac starostí majú s rozmazannou princeznou Milou. Včera si opäť zmyslela, že niečo chce a chce a chce. Chce sa na koči previesť cez všetky mestá otcovho kráľovstva, cez žiadne nie dvakrát a vrátiť sa späť na zámok. Radcovia dumajú, ale vydumať nevedia. Keby aspoň vedeli, či taká trase existuje... vybrali sa pre pomoc za dobrou vílou Amálkou.
"Teraz sa vám nemôžem venovať," odvetila dobrá víla milým hlasom, lebo práve pracovala na nebezpečnom pokuse s profesorom Indigom. "Zoberte si však túto čiernu krabičku. Dokáže odpovedať, či v ľubovolnom kráľovstve existuje cesta prechádzajúca polovicou miest."
Úloha
Na vstupe je počet miest N v kráľovstve. Ďalej nasleduje popis všetkých ciest, dvojích čisel ai bi. Každá dvojica hovorí, že medzi mestami ai a bi vedie cesta.
Máte k dispozícii čiernu skrinku, ktorej vždy keď dáte na vstup popis ľubovolného kráľovstva s N' mestami, ona vám v konštantnom čase odpovie, či sa v popísanom kráľovstve nachádza cesta prechádzajúca cez N' div 2 miest (počíta sa aj prvé a posledné mesto na ceste). Na nájdenej ceste sa žiadne mesto neopakuje. Formát popisu kráľovstva si môžete zvoliť.Príklad práce krabičky
Vstup
N'=7
cesty: (1,2) (1,3) (1,4) (1,5) (1,6) (1,7)
Výstup
áno
Vstup
N'=8
cesty: (1,2) (1,3) (1,4) (1,5) (6,5) (6,8) (7,8)
Výstup
nie
Vašou úlohou je zistiť, či v kráľovstve na vstupe existuje alebo neexistuje okružná cesta, ktorá začína a končí v meste 1, prechádza všetkými mestami a žiadne mesto (okrem mesta 1) nie je na nej dva alebo viackrát. Váš program má pracovať čo najrýchlejšie, pretože kráľovstvo je veľké.
Príklad vstupu a výstupu
Vstup
N=4
cesty: (1,2) (1,4) (2,3) (2,4)
Výstup
áno
Vstup
N=5
cesty: (1,2) (1,3) (2,3) (3,4) (3,5) (4,5)
Výstup
nie
(c) 12. Apríl 2001 webmaster
