- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Priklady 4.kola (2. kola letnej casti) 18.rocnika KSP
Mile deturence,
a su tu zadania posledneho kola KSP. Svoje riesenia nam posielajte najneskor do 7. maja. Nezabudnite nam spolu s nimi poslat znamky v hodnote 15,- Sk.
Este by sme vas radi upozornili, ze 18. maja o 13:45 sa uskutocni uz 3. rocnik internetovej sutaze Internet Problem Solving Contest - IPSC. Ide o online programatorsku sutaz trojclennych teamov trvajucu 5 hodin. Vsetka komunikacia prebiaha vyhradne v anglictine prostrednictvom internetu. Na sutaz sa treba vopred registrovat. Vsetky relevantne informacie vratane minulorocnych prikladov, ilustracnych prikladov, pravidiel, technickych informacii a registracnych formularov najdete na ipsc.ksp.sk. Preto nevahajte a zapojte sa!
KSPaci
1. O chemickych zluceninach
Sepro studuje za biochemika. Bude raz z neho taky velky chemik, ze to tu vsetko istotne vyhodi do vzuchu. Ale skor to tu asi vsetko zamori biotoxinmi. Kym sa tak vsak stane, musi Sepro este vela zincice vypit, vela klobas pojest a hlavne sa toho vela naucit.
Momentalne vsak sedi v skole a studuje biomolekuly. Pred sebou ma chemicku skladacku a snazi sa poskladat molekuly kyanidu draselneho, trinitrotoluenu, tripletu mitochondrialnej deoxyribonukleovej kyseliny a mnohych inych.
Skladacka sa sklada z vela guliciek s nozickami reprezentujucich atomy a vela rovnych tenkych dutych rurok rozmanitych dlzok reprezentujucich chemicke vazby. Ak maju byt dva atomy spojene chemickou vazbou, tak staci zobrat prislusne gulicky a nastoknut rurku na ich nozicky. Musite si vsak dat pozor aby ste rurku neohybali, lebo by sa mohla zlomit a hlavne musite vediet ako rozmiestnit atomy v priestore tak, aby sa ziadne dve vazby nekrizili.
Seprovi sa vsak nejako ruky pletu, oci krizia, skratka mu to akosi nejde. Zislo by sa mu trocha pomoct.
Uloha
Je dana molekula skladajuca z N atomov a M chemickych vazieb. Atomy su ocislovane celymi cislami od 1 po N. Vazby su zadane dvoma cislami atomov, ktore spajaju. Vasou ulohou je napisat program, ktory rozmiestni vsetkych N atomov do priestoru, t.j. urci kazdemu atomu jeho suradnice x,y,z v priestore tak, aby sa ziadne dve vazby nekrizili.
Priklad
Vstup
N=5, M=10
Vazby:
1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
Vystup
1. atom: (0,0,0)
2. atom: (2,0,0)
3. atom: (0,2,0)
4. atom: (2,2,1)
5. atom: (2,2,-1)
2. O neprijemnostiach
Kym dostava nami napisany program len male vstupy, je vsetko v pohode. Horsie je, ked dostaneme vacsi vstup. U pomalsich programov sa uz casto ani vysledku dozit nemusime. No a neprijemnosti zacinaju, ked je vstup taky velky, ze sa nam naraz ani len do pamate nezmesti. Ako napriklad teraz...
Uloha
V subore mame cislo N a za nim po riadkoch ulozene pole NxN celych cisel. Napiste program, ktory ulozi do vystupneho suboru toto pole preklopene podla osi y=x. (Pre skusenejsich: cize ked to pole berieme ako maticu, treba napisat program, ktory ju transponuje.) Matica moze byt taka velka, ze nielenze nam nevojde do pamate cela, dokonca nam do pamate nemusi vojst ani cely jej riadok. Zato na disku je miesta dost a mozete pouzivat pomocne subory.
Priklad
Vstup
N=4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Vystup
1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16
3. O elixiroch
Zas je tu neporiadok. Ale aky!! Zoja, lesna vila, je zufala. Zly skriatok jej pocarbal steny, rozburdal postielku a - povazte sami - zablatil saty. Najhorsie ale je, ze jej poprelieval zazracne flasticky. Zoja mala kopu flasticiek a v kazdej z nich mala povodne rannu rosu, vceli med alebo mesacny svit. Skriatok si dal zalezat, a tak sa teraz v kazdej flasticke nachadzaju vsetky tri substancie v nejakom pomere. Zoja by z nich potrebovala namiesat liecivy elixir, lenze v sucasnej situacii je to uloha bez vypoctovej techniky (a vasej pomoci) takmer neriesitelna.
Uloha
Na vstupe je pocet flasticiek N. V kazdej z nich sa nachadza urcite (nenulove) mnozstvo kazdej zlozky. Pre kazdu z nich mame na vstupe tri cisla, udavajuce pomer objemov jednotlivych zloziek. (Teda 3 2 4 znamena, ze vo flasticke su 3 diely rosy, 2 medu a 4 mesacneho svitu, alebo este inymi slovami: nech si z tejto flasticky odlejeme, kolko chceme, urcite tam bude napr. dvakrat viac mesacneho svitu ako medu). Nakoniec su na vstupe tri cisla, udavajuce pomer objemov zloziek v liecivom elixire.
Vasou ulohou je napisat program, ktory zisti, ci sa z roztokov vo flastickach da namiesat liecivy elixir a ak ano, tak v akom pomere treba obsahy jednotlivych flasticiek zmiesat.
Priklad
Vstup
N=3
1 2 5 9 3 5 2 2 1 6 4 5
Vystup
1. flaska: 2 diely
2. flaska: 2 diely
3. flaska: 5 dielov
Vstup
N=3
1 2 3 4 5 6 7 8 9 1 1 1
Vystup
Zoja ma smolu.
4. O novom probleme v Chile
Ako vsetci iste viete, v Chile maju s dopravou nemale problemy. Cestna siet totiz vyzera tak, ze vsetky mesta lezia na priamke a priamou cestou su spojene vzdy len susedne dve. Mesta su ocislovane od 1 po N v poradi, v akom lezia na priamke. Z mesta 1 do mesta N chodi z casu na cas autobus, ktory stoji v kazdom meste medzi nimi. V kazdom meste sa da nastupit aj vystupit a vie sa, kolko stoji listok z kazdeho mesta do kazdeho s vyssim cislom. Pocas cesty mozeme na niektorych zastavkach vystupit, nastupit a kupit si novy listok z mesta, v ktorom prave sme.
Toto je dobre znama situacia. Ved niektori z vas uz pomahali cestujucim najst, ako sa da najlacnejsie dostat z mesta 1 do mesta N. Juana Carlosa vsak vcera napadla prefikana myslienka. Nikde nie je povedane, ze musi mat pocas celej cesty pri sebe vzdy prave jeden listok. Staci mu, ked ma aspon jeden. Ak pride revizor, len vyberie lubovolny platny a ukaze mu ho. A da sa na tom usetrit. Ved napriklad z Puerta Montt je to do Santiaga lacnejsie ako z Valdivie, ktora lezi po ceste...
Uloha
Pomozte Juanovi usetrit a napiste program, ktory nacita pocet miest N v Chile, cenu listka medzi kazdymi dvoma mestami i, j, i<j a zisti, ako najlacnejsie sa da za takychto podmienok dostat z mesta 1 do mesta N.
Priklad
Vstup
N=4
A[1,2]=7 A[1,3]=2 A[2,3]=6 A[1,4]=10 A[2,4]=3 A[3,4]=9
Vystup
najlacnejsie sa da dostat za 5 korun - kupi si listky 1-3 a 2-4.
5. O Santolande IV
Najprv si znovu popiseme Santov uzasny vynalez - rumove jaskyne. Taka rumova jaskyna pozostava z N komor ocislovanych 1 az N. Medzi niektorymi dvojicami komor vedu jednosmerne tunely, pricom kazdy tunel je pri vchode oznaceny nejakym znakom (pismenom alebo cislicou). Medzi dvojicou komor moze viest viacero tunelov a z jednej komory moze vychadzat viacero tunelov oznacenych tym istym znakom.
Komora cislo 1 je startova komora. Niektore komory su oznacene ako cielove komory (cielova komora sa pozna podla toho, ze je v nej ukryta flasa rumu).
Zlatokop, ktory chce vojst do rumovej jaskyne, dostane od Santa papierik s postupnostou znakov. Zlatokop zacina put v komore 1 a v kazdom kroku musi prejst tunelom oznacenym rovnakym znakom, ako je prislusny znak na papieriku (v i-tom kroku musi pouzit tunel oznaceny i-tym znakom). Ak z komory vychadza viacero tunelov oznacenych tym spravnym znakom, moze si vybrat lubovolny z nich. Ak z komory nevychadza ani jeden tunel na dany znak, zlatokop ma smolu a s dlhym nosom sa musi pobrat domov. Ak sa mu vsak podarilo vycerpat vsetky znaky z papierika, moze v komore, v ktorej sa prave nachadza, vyhladat flasu rumu. V cielovej komore sa mu to spravidla podari (zlatokopi maju velmi dobry cuch, najma co sa rumu tyka). V necielovej komore samozrejme nenajde nic (kedze tam ziadny rum nie je) a opat sa s dlhym nosom musi pobrat domov.
Ako si Santo povsimol, zlatokopi su ludia obdareni mimoriadnym stastim. V danej jaskyni a s danou postupnostou symbolov na papieriku je obycajne vela moznosti, ako volit trasu (pretoze z niektorych komor na dany znak moze vychadzat viacero tunelov). Avsak, ak existuje co len jedna postupnost vyberov tunelov, ktora zlatokopa dovedie k rumu, mozete si byt isti, ze zlatokop ju najde.
Uloha
Najoblunejsia rumova jaskyna v Santolande bola jaskyna A. Tato jaskyna sa vyznacovala tym, ze v kazdej komore na lubovolny znak existovala prave jedna moznost, ktorym tunelom sa mohol zlatokop vybrat, alebo ziadny tunel na dane pismeno z komory neviedol. Zlatokopi ju mali radi, lebo pri hladani rumu nemuseli velmi rozmyslat. Nuz si Santo pre nu pripravil mnozstvo papierikov s postupnostami znakov.
Predvcerom vsak bolo zemetrasenie a celu jaskynu A zasypalo. Santa zacalo trapit, co bude s papierikmi do nej robit. Zahodit ich je skoda. Postavit taku istu jaskynu znova sa mu tiez nevidelo. Tak sa rozhodol postavit jaskynu, v ktorej sa budu postupnosti znakov na papierikoch citat odzadu. Navyse chce, aby obratena postupnost na papieriku bola v novej jaskyni rumova prave vtedy, ked bola rumova v jaskyni A. A kedze zlatokopom neuskodi porozmyslat, nemusi byt trasa jaskynou pre postupnosti jadnoznacna (na rozdiel od jasnkyne A).
Oznacme postupnost b1b2...bn reverzom postupnosti a1a2...an, ked plati bn...b2b1 = a1a2...an. Napiste program, ktory nacita popis rumovej jaskyne A a vypise popis rumovej jaskyne B takej, ze postupnost reverz a je rumova pre jaskynu B prave vtedy, ked a je rumova pre jaskynu A.
Priklad
Vstup
Jaskyna A:
NA = 2
(1,1,a)
(1,2,b)
(2,2,c)
Rum je v jaskyni cislo 2.
Vystup
Jaskyna B:
NB = 2
(1,1,c)
(1,2,b)
(2,2,a)
Rum je v jaskyni cislo 2.
Poznamka:
Pre jaskynu A je postupnost na papieriku rumova, ak zacina niekolkymi a, nasleduje jedno b a konci niekolkymi c. Pre jaskynu B je postupnost na papieriku rumova, ak zacina niekolkymi c, nasleduje jedno b a konci niekolkymi a.
(c) 12. April 2001 webmaster
