Priklady 4.kola (2. kola letnej casti) 18.rocnika KSP-Z

Mile deturence,

a su tu zadania posledneho kola KSP. Svoje riesenia nam posielajte najneskor do 4. juna. 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!

1. Z podzemneho archivu
2. Zbytocny Misko
3. Zvlastne poznamky
4. Zabudnuta pekaren
5. Zbludila Zeofina

V podzemi sa nasli nekonecne velke zasoby zltej pasky a deti sa s nou hned zacali zabavat. Rozdelili jeden kotuc na policka a zacali na ne zapisovat rozne divne znaky. Kludne aj jeden znak cez druhy. Vzdy, ked niekto popisal nejaky suvisly usek zltej pasky, oznamil ostatnym interval, na ktorom sa nachadza jeho prave vytvorene dielo. Na konci dna chceli deti vediet, kolko policok zltej pasky vlastne popisali, ale zistili, ze to vobec nebude jednoduche.

Uloha

Na vstupe je dane cislo N - pocet zapisov na zltu pasku a dalej N intervalov, kam deti pisali. Interval i,j znamena, ze sa zapisovalo na policka i,i+1 ... j. Vasou ulohou je zistit pocet policok zltej pasky, na ktorych je nieco napisane.

Priklad

Vstup
N=4

2 4
3 4
3 5
7 7

Vystup
Deti popisali 5 policok zltej pasky.

Misko je agentom ATS (Atlantidska tajna sluzba). Nedavno zistil, ze v Atlantide operuju cudzi spioni. A tak by ho zaujimalo, ktory z nich je velmi dolezity, ktory menej, ktory je uplne zbytocny a podobne. Vyhlasil velku, celostatnu patraciu akciu. Na konci (ked uz vsetci ostatni agenti spokojne oddychovali v blizkom rekreacnom zariadeni) mal na stole obrovske mnozstvo listkov s napismi v tvare: XZ nosi spravy AB.

Najdolezitejsi spion je ten, ktory nemusi nikomu odovzdavat spravy. Ten trochu menej dolezity nenosi spravy nikomu, okrem najdolezitejsieho spiona. Lubovolny agent je menej dolezity ako ti, ktorym nosi spravy a dolezitejsi ako vsetci ti, ktori nosia spravy jemu. Misko teraz chce, aby mu niekto zotriedil cudzich spionov podla dolezitosti.

Uloha

Na vstupe je zoznam ziskanych informacii v tvare XZ AB (XZ informuje AB). Vasou ulohou je zotriedit spionov podla dolezitosti od najdolezitejsieho (nemusi nikoho informovat) az po najmenej doleziteho (nikto mu nenosi spravy). Ak je takych poradi viac, program vypise lubovolne z nich. Ak taka postupnost neexistuje, vypise, ze uloha je nesplnitelna.

Priklad

Vstup

Vlado Janka
Misof Brano
Misof Nanka
Yoyo Brano
Brano Vlado
Nanka Meri
Brano Nanka
Janka Risko
Risko Meri
Davidko Meri
Janka Meri

Vystup

Meri Nanka Davidko Risko Janka
Vlado Brano Yoyo Misof

Kleofasa odjakziva pritahovali velke veci. Medzi jeho najoblubenejsie patri aj faktorial. Ved vypocitat taky faktorial nie je vobec jednoduche. Kleofas sa ale rad pysil tym, ze vedel zratat aj velmi velke faktorialy. A aby o tom presvedcil aj vsetkych naokolo, zacal vo vsetkych svojich poznamkach a vypoctoch pouzivat faktorialovu sustavu. Predtym, ako stihol dokoncit svoj navacsi vynalez, ale niekam zmizol. Teraz stoja jeho nasledovnici pred tazkou pracou. Prestudovat jeho poznamky a trapit sa pocitanim vo faktorialovej sustave.

Uloha

Napiste program na scitanie dvoch cisel vo faktorialovej sustave. Vystupom je opat cislo vo faktorialovej sustave. Cislo a_na_n-1... a₁ vo faktorialovej sustave je a_n.n! + a_n-1.(n-1)!+...+ a₁.1! v desiatkovej, pricom 0<=a_i<=i.

Priklad

Vstup

1211 + 321

Vystup

2210

V istej nemenovanej dedinke maju pekaren. Nie vsak obycajnu, ale taku staru, prastaru pekaren, v ktorej sa vsetko robi rucne. Napriklad aj ukladanie napecenych bochnikov chleba. Tie treba ulozit do radu tak, aby na jednom konci boli tie najchrumkavejsie a na druhom tie menej podarene. Pekarov pomocnik, za tuto pracu zodpovedny, si uz nacvicil pracu s pekarskou lopatou, na ktoru sa vedla seba zmestia prave 3 alebo 4 bochniky chleba. Ked sa rozhodne, ze treba bochniky v rade trochu preusporiadat, naberie 3 alebo 4 susedne bochniky na lopatu a obratnym pohybom ich vo vzduchu prehodi tak, ze sa tieto bochniky ocitnu na lopate v zmenenom poradi - najpravejsi bochnik sa ocitne uplne vlavo a ostatne sa len posunu o jedno miesto vpravo. Potom ich z lopaty zosunie do povodneho radu a ak treba, moze takyto kusok opakovat, kolkokrat sa mu len zachce.

Uloha

Je dane cislo N - pocet bochnikov v rade, za nim nasleduje povodne poradie bochnikov v rade, pricom kazdy bochnik ma priradene unikatne cislo z rozsahu 1 - N, urcujuce chrumkavost toho-ktoreho bochnika (chrumkavejsi ma vacsie cislo) . Ulohou je vypisat postupnost prehadzovacich operacii, ktore sposobia, ze bochniky budu v rade usporiadane od najchrumkavejsieho po ten najmenej chrumkavy. Prehadzovacou operaciou je jedno nabratie bochnikov na lopatu a ich preusporiadanie; kazda takato operacia sa da popisat polohou prveho bochnika v rade, ktory naberieme (teda 1, 2, ...) a poctom nabranych bochnikov (teda 3 alebo 4).

Pozrime sa na priklad takej prehadzovacej operacie: nech a₁, a₂, ..., a_i, a_i+1, a_i+2, a_i+3,..., a_n su chrumkavosti bochnikov v rade za sebou, potom prehadzovacia operacia (i,4) bude ovplyvnovat bochniky na poziciach i, i+1, i+2 a i+3 a vysledkom bude rad bochnikov, ktorych chrumkavosti budu a₁, a₂, ..., a_i+3, a_i, a_i+1, a_i+2, ..., a_n.

Priklad

Vstup
N=7

6 7 3 4 2 1 5

Vstup
1. operacia: (5,3)
2. operacia: (2,4)
3. operacia: (3,3)
4. operacia: (1,4)

Zeofinu pochytila tuzba vytvorit nieco velkolepe. Preto sa rozhodla, ze nakresli taky velky obrazok, ako nikdy pred tym. A tak kreslila a kreslila... Po niekolkych dnoch usudila, ze obrazok je uz dost velky, a tak sa rozhodla vratit sa domov. No vtedy s hrozou zistila, ze zabludila. Pamata si sice, aky obrazok nakreslila, ale vobec netusi, ako sa moze dostat domov. Kedze je uz uplne bezradna a vycerpana, budete jej musiet pomoct.

Ked chce Zeofina kreslit, namoci si chvostik do atramentu, postavi sa doprostred velkeho cisteho papiera a zacne sa po nom presuvat. Ak ma chvostik spusteny, zanechava za sebou ciaru, ak ho ma zdvihnuty, presuva sa len tak. Aby sa pri kresleni nepomylila, dopredu sa nauci postupnost povelov tvaru

• dopredu k - pohni sa k krokov dopredu (k je realne),
• dolava u - otoc sa o u stupnov dolava,
• doprava u - otoc sa o u stupnov doprava,
• zdvihni - zdvihni chvostik a
• poloz - poloz chvostik na papier

Uloha

Napiste program, ktory nacita postupnost povelov, ktorymi Zeofina vykreslila obrazok a poradi Zeofine, ako sa ma dostat domov. To znamena, ze vas program musi vypisat, ako sa ma Zeofina otocit a o kolko krokov sa ma pohnut dopredu, aby sa dostala na miesto, z ktoreho kresbu zacinala.

Priklad

Vstup

DOPREDU 10
DOPRAVA 90
DOPREDU 10
DOPRAVA 90
DOPREDU 30
DOLAVA 90
DOPREDU 10

Vystup

DOLAVA 135
DOPREDU 28.284