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

Mili nasi riesitelia,

mozno ste si to uz vsimli, mozno este nie, ale pomalicky sa nam blizi jar. Slnko svieti jasnejsie, vzduch je teplejsi a vy sa uz neviete dockat chvile, ked z pivnice vytiahnete bicykel, oprasite ho, naolejujete, nafukate pneumatiky a vyrazite do prirody. A aby vam cakanie na jar ubehlo rychlejsie, mame tu pre vas zadania stvrteho kola. Riesenia nam s dakymi tymi znamkami posielajte do 2. maja 2000. A este nieco: radi by sme vas upozornili na online sutaz Internet Problem Solving Contest, urcenu pre trojclenne timy, ktorej druhy rocnik sa bude konat 19. maja. Viac informacii najdete na stranke http://www.ksp.sk/ipsc/.

Hodinka pred polnocou je viac ako dve hodiny po nej.

O vojenskych zatarasoch
O Kiribatskych ponorkach
O Velkej cene Formule 1
O meteorologovi Ferdovi
O novych zlatokopoch

1. O vojenskych zatarasoch

Kiribatske kralovstvo zacalo vojnu s Kralovstovom Zimbabwe. Vraj hackeri z Kiribati napadli WWW stranky na oficialnom kralovskom serveri v Zimbabwe. Nevedno, co je na tom pravdy. Mozno to bola len zamienka. Ale v tejto chvili uz Zimbawejski vojaci zacali pochod na Kiribati. Na pokyn kiribatskeho krala zasadli vojenski strategovia a taktici a zacali organizovat obranu.

Medzi Kiribati a Zimbabwe vedie siet ciest. Kazda cesta ma danu svoju sirku. Aby kiribatske vojsko uspesne obranilo svoju krajinu pred nepriatelom musia postavit krizom cez celu sirku niektorych ciest zatarasy. Zistite, kolko najmenej metrov zatarasov musi kiribatska armada postavit, a ktore cesty pritom zatarasit aby si mohla byt ista, ze Zimbabwejski vojaci nevstupia do ich vlasti.

Uloha

Je dany pocet uzlov N cestej siete medzi Kiribati a Zimbabwe. Uzol cislo 1 su Kiribati a uzol cislo N je Zimbabwe. Dalej je dany pocet ciest M spajajucich uzly. A nakoniec je na vstupe M trojic celych cisel x,y,s popisujucich jednotlive cesty. Trojica x,y,s ( 1 <= x,y <= N) znamena, ze cesta vedie z uzla x do uzla y a jej sirka je s metrov. Cesty su obojsmerne. Vasou ulohou je zistit, ktore cesty treba zatarasit, aby sa postavilo, co najmenej metrov zatarasov a pritom neexistovala cesta, po ktorej by sa mohli Zimbawejski vojaci dostat do Kiribatskeho Kralovstva. Vypiste aj celkovu dlzku zatarasov. Ak je moznosti ako cesty zatarasit viac vypiste lubovolnu z nich.

Priklad

Vstup:

Vystup: Treba zatarasit cesty (1,3), (2,3) a (2,4). Celkova dlzka zatarasov bude 9 metrov.

2. O Kiribatskych ponorkach

Blizi sa leto a s nim aj potapacska sezona. Citit to aj v Kiribatskom Spolku Potapacov, kde su pripravy na nu v plnom prude. Na zvysenie bezpecnosti potapania treba podrobne preskumat morske priekopy medzi Kiribatskymi ostrovmi, a tak sa clenovia spolku rozhodli zadovazit si novu ponorku.

Vsetky ponorky dostupne na kiribatskom trhu su dvojrozmerne a pozostavaju z rovnako velkych stvorcovych segmentov. Dva segmenty jednej ponorky bud nemaju ziaden prienik, alebo maju spolocnu celu jednu stranu. Kazda ponorka pozostava z jedneho kusa, teda z lubovolneho jej segmentu sa da do lubovolneho ineho prejst cez niekolko dalsich jej segmentov. Navyse plati, ze ked zoberieme dva segmenty ponorky, ktore su v rovnakej hlbke, a spojime ich stredy myslenou ciarou, ani jeden bod tejto usecky nelezi mimo ponorky.

Morska priekopa ma tvar obdlznika, ktory pozostava z MxN stvorcovych segmentov rovnakej velkosti ako segmenty ponorky. Niektore segmenty priekopy su zarastene koralmi, ktore prekazaju pri jej prieskume. Horna strana obdlznika predstavuje morsku hladinu.

Ponorka sa na zaciatku potapania nachadza na hladine (t.j. ziadna jej cast nie je pod hladinou). Pocas celeho potapania musia byt horne strany jej segmentov rovnobezne s hladinou. Posadka moze pocas zostupu ponorku posuvat doprava, dolava alebo dole. V ziadnom okamihu potapania sa vsak ziaden jej segment nesmie nachadzat na mieste zarastenom koralmi.

Clenovia Kiribatskeho Spolku Potapacov teraz smutne sedia nad katalogom predavanych ponoriek a mapou morskej priekopy, v ktorej je zakreslene, ktore jej segmenty su zarastene koralmi. Dumaju, dumaju, ale vydumat nevedia, ktoru z ponoriek kupit, aby sa mohli ponorit co najhlbsie. Pomozte im a napiste program, ktory im tuto tazku ulohu pomoze vyriesit.

Uloha

Su dane cisla M a N a mapa morskej priekopy s rozmermi MxN. Dalej su dane cisla a, b a tvar ponorky s rozmermi a x b. Napiste program, ktory zisti, ako hlboko sa moze dana ponorka do danej priekopy ponorit.

Priklad

Vstup:

7 8         2 2
..#####     .#
..#....     ##
.......
.......
..#....
.#.#..#
....#..
...#.#.

Vystup:
Ponorka sa moze ponorit do hlbky 6.

3. O Velkej cene Formule 1

Tato sezona bola pre Schumachera velmi zla. Niektore preteky sice vyhral on, dost vela ich ale vyhral aj Hakkinen. Nastastie ma vo vedeni pretekov Formula 1 priatela, ktory mu je co-to vdacny. Taky vdacny, ze mu je ochotny za kazdu cenu pomoct. Avsak jedine, coho je schopny, je iniciovat odhlasovanie zmeny bodovania. A tak teraz Schumacher sedi nad vysledkovymi listinami a duma, ci sa da vymysliet bodovanie, pomocou ktoreho by ziskal titul majstra sveta.

Uloha

Napiste program, ktory dostane na vstupe vysledkove listiny N pretekov a rozhodne, ci existuje take obodovanie prveho az tretieho miesta, pri ktorom by mohol Schumacher vyhrat.

Na vstupe je pocet pretekov N, a tabulka, kolkokrat sa ktory pretekar umiestnil na ktorom mieste. Vystupom bude SCHUMACHER MOZE VYHRAT, ak existuje take obodovanie prvych troch miest p₁>= p₂ >= p₃>=1, pri ktorom by Schumacher vyhral, to znamena, ze by mal najviac bodov zo vsetkych.

Priklad

Vstup:

N=5
Meno             1. miesto   2.miesto  3.miesto
Hakkinen            4           0         1
Schumacher          1           4         0
Hill                0           0         2
Irvine              0           1         1
Davidko             0           0         0

Vystup:

SCHUMACHER MOZE VYHRAT

(pri bodovani p₁=10, p₂=9, p₃=5)

4. O meteorologovi Ferdovi

Ferdo ako cerstvo vystudovany meteorolog nastupil do prace do meteorologickeho ustavu. Velmi sa tesil, ze si bude moct zapredpovedat pocasia do lubovole, ba ze ho mozno obcas pustia aj vystupovat do televiznych sprav o pocasi a teraz toto... Ako noveho zamestnanca ho totiz prevelili na oddelenie statistiky. Ferdo teraz smutne sedi nad stlpcami zaznamov o teplotach nameranych kazdy den od vzniku meteorologickeho ustavu. Nadriadeni mu totiz dali za ulohu zistit, kedy bolo najteplejsie obdobie. Obdobie je lubovolny suvisly usek aspon K dni. Teplotou obdobia rozumieme priemernu teplotu za jednotlive dni. Pomozte chudakovi Ferdovi, bezmocne sediacemu nad stohom zaznamov, lebo inak skolabuje a budete ho musiet kriesit.

Uloha

Napiste program, ktory nacita pocet dni existencie ustavu N, minimalnu dlzku obdobia K, teploty t₁,t₂,... t_N (realne cisla) namerane v jednotlivych sledovanych dnoch a vypise prvy a posledny den obdobia, ktore je dlhe aspon K dni a ma pritom maximalnu moznu priemernu teplotu.

Priklad

Vstup:

N = 8, K = 3
teploty:
-1.9, 4.5, -3.2, 0.5, -4.5, 5.8, -1.6, -2.7

Vystup:

Najteplejsie bolo v obdobi od 2. po 6. den.
Priemerna teplota 0.62.

5. O novych zlatokopoch

Opat prisla vlna zlatej horucky, a tak aj na Vysnu Klondiku dorazila skupinka novych zlatokopov. Vystupili z vlaciku, ktory ich doviezol do Puerto Paza, na okraj civilizacie, poobzerali sa a... Ktovie ci stastnou, ale urcite nahodou natrafili prave na Santa a Banta. "Ehm... Prosim vas, neviete nam povedat, ako sa dostaneme do Dolneho Kelcova ?" "To musite najskor do Nalomenej Triesky." zahlasil suverenne Santo. "To musite najskor do Nastiepeneho Iveru." zahlasil naraz s nim nemenej suverenne Banto. "Viete co, ved my sa tam vlastne tiez vraciame... Odvedieme vas tam. Samozrejme, nebude to zadarmo..."

Cesta do Dolneho Kelcova je usecka, na nej lezi N+1 miest, ocislovanych od 0 (Dolny Kelcov) po N (Puerto Paza, kde prave su). Od poslednej reformy VHDD (Vysnoklondicka hromadna dostavnikova doprava) vsak dostavniky premavaju zvlastne. Presnejsie, z mesta A do mesta B ide dostavnik len ak A>B a A-B nie je zlozene cislo. (Zlozene cislo je prirodzene cislo, ktore ma ineho delitela ako 1 a seba.) Uznate, ze za tychto okolnosti nie je vobec lahke niekam sa dostat. Preto niet divu, ze sa Santo a Banto stavili - budu na striedacku vyberat, do ktoreho mesta sa ide. Kto dovedie skupinku do Dolneho Kelcova, vyhrava a dostane vsetky peniaze, ktore im za sprievod greenhorni zaplatia.

Uloha

Napiste program, ktory nacita cislo N a nasledne bude hrat tuto hru za zacinajuceho zlatokopa.

Priklad priebehu hry

N=11

Santo: Podme do mesta 8.
Banto: Teraz podme do mesta 3.
Santo: A teraz do mesta 0.
Santo vyhral.

Podporte nás

Účet

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

kontakt