- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Priklady 1. kola
Mili nasi riesitelia,
vitame Vas pri rieseni noveho rocnika KSP. Dufame, ze aj tento rok sa
Vam nase ulohy budu pacit a ze sa do sutaze zapojite v hojnom pocte.
Riesenia prveho kola nam posielajte do
1. O d'Artagnanovi
Ked mlady d'Artagnan dovrsil osemnasty rok zivota, rozhodol sa, ze sa vyda do Pariza a stane sa musketierom. Dostat sa do Pariza vsak v tej dobe nebolo vobec jednoduche. Jedinou rozumnou moznostou bolo vydat sa po kralovskych cestach, spajajucich jednotlive mesta. Kazda cesta zacina aj konci mohutnou mestskou branou. Problem je, ze kazdu mestsku branu strazia bud kralovi musketieri alebo kardinalovi gardisti a znacia si vsetkych, co prisli do mesta. Preto ked clovek prisiel do cudzieho mesta branou strazenou musketiermi, musel z neho aj odist niektorou branou strazenou musketiermi - gardisti ho nemaju na zozname a dali by ho zavriet. A naopak, ak prisiel branou strazenou gardistami, musel nejakou takou aj odist. Navyse sa vie, ze medzi gardistami a musketiermi vladne nepriatelstvo, preto ak branu na jednom konci cesty strazia jedni, na druhom konci ju urcite strazia druhi. Necudo, ze d'Artagnan uz hodiny sedi nad mapou Francuzska a rozmysla, ako sa v tejto situacii co najrychlejsie dostat do Pariza. (Z rodneho mesta moze d'Artagnan odist hociktorou branou.)Uloha: Vo Francuzsku je N miest cislovanych od 1 po N. Pariz ma cislo 1, d'Artagnanove rodisko ma cislo N. Medzi mestami vedie M ciest. Vsetky cesty su obojsmerne. O kazdej ceste vieme cislo jej zaciatocneho a koncoveho mesta, jej dlzku ako aj to, aki vojaci strazia jej zaciatok. (M - musketieri, G - gardisti. Koniec pochopitelne strazia ti druhi.) Napiste program, ktory nacita pocet miest N, pocet ciest M a informacie o jednotlivych cestach a vypise dlzku najkratsej trasy z d'Artagnanovho rodiska do Pariza za danych podmienok.
Priklad:
Vstup:
N=5, M=7
cesty:
1 2 3 M 1 4 4 G 1 3 2 G 2 5 3 G 2 4 10 M 5 4 1 G 4 3 1 M
Vystup:
Najkratsia cesta ma dlzku 5.(Je to cesta 5 --> 4 --> 1.)
2. Dopravny Podnik Mesta Bratislavy
Jedneho krasneho dna sa rozhodli Janko a Marienka so svojimi deturencami a niekolkymi jazvecikmi ist do hlavneho mesta na vylet. Prisli, ako inak, na hlavnu stanicu a teraz cakaju na zastavke autobusu. Uz asi stvrthodinu hladia do automatu na listky a spekuluju, aky listok kupit. Janko vravi: "Ja by som kupil jeden zlavneny listok + pes, jeden cely a jeden cely + pes." "To je hlupost!" vravi Marienka. "Bolo by to zbytocne je drahe, lepsi by bol jeden cely+zlavneny+pes..." Ich drahe deturence na nich nechapavo hladia. Aj by svojim rodicom poradili, ale este nevedia hovorit. Preto im musite pomoct vy.Uloha: Napiste program, ktory nacita cisla A, B, C a N. Dalej nacita N typov cestovnych listkov, pricom kazdy typ ma tvar: "X dospelych + Y deti + Z psov za cenu P korun.'' Vas program ma vypisat, aku najmensiu cenu musi zaplatit za listky A dospelych, B deti a C psov. (Cestujuci si mozu kupit listky aj pre viac ludi alebo psov, ak to bude stat menej.)
Priklad:
Vstup:
A=2 B=3 C=2 N=6 1 0 0 10 0 1 0 5 0 0 1 10 1 0 1 19 0 1 1 14 1 1 1 23Vystup:
51(Su to listky za 23+23+5 korun.)
3. O spartakiade
Iste viete, ze kedysi sa pravidelne usporiadavala spartakiada. V rok jej konania sa na vsetkych skolach na telesnej vychove cvicievali rozne choreograficke prvky a najlepsi z najlepsich ziakov potom predvadzali svoje umenie pred ocami pritomnych aj televiznych divakov na Prazskom Strahove. Obcas to ale uplne nevyslo a po niektorom narocnom prvku sa cvicenci ocitli vo formacii, v ktorej povodne vobec nemali byt. Nastastie boli vzdy na zemi v pravidelnych vzdialenostiach nakreslene kruzky, podla ktorych sa dalo orientovat. Kazdy z cvicencov vtedy dobehol na najblizsi neobsadeny kruzok a pokracoval v cviceni. Najvacsi problem vsak mali organizatori so zaverom, ked sa vsetci zucastneni mali postavit vedla seba a poklonit sa. Vtedy ich to nenapadlo, ale dnes by s velkou nadejou cakali na vase programy.Uloha: Napiste program, ktory nacita pocet cvicencov N a pre kazdeho cvicenca suradnice kruzku, na ktorom stoji. Kruzky su umiestnene na vsetkych miestach s celocislenymi suradnicami. Vas program by mal vypisat pocet presunov, ktore su potrebne k tomu, aby vsetci cvicenci stali na kruzkoch s rovnakou y-ovou suradnicou a neboli medzi nimi neobsadene kruzky (t.j. x-ove suradnice cvicencov budu x, x+1, ... , x+N-1). Tento pocet ma byt najmensi mozny. Cvicenci sa mozu presuvat len z kruzku na kruzok a to tak, ze prave jedna zo suradnic noveho kruzku sa od prislusnej predoslej suradnice lisi presne o 1 (teda mozu ist na kruzok vlavo, vpravo, dopredu alebo dozadu). V ziadnom momente presuvania by na jednom kruzku nemal stat viac ako jeden clovek.
Priklad:
Vstup:
N = 5
Suradnice cvicencov:
(1,2), (2,2), (1,3), (3,-2), (3,3)Vystup:
Minimalny pocet presunov: 8
(Cvicenec so suradnicami (1,3) sa presunie na (0,3) a odtial na (0,2), cvicenec z pozicie (3,-2) sa presuva cez suradnice (3,-1), (3,0), (3,1) na (3,2) a cvicenec z pozicie (3,3) sa presunie cez (4,3) na (4,2).)
4. O vekslakoch
Je take miesto, kde ludia nakupuju peniaze za peniaze, marky za dolare, koruny za jeny, jeny za franky, libry za drachmy a vsakovake ine za vsakovakejsie insie. Mota sa tam mnoho pochybnych existencii, ktore sleduju iba svoje male, mnohokrat iracionalne ciele. Volaju ich vekslaci. Ked ma clovek stastie a dostatok informacii, moze prist na takomto mieste k slusnemu majetku tak, ze si donesie peniaze v nejakej mene, vymiena ich, vymiena, az ma opat peniaze v tej istej mene, ale je ich viac. To sa nie vzdy da dosiahnut.Uloha: Zistite, ci sa to da dosiahnut, ak mate dany zoznam kurzov, za ktore vekslaci menia peniaze. Ak sa to da, tak uvedte aj postupnost vymen s prislusnymi kurzami. Predpokladajte, ze mozete presne zamenit lubovolne mnozstvo danej meny. Uvedomte si vsak, ze ak vekslak meni koruny na dolare, nemusi to robit naopak v rovnakom kurze.
Priklad:
Vstup:
SKK 44.23 na USD 1 USD 1.3 na GBP 1.08 GBP 1.18 na SKK 65.993 USD 0.02 na SKK 1 SKK 50 na USD 1Vystup:
ano: SKK 44.23 na SKK 50(SKK 44.23 zamenime za USD v kurze 44.23:1, potom USD na SKK v kurze 0.02:1)
5. Hra s pesiakmi
Za starych dobrych cias travili Janko s Marienkou vecery hranim hry Boxes. Ta ich uz vsak davno omrzela, tak teraz skusaju vselijake nove hry, napriklad hru s pesiakmi. Tato hra sa hra na sachovnici s m riadkami a n stlpcami. Jeden hrac ma n bielych pesiakov a druhy hrac ma n ciernych pesiakov. Na zaciatku hry su biele figurky rozostavene v spodnom riadku sachovnice a cierne v hornom. Hrac, ktory je na tahu, moze potiahnut jednou zo svojich figurok o lubovolny pocet policok smerom dolu alebo hore, pricom nesmie preskocit superovu figurku ani vyjst za okraj sachovnice. Hraci sa pri tahoch striedaju, pricom zacina hrac s bielymi fugurkami. Prehrava hrac, ktory uz nemoze urobit ziadny tah.Uloha: a) Napiste program, ktory bude hrat tuto hru proti Marienke, ked na nu Janko nema cas. Program najprv nacita n a m a spyta sa uzivatela, aku farbu figurok chce mat. Potom vas program striedavo taha a pyta si tah od uzivatela. Sustredte sa na to, aby vas program hral hru co najlepsie.
b) Marienka si pamata mnoho rozohranych hier, ktore by chcela dohrat. Napiste preto program, ktory nacita n, m, farbu uzivatelovych figurok a farbu figurok hraca, ktory je prave na tahu. Potom nacita situaciu hry (t.j. pre kazdy stlpec sachovnice poziciu bieleho a cierneho pesiaka) a dohra tuto hru proti uzivatelovi. Opat sa sustredte na to, aby vas program hral hru co najlepsie.
Priklad:
Nech napr. m=5 a n=4.
|
|
| obr. 1 | obr.2 |
1999, Organizatori KSP