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 3.kola 18.rocnika KSP

Mili riesitelia,

taak a su tu nove zadania. Dufam, ze ste uz na zaciatku skolskeho roka zaregistrovali zmenu pravidiel: Vsetky vysledkove listiny sa budu ratat od 3. kola, podobne to bude s pozyvanim na jesenne sustredenie KSP. A preto ak ste KSP doteraz nikdy neriesili, nevahajte a zapojte sa, ale nezabudnite nam vsak poslat evidencny listok. Riesenia nam poslite najneskor do 5. marca 2001, nezabudnite k nim prilozit postove znamky v hodnote 15,- Sk.

Ked ta biju, utekaj!
KSPaci

O zufalom programatorovi
O maskrtnom Davidkovi
O Santovi, Bantovi a parcelach II
O futbalovom druzstve
O Santolande III

1. O zufalom programatorovi

Kde bolo, tam bolo, kdesi pod horami stal domcek. Keby ste k nemu potichucky prisli a nazreli cez okno, zbadali by ste pri praci programatora. Nazvime ho trebars Miso. Prave si sadol k pocitacu, vedla seba polozil tacku s cajom a kolacikmi, na pocitaci pustil hudbu, proste idylka... Zrazu buchol pastou po stole. "To snad ani nie je pravda! Ten blby prehravac tie pesnicky zase prehadzal! (Cely priklad je zalozeny na praktickej skusenosti - ked date WinAmp-u otvorit adresar, nenahadze pesnicky do playlistu v poradi, v akom su ocislovane. Lezie to na nervy :-)) V takychto podmienkach sa naozaj neda pracovat!"

Preto zacal pesnicky usporaduvat tak, aby boli v poradi, v akom su ocislovane. Preusporiadat sa daju jedine tak, ze vzdy chyti mysou niektoru pesnicku a odtiahne ju na nejake miesto v playliste. Tejto operacii hovorme presun. No a kedze Miso je snad este lenivejsi ako priemerny programator, chcel by si pesnicky usporiadat na co najmenej presunov. Nechce sa mu vsak nad tym rozmyslat, ba co viac, ani len program na to sa mu nechce pisat. Tak to nechal na vas, ved vy ste predsa vsetci taki sikovni a snazivi...

Uloha

Na vstupe je dane N - pocet pesniciek v albume a N cisel od 1 po N (kazde prave raz) - cisla pesniciek v poradi, v akom su teraz v playliste. Vasou ulohou je napisat program, ktory vypise minimalny pocet presunov potrebny na usporiadanie playlistu. V usporiadanom playliste maju byt pesnicky samozrejme v poradi 1,2,...,N.

Priklad

Vstup

N=5
2 5 1 3 4

Vystup
Stacia 2 presuny (napr. presunieme pesnicku 2 na 3. miesto a potom 5 na 5. miesto)

2. O maskrtnom Davidkovi

Davidko je velmi maskrtny a tak necudo, ze sa casto cestou zo skoly zastavi v malom obchodiku na rohu ulice, kde predavaju rozne oriesky a susene ovocie. Velke bolo Davidkovo potesenie, ked mu minule pri odchode povedali, ze je milionty zakaznik a moze si niekedy vecer, po zaverecnej, prist nabrat orieskov a suseneho ovocia, kolko mu taska unesie. Davidko teraz sedi a premysla, ako by co najcennejsie jedlo z obchodu odniesol...

Uloha

Na vstupe je dane M - nosnost Davidkovej tasky, N - pocet druhov maskrt, ktore v obchode po zaverecnej ostali, a dalej ich specifikacia. Ku kazdemu druhu je dana hmotnost a cena za celu tu hmotnost. Vypiste, kolko si ma Davidko z jednotlivych druhov maskrt navazit, aby sa mu taska nepretrhla a pritom, aby co najdrahsie maskrty domov doniesol. Taktiez vypiste hodnotu odneseneho tovaru.

Zamyslite sa nad efektivnostou vasho algoritmu.

Priklad

Vstup
M = 5
N = 3

3 15
2.5 113
1 79,5

Vystup

1.5 2.5 1
200

3. O Santovi, Bantovi a parcelach II

Santo a Banto si na Vysnej Klondike opat nasli niekolko zlatych zil. Celi nateseni teda utekali na registracny urad, pekne si parcelu zapisat. Tam ich ale ako prvy zaujal obrovsky papier popisujuci nove zmeny vo vyhlaske o parcelach. Podla nej sa za parcely bude platit poplatok, ktory zavisi od poctu zlatych zil vo vnutri parcely. Zily na okraji sa nezapocitavaju. Ak by si tesne vedla nich prenajal parcelu nejaky iny zlatokop, ma na zlatu zilu na rozhrani rovnaky narok a je iba na nich, ako sa dohodnu. "Tak to teda nie. My im cez rozum prejdeme a za parcelu nic platit nebudeme", prehlasil po kratkom zamysleni Banto a rozbehol sa vyplnat formular. Hned vsak zastal na kolonke "Plocha parcely".

Uloha

Napiste program, ktory pre zadane cislo N a N bodov v rovine vypise obsah takeho mnohouholnika, ze vsetkych N bodov lezi na jeho obvode, ako aj jeho vrcholy v poradi po obvode.

Priklad

Vstup
N = 6

(0.5, 2), (-0.5, 1),
(0, 1),   (0, -0.5),
(1, 0),   (-0.5, 0)

Vstup
Obsah je 2.125.

(-0.5, -0.5), (1.5, -0.5),
(0, 1),       (0.5, 2),
(-0.5, 1)

Poznamka: To je mnohouholnik na obrazku, samozrejme riesenim moze byt aj iny.

4. O futbalovom druzstve

Na jednom gymnaziu sa medzi triedami kazdorocne organizuje futbalovy turnaj. Milan, najlepsi futbalista 4.B, sa rozhodol vybrat z triedy druzstvo, ktore to tento rok musi vyhrat. Poobede zavolal vsetkych svojich spoluziakov na futbalove ihrisko. Kazdy Milanovi predviedol, ako je dobry v utoku, v poli a v obrane a on kazdemu priradil tri cisla urcujuce jeho kvalitu. Potom Milan zasiel za Risom, najlepsim programatorom 4.B, a poprosil ho, aby na zaklade tychto cisel zostavil najlepsie mozne futbalove druzstvo. Riso je vsak uz unaveny a musi sa ist domov ucit, preto vas poprosil, aby ste zostavili druzstvo vy.

Uloha

Je dane N - pocet futbalistov v triede. Pre kazdeho z nich su dane tri cisla f_a, f_b, f_c - kvalita hraca v utoku, v poli a v obrane. Chceme zostavit druzstvo zlozene z A utocnikov, B poliarov a C obrancov tak, aby sucet kvalit utocnikov v utoku, poliarov v poli a obrancov v obrane bol najvacsi mozny. Vasou ulohou je vypisat tento sucet.

Priklad

Vstup
N=8, A=2, B=2, C=1

1. hrac: 1 2 3
2. hrac: 10 5 4
3. hrac: 6 7 9
4. hrac: 0 1 12
5. hrac: 1 2 3
6. hrac: 1 5 4
7. hrac: 6 7 9
8. hrac: 9 1 0

Vystup
Sucet kvalit hracov druzstva: 45

Poznamka: Napriklad druzstvo: utocnici: 2, 8, poliari: 3, 7, obrancovia: 4

5. O Santolande III

Pre tych, co este stale nemali moznost zoznamit sa so Santom a jeho uzasnym vynalezom - rumovymi jaskynami, v kratkosti zrekapitulujeme: 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 ako si Santo povsimol, ak existuje co len jedna postupnost vyberov tunelov, ktora zlatokopa dovedie k rumu, mozete si byt isti, ze zlatokop ju najde.

Uloha

a) Santo v slabej chvilke navyrabal mnozstvo papierikov a na kazdy z nich napisal nejaku postupnost zlozenu z cifier 0...9 - cislo v desiatkovej sustave. A kedze nevedel, co s tolkymi papierikmi robit, rozhodol sa postavit rumovu jaskynu, ktorej tunely budu tiez pooznacovane ciframi 0...9 taku, ze trasa pre danu postupnost cifier c₁c₂...c_k na papieriku z komory 1 do niektorej z cielovych komor existuje prave vtedy, ked cislo c₁c₂...c_k v desiatkovej sustave je delitelne 6. Vasou ulohou, ako uz iste tusite, bude navrhnut pre Santa tuto rumovu jaskynu. V ramci uspornych opatreni sa snazte, aby mala co najmenej komor.

b) Santovi sa raz snival takyto sen: Majme dve rumove jaskyne A a B. Nech a₁a₂...a_k je postupnost znakov na papieriku urcena pre jaskynu A a b₁b₂...b_l je postupnost znakov urcena pre jaskynu B. Majme zleho Banta, ktory za temnej noci berie noznice a striha obidva papieriky na m kuskov. Kazdy kusok obsahuje suvisly usek niekolkych (mozno 0) znakov z prislusneho papierika. Potom vezme prvy kusok z prveho papierika, prilepi k nemu prvy kusok z druheho papierika, prida druhy kusok z prveho, druhy kusok z druheho, striedavo priliepa kusky z prveho a druheho papierika, az dostane novu postupnost znakov a₁...a_i₁, b₁...b_j₁,...,a_{i_m-1+1}...a_{i_m}a_{i_m-1+1}. Napriklad z postupnosti VYSNA a KLONDIKA by takto mohol dostat napriklad KLO VY NDI SNA KA.

V tomto momente sa Santo zobudil. A vymyslel pre vas ulohu. Predtym vsak dve definicie. Postupnost znakov a₁...a_k pre jaskynu J sa nazyva rumova, ak existuje trasa podla tejto postupnosti, ktora v jaskyni J vedie do cielovej komory. Hovorime, ze postupnost c₁...c_k+l je zmiesanina postupnosti a₁...a_k a b₁b₂...b_l ak vznikla postupom zo Santovho sna. Napiste program, ktory nacita popisy dvoch rumovych jaskyn A a B a vypise popis rumovej jaskyne C takej, ze postupnost c je rumova pre jaskynu C prave vtedy, ak je zmiesaninou nejakej rumovej postupnosti a pre jaskynu A a rumovej postupnosti b pre jaskynu B.

Priklad

Vstup
Jaskyna A:
N_A = 1

(1,1,a)

Rum je v jaskyni cislo 1.

Jaskyna B:
N_B = 2

(1,2,b),
(2,2,b)

Rum je v jaskyni cislo 2.

Vystup
Jaskyna C:
N_C = 2

(1,1,a),
(1,2,b),
(2,2,a),
(2,2,b)

Rum je v jaskyni cislo 2.

Poznamka:
Pre jaskynu A je postupnost na papieriku rumova, ak sa sklada z 0 alebo viacerych pismen a. Pre jaskynu B je postupnost na papieriku rumova, ak sa sklada z 1 alebo viacerych pismen b. Vystupom bude jaskyna C, pre ktoru je postupnost na papieriku rumova, ak sa sklada z pismen a a b a obsahuje aspon jedno pismeno b.

Podporte nás

Účet

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

kontakt