• KSP
• • Home
  • Novinky
  • Pravidlá
  • FAQ
  • Kuchárka
  • Liaheň
• Séria
• • Zadania a výsledky
  • Odovzdaj riešenie
  • Ideálne riešenie
  • Archív zadaní
  • Zbierka
• Akcie
• • Sústredenia
  • Proboje
  • Akadémia a klub
  • LTT
• Ostatné
• • Podporte nás
    2% z daní
  • Organizátori
  • Sponzori
  • Kontakt
• Iné semináre
• • Trojsten
  • KMS
  • FKS
  • Iné súťaže

Korešpondenčný seminár z programovania

Priklady 2. kola

1. Z krajiny byrokratov
2. Zoltanov tanecny vecer
3. Zoro a zly drak
4. Zazvorove pivo
5. Z centralneho trhoviska

Mili nasi riesitelia,

ako vianocny darcek k Vam prichadzaju zadania druheho kola KSP-Z. Riesenia nam posielajte do 1. februara 1999 a spolu s nimi poslite aj dvoj a trojkorunove znamky v celkovej hodnote 10.- Sk. Prajeme Vam vesele Vianoce, stastny novy rok a polrocne vysvedcenie, za ktore Vas nik neodmeni vypraskom.

V krajine byrokratov treba takmer na vsetko uradne povolenie. Na uradoch su teda obrovske rady, v ktorych casto stoja aj samotni byrokrati. Ale na takeho byrokrata caka na urade mnozstvo ludi. Preto, aby sa zamedzilo nepokojom suvisiacim s dlhymi cakacimi dobami, bol do uradov zavedeny Prioritny system vybavovania byrokratov. Pri prichode na urad kazdy clovek oznami svoje meno a dolezitost. Dolezitost je realne cislo. Cim je vacsie, tym viac je dany clovek potrebny v urade. Ziadni dvaja ludia nemaju rovnaku dolezitost. K vybaveniu potom vzdy volaju cloveka s najvacsou dolezitostou.

Uloha: Naprogramujte Prioritny system vybavovania byrokratov ako program pracujuci v nekonecnej slucke, ktory bude zo vstupu prijimat spravy dvoch typov: spravy o prichodoch jednotlivych ludi na urad a poziadavku na vypisanie mena najdolezitejsieho z cakajucich (ten je potom vybaveny a dalej uz necaka). Spravy su nasledujucich tvarov:
PRICHOD<meno><dolezitost>
DALSI

Na zaciatku na urade necaka nikto. Mozete predpokladat, ze mena su jednoslovne, dlhe najviac 20 znakov.

Priklad:
Vstup a vystup:
>PRICHOD KATKA 93.3
>PRICHOD MATEJ 120.7
>PRICHOD PETER -88.9
>PRICHOD FILIP 62.34
>DALSI
MATEJ
>PRICHOD KLEOFAS 1000.3
>DALSI
KLEOFAS
>DALSI
KATKA
...

Zoltan Samba je ucitelom v tanecnej skole. Prave sa konci kurz tanca pre stredoskolakov a na jeho plecia spadla zodpovednost za vydareny priebeh zaverecneho tanecneho vecierka - venceku. Pri prvom tanci by rad videl na parkete co najviac svojich ziakov. O kazdom chlapcovi a dievcati vie, ci by spolu chceli tancovat, alebo nie. Chcel by ziakov poparovat tak, aby nikto netancoval s niekym, s kym nechce tancovat a sucasne aby vznikol co najvacsi pocet parov. A tak si na papier napisal mena chlapcov do jedneho stlpca, mena dievcat do druheho a skusal ich poparovat. O chvilu ho takto zastihla jeho kolegyna Zita Polkova.

"Na to treba ist systematicky," vravi. "Najprv treba poparovat tych, co su ochotni tancovat s najmenej partnermi. Tych, ktori maju vela potencialnych partnerov, je dobre sparit az na konci - pravdepobnost, ze sa im z nich niekto ujde, je vyssia ako u tych, ktori nemaju velky vyber partnerov."

"Pozri, Peter chce tancovat len s Luciou a Lucia len s Petrom, v tomto pripade je to jednoznacne. Dalsi chlapec, pre ktoreho existuje najmensi pocet potencialnych partneriek, je Miro: moze tancovat len s Jankou a Dankou. Priradime mu Danku, lebo Danka moze tancovat s menej chlapcami ako Janka. A mame dalsi par. Takto postupujeme aj nadalej: Uvazujeme uz len o tych chlapcoch a dievcatach, ktori nemaju par. Z nich vyberieme chlapca, ktory je ochotny tancovat s najmenej dievcatami. Z tychto dievcat mu priradime tu, ktora z nich moze tancovat s najmenej chlapcami. V pripade nejednoznacnosti vyberu (napr. ked niekolko chlapcov ma na vyber rovnaky pocet dievcat) vyberieme lubovolneho z nich. Tymto sposobom vytvorime maximalny pocet parov, aky sa da."

Uloha: Pocet chlapcov oznacme N, pocet dievcat M. Dalej pre kazdeho chlapca mame zoznam dievcat, s ktorymi moze tancovat. Chceme vytvorit co najviac tancujucich parov chlapec - dievca. Samozrejme, kazdy chlapec moze tancovat s najviac jednym dievcatom a naopak. Chlapec moze tancovat len s dievcatom, ktore sa nachadza v jeho zozname. Ak si myslite, ze metoda Zity Polkovej najde vzdy maximalny pocet parov, tak to dokazte a tuto metodu naprogramujte. Ak si to nemyslite, tak uvedte konkretny priklad, na ktorom metoda zlyha. (Nemusite naprogramovat tu spravnu, ale mozte sa o to pokusit.)

Zorovi sa podarilo urcit datum konca sveta a s ulavou zistil, ze este mu zostal cas na to, aby stihol zabit zleho draka. Zly drak zije v jaskyni a ma n hlav. Zabit draka vsak nie je vobec take jednoduche, ako by sa mohlo zdat. Zoro vlastni dva mece - zlaty a strieborny. Ak zautoci na draka striebornym mecom, zotne mu s hlav, ak zlatym, zotne z hlav. Ak vsak drakovi zostane aspon jedna hlava, dorastie mu hned niekolko novych. Ak Zoro utocil striebornym mecom, dorastie a novych hlav, ak zlatym, tak b novych hlav. Zoro nemoze pouzit taky mec, ktory by zotal viac hlav ako drak v danom okamihu ma. Drak zomrie, ak nema ziadnu hlavu. Pomozte Zorovi zistit, ci s danou sadou mecov dokaze porazit draka, alebo ci sa ma radsej vratit do Hanoja a zohnat ine mece.

Uloha: Vasou ulohou bude napisat program, ktory najprv nacita cisla n, s, z, a, b a vypise, ci sa Zorovi moze podarit zabit draka (t.j odtat vsetky jeho hlavy).

Priklad:
Vstup:
n=5
s=4, a=2
z=2, b=3
Vystup:
Ano
(Zoro moze pouzit zlaty mec (drakovi zostane 6 hlav) a nasledne dvakrat strieborny mec, cim draka dorazi.)

Zavoznik Zacharias sa zivi rozvozom zazvoroveho piva. Pivo je sice nezdrave, ale vsetkym pupkatym zbrojnosom prevelmi chuti, takze Zacharias pekne zaraba a dnom i nocou bohatne. Ma to iba jeden hacik. Vzdy, ked nas Zacharias vstupi aj s vozom piva do hocijakeho mesta, musi zaplatit myto a to sa mu veru vobec, ale vobec nepaci. Teraz prave je v meste A a chcel by sa dostat do mesta B, kde sa ma konat velky jarmok, na ktorom sa jeho pivo urcite bude dobre predavat. Chce tam vsak docestovat tak, aby musel cestou platit myto v co najmenej mestach. A tak sedi zadumany na voze a premysla.

Uloha: Na vstupe mate zadane prirodzene cislo N>1 urcujuce pocet miest (mesta su cislovane cislami 1 az N), cislo M urcujuce pocet ciest a dalej zoznam tychto ciest. Kazda cesta vedie medzi dvoma mestami a je zadana dvojicou cisel tychto miest. Dalej su zadane cisla miest A a B. Zistite, ci sa Zacharias moze dostat z mesta A do mesta B. Ak ano, vypiste trasu, veducu z A do B cez najmensi mozny pocet miest. Ak je takychto tras viac, vypiste lubovolnu.

Priklad:

Vstup:
N=7, M=6
cesty:
1 6
2 3
2 7
4 7
4 5
3 5
A=3, B=4

Vystup:
Vysledkom je trasa iduca cez mesta 3, 5 a 4. Existuje este trasa 3, 2, 7, 4, ta vsak ide cez viacej miest. Ak by sa vsak Zacharias chcel dostat z mesta A=3 do mesta B=1, odpovedou programu by malo byt, ze cesta neexistuje.

Raz sa Zoro vybral do mesta nakupovat. Volakto mu vsak zakerne premagnetizoval kompas, a tak si po niekolkych dnoch putovania uvedomil, ze pravdepodobne zabludil. Nezaprel vsak svoju dobrodruznu povahu, pokracoval vytycenym smerom, i dosiel do mesta takeho velkeho, ake nikdy predtym nevidel. Tam sa popytal nahodneho okoloiduceho na smer na trhovisko. Ten mu takto riekol: "Vidim, ze nie si tunajsi. Mas vobec peniaze, ked sa ti na trh zachcelo?". Zoro siahol do mesca, vytiahol tucny zvazok bankoviek a zatriasol s nimi cudzincovi pred ocami. Ten odvetil: "S takymito peniazmi u nas nepochodis, hybaj ich do banky zamenit. Ale pamataj, nase nominalne hodnoty sa inaksie pocitaju!"

V banke Zoro zistil, ze prevodova tabulka medzi normalnou a tunajsou menou je velmi komplikovana - tu totiz uznavaju iba cisla, ktore su odpredu rovnake ako odzadu a nazyvaju ich palindromy. Ako je aj vsade inde zvykom, palindromy maju utriedene, pricom hodnotu palindromu urcuje jeho poradove cislo. Teda napriklad palindrom 6 ma hodnotu 6, palindrom 11 ma hodnotu 10, alebo palindrom 131 ma hodnotu 22. Ako ale Zoro zisti, ci ma dost penazi na zaplatenie meca aj stitu, ked predavac ma obe sumy vycislene v tunajsej mene?

Uloha: Pomozte Zorovi a napiste program, ktory nacita dva palindromy x a y a vypise ich sucet - tiez palindrom. Konkretne, vypise ten palindrom, ktoreho poradove cislo je suctom poradovych cisel palindromov x a y.

Vstup:
44, 2
101, 101
Vystup:
66
292