KSP
- Home
- Novinky
- Pravidlá
- FAQ
- Kuchárka
- Liaheň
Séria
Akcie
Ostatné
Iné semináre
- Trojsten
- KMS
- FKS
- Iné súťaže

Korešpondenčný seminár z programovania

Priklady 4.serie KSP

V dnoch 12.--18.marca 1995 sa konalo jarne sustredenie KSP v Krpacove v Nizkych Tatrach. Dakujeme nadacii Soros Open Society Fund, Bratislava za to, ze nam umoznila toto sustredenie zorganizovat.

Ako sme ocakavali, KSP ziskalo niekolko novych riesitelov (priblizne 25) z Ukrainy, Ruska, Polska a Ceskej Republiky. Tito riesitelia budu zaradeni v osobitnej kategorii a budete si moct ich vysledky porovnat s vasimi.

Ak mate pristup k internetu (ak neviete, co to je, asi k nemu pristup nemate), mozete zadania a najnovsie spravy o KSP citat aj na WWW strankach na adrese http://www.uniba.sk/www/csp.html.

Na zaver uz len: riesenia 4.kola posielajte najneskor do 15.maja 1995 na nasu adresu (nezabudnite na obalku napisat heslo KSP).

O blsom tanci

Riaditel hilbertovho cirkusu sa rozhodol rozsirit program o nove cislo. Na konkurze zvitazil Blsi tanec. Tento tanec tancuje naraz N blsiek, oznacenych cislami 1 az N, ktore su rozostavene na polickach ocislovanych od 1 po N. Z kazdeho policka vedie prave jedna sipka na nejake policko, pricom do kazdeho policka vedie prave jedna sipka.

Na zaciatku kazda blska sedi na policku s rovnakym cislom ako ma ona. Potom v kazdej sekunde preskocia blsky (vsetky naraz) po sipkach na svoje nove policka. Tanec konci, ked su blsky rozmiestnene tak, ako na zaciatku. Riaditel potrebuje, aby cislo trvalo najdlhsie ako sa da a preto treba vhodne nakreslit sipky.

Uloha: Napiste program, ktory pre dane N vypise, ako treba nakreslit sipky, aby cislo trvalo najdlhsie ako sa da. Program by mal tiez vypisat, ako dlho bude cislo trvat.

Priklad:

Vstup:  N=5
Vystup: 1-2 2-1 3-4 4-5 5-3
        Cislo bude trvat 6 sekund.
Vstup:  N=8
Vystup: 1-2 2-3 3-1 4-5 5-6 6-7 7-8 8-4
        Cislo bude trvat 15 sekund.

O tovarni na ceruzky

V tovarni na ceruzky HOK-NI-RO vyrabaju velmi kvalitne rucne vyrezavane ceruzky roznych dlzok. Potom ich balia po N kusoch, pricom v krabicke su ceruzky vzdy usporiadane podla dlzky. V ramci automatizacie kupili do tovarne triedicku. Triedicka je vybavena pravitkom na meranie dlzok ceruziek a rukou, ktora umoznuje vymenit dve ceruzky. Problem je v tom, ze ruka je poskodena a dokaze vymienat iba dve take ceruzky, medzi ktorymi je prave jedna ina ceruzka. V tovarni potrebuju vediet, ci pre danu skupinu ceruziek sa tieto daju usporiadat na triedicke.

Uloha: Napiste program, ktory pre dane N a N dlzok ceruziek vypise, ci sa tieto daju usporiadat na triedicke.

Priklad:

Vstup:  N=4    2,3,1,4
Vystup: Ceruzky sa nedaju usporiadat.
Vstup:  N=3    3,2,1
Vystup: Ceruzky sa daju usporiadat.

O velkej polovacke

Rodina Santovcov sa pohadala s rodinou Bantovcov kvoli portretu starej Santovky. Rodiny vytiahli stare pusky a nastala polovacka.

Situacia v meste sa stala natolko neprehladna, ze serif o obcanoch nevie, do ktorej rodiny patria. Aby to zistil poslal svojich pomocnych serifov na pozorovacie stanovistia, aby mu odtial posielali informacie, kto na koho vystrelil (nemusel nutne trafit). Z tychto informacii chce serif zistit prislusnost jednotlivych obcanov k rodinam. Serif vie, ze konfliktu sa zucastnuju iba dve rodiny a ze vo vnutri rodiny nie su ziadned spory (t.j. clenovia jednej rodiny na seba nestrielaju).

Uloha: Napiste program, ktory nacita N dvojic mien (kazda dvojica mien obsahuje informaciu, kto na koho vystrelil) a vypise rozdelenie obcanov do rodin. V pripade, ze informacie su nedostacujuce na jednoznacne zaradenie clenov do rodin, program vypise: "MALO INFORMACII". V pripade, ze sa podla danych informacii nedaju rozdelit obcania do dvoch rodin, program vypise: "CHYBNE INFORMACIE".

Priklad:

Vstup:  Santo,Banto  Banto,Jim  Jim,Santo
Vystup: CHYBNE INFORMACIE
Vstup:  Santo,Banto  Jim,Bill
Vystup: MALO INFORMACII
Vstup:  Mary,Santo  Bill,Banto  John,Jim   Bill,John  Mary,Bill
Vystup: Santo,Jim,Bill vs John,Mary,Banto

O N-trise

Programator O Velky sa rozhodol napisat modifikaciu znamej hry tetris. Od povodneho tetrisu sa nova verzia bude lisit v tom, ze padajuce dieliky sa nebudu skladat zo styroch, ale z N stvorcekov. Teraz uz treti den sedi a na stvorcekovy papier kresli vsetky mozne dieliky, ktore sa daju zlozit z N stvorcekov a stale si nie je isty, ci ich ma vsetky.

Uloha: Napiste program, ktory pre dane N vypise vsetky dieliky, ktore sa daju zlozit z N stvorcekov a ich pocet. Dieliky vzniknute rotaciou povazujeme za rovnake.

Priklad:

Vstup:  N=4
Vystup: ##  #      #   ##  ##    #
        ##  ###  ###  ##    ##  ###  ####
        Existuje 7 roznych dielikov.

O velkych cislach

Raz si u softferoveho druzstva SoDr pracovnici Matematicko --- matematickej fakulty Matematickej univerzity objednali program, ktory by im umoznil pracovat s velkymi cislami. Cisla s ktorymi chcu pracovat nie su dlhsie ako 257 cifier, mozu byt kladne aj zaporne.

Uloha: Napiste pre pracovnikov MMF MU kniznicu, ktora im umozni pracovat s celymi cislami, ktorych desiatkovy zapis moze byt dlhy az 257 cifier. Vasa kniznica musi obsahovat tieto procedury a funkcie (deklaracie su uvedene pre jazyk Pascal, ak by ste programovali v inom jazyku, pouzite podobne):

GAdd(a,b,c,err) --- scitanie (c:=a+b)
GSub(a,b,c,err) --- odcitanie (c:=a-b)
GMul(a,b,c,err) --- nasobenie (c:=a\times b)
GDiv(a,b,c,r,err) --- celociselne delenie (c:=a \div b; r:=a \mod b)
GAbs(a,c) --- absolutna hodnota cisla (c:=\abs(a))
GInput(a,err) --- vstup velkeho cisla a
GOutput(a) - vystup velkeho cisla a

Vo vsetkych pripadoch premenna err po navrate z procedury obsahuje nulu, ak operacia prebehla v poriadku a kod chyby, ak pocas operacie nastala nejaka chyba (napriklad: vysledok presiahol rozsah velkych cisel apod.)

Nezabudnite, ze ku kniznici treba napisat aj podrobny popis fungovania jednotlivych procedur a pouzitych datovych struktur.

Podporte nás

Účet

Prihlasovanie už nefunguje. Používaj nový KSP web.

kontakt