- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Priklady 2. kola
- Zavis a jeho rozhlasovy sen
- Ziskuchtivi zbojnici a Kiribati
- Zlato n ad zlato
- Zatvorkove postupnosti
- Zrazene vlaciky
Mili priatelia KSP,
prichadzaju Vianoce a s nimi aj zadania druheho kola kategorie Z. Ako obvykle, aj tento rok ste si mnohi neprecitali propozicie seminara, co sa prejavilo niekolkymi disketami, neuplnymi popismi, niekolkymi chybajucimi informaciami (trieda, skola, adresa domov a pod.) a jednym anonymom. Anonym je zo Sniny, prosime ho, aby sa prihlasil. Zvysnych ucastnikov prosime o poslanie chybajucich udajov pokial mozno na navratke KSPecka.
Vase riesenia nam posielajte na horeuvedenu adresu (heslo KSP-Z) a to do 2. februara 1997 (rozhoduje peciatka na obalke). Tesime sa na vase riesenia.
Kto ma mrcha zenu, netreba mu krenu!
KSPaci
1. Zavis a jeho rozhlasovy sen
Zavis je obchodnikom od narodenia. Raz ho napadlo, ako dobre by sa dalo zbohatnut, keby si zalo zil vlastne radio. Mal by kopec peniazkov za reklamu, jednym slovom rozpravka.
I zacal zistovat, kto by mal zaujem v Zavis radiu odvysielat reklamu. Pre kazdy den od dna D (predpokladaneho zaciatku vysielania) si vypocital, kolko bubacikov by zarobil na reklame. Nadseny si lahol spat. Ked sa rano zobudil, napadla ho hrozna myslienka: ved on nema ziadny vysielac! Mohol by si nejaky prenajat, ale to stoji dost bubacikov. Navyse, vysielac sa da prenajat iba na jedno suvisle obdobie. Chudak Zav is, schytil ceruzku a papier a zacal pocitat, odkedy dokedy je najvyhodnejsie prenajat si vysielac, aby co najviac zarobil...
Uloha: Napiste program, ktory nacita C - cenu za jeden den prenajatia vysielaca, pocet dni D, pre kazdy den B[i] - kolko v ten den moze Zavis zarobit na reklame a vypocita, odkedy dokedy je pre Zavisa najvyhodnejsie prenajat si vysielac.
Priklad:
Vstup:
pocet dni: 6
cena za jeden den vysielania: 20
zaro
bky v jednotlive dni: 18 35 6 80 15 21
Vystup:
Najvyhodnejsie je prenajat si vysielac od 2. do 4. dna. Spolu zarobi
35+6+80 - 3x20 = 61 bubacikov
2. Ziskuchtivi zbojnici a Kiribati
Suostrovie Kiribati ma problemy. Od isteho casu ich pravidelne (kazdy prvy pondelok v mesiaci) prepadavaju Ziskuchtivi zbojnici. Nakoniec Kiribatcania povedali "dost" a rozhodli sa nakupit v miestnom obchode s domacimi zvieratami levy a umiest nit ich na pobrezi. Najblizsie ked si Ziskuchtivi zbojnici pridu zobrat, co im nepatri, pridu mnohi o ruky, nohy alebo o hlavu (ti (ne)stastnejsi). Uz treba len vyratat dlzku pobrezia (aby zistili, kolko levov treba) a Ziskuchtivi zbojnici, traste sa!
V kralovskej kniznici si Kiribatcania nasli mapu suostrovia, no nech robia, co robia, dlzku pobrezia nevedia zistit. Zistili iba nasledujuce skutocnosti: Mapa je rozdelena na MxN stvorcekov, kazdy stvorcek predstavuje pevninu (je oznaceny 1) a lebo more (je oznaceny 0), teda ziaden stvorcek neobsahuje pevninu aj more zaroven. Stvorceky dotkykajuce sa navzajom hranou ( nie rohom) patria do toho isteho ostrova. Ziadny ostrov sa nedotyka okraja mapy (inak by s nevedelo, ci mimo mapy nepokracuje), teda na okraji mapy je more. Kazdy ostrov na mape patri do suostrovia Kiribati a kazdy ostrov zo suostrovia Kiribati je na mape. Pobrezie tvoria hrany medzi stvorcekom pevniny a stvorcekom mora. V suostrovi Kiribati sa mozu nachadzat (uz bez ostrovov ) aj laguny, vnutorne jazera a ine mlaky, ktorych brehy sa do pobrezia nezaratavaju.
Uloha: Napiste program, ktory vypocita dlzku Kiribatskeho pobrezia (tj. sucet dlzok pobrezi vsetkych ostrovov na Kiribati), pricom su dane rozmery mapy M a N a mapa sustrovia.
Priklad:
Vstup:
M=5, N=6
Mapa suostrovia:
000000
011100
010110
011110
000000
Vystup:
Dlzka pobrezia je 14.
3. Zlato nad zlato
V softferovom druzstve SoDr maju novu ulohu. Tentoraz ide o program pre jedno zlatnictvo. Nanestastie kazdy z N pracovnikov vytvoril vlastny program a medzi sebou sa nevedia dohodnut, ktory pouzit. Programy (ocislovane od 1 az N podla osobneho kodu pracovnika) sa lisia vyslednym cislom udavajucim pocet karatov testovaneho zlateho predmetu.
Po burlivej polemike zavrhli programy s najvyssim odhadom (aby zakaznik nemusel vela platit), aj s najnizsim odhadom (aby zakaznik nemoh ol byt odsudeny za kradez). Nakoniec sa rozhodli pre zlatu strednu cestu, teda pre taky program, ze ked rozdelime zvysne programy na dve skupiny podla toho, ci davaju mensi alebo vacsi vysledok, tak ich bude bud rovnako, alebo tych s mensim vysledkom bude o jeden menej.
Cele druzstvo zacalo burlivo oslavovat, ako mudro to vyriesilo, az kym nezacali vyberat prislusny program. Naraz vsetkym zamrzol usmev na tvari.
Uloha: Napiste program, ktory dostane na vstupe N roznych cel ych cisel (vysledkov programov jednotlivych pracovnikov) a vypise vysledok, aky da program vybraty podla kriterii uvedenych vyssie.
Priklad:
Vstup:
N=7
Vysledky programov: 10, 4, 3, 15, 2, 6, 1
Vystup:
Vybraty program dava vysledok 4.
4. Zatvorkove postupnosti
Zatvorka kdesi cital o takejto postupnosti: Vezmime si lubovolne prirodzene cislo N>1. Ak je parne, vydelme ho dvomi, ak je neparne, vynasobme ho tromi a pripocitajme jednotku. Toto mozeme opakovat dovtedy, kym nie je N jedna.
Hm, povedal si Zatvorka, to by bolo nieco pre mojich neposlusnych ziakov! Ak budu zase tak vyvadzat ako minule, dam im nejake cislo, a nech si pocitaju. Ved sa oni naucia posluchat! Ma to vsak jednu nevyhodu: ak to cislo bude velmi velke, bude sa tazko pamatat. Nuz, Zatvorka teraz chudak sedi a rozmysla, ake cislo by sa najviac hodilo.
Uloha: Pomozte Zatvorkovi. Najdite (za vydatnej pomoci va sho makacskeho programu) take cislo N, ze p(N)/c(N) bude co najvacsie, kde p(N) je pocet clenov Zatvorkovej postupnosti a c(N) je pocet cifier cisla N (v desiatkovej sustave).
Velmi dolezita poznamka: Hodnotit budeme hlavne najdene cislo - velkost jeho podielu p(n)/c(n). Dolezite je, aby ste nam vase cislo aj zdovodnili (ukazali, ze uvedeny podiel je pren taky, aky uvadzate). Samozrejme nam poslite aj postup, akym ste k vysledku dospeli a ak ste pri tom pouzili cirou nahodou aj pocitac, tak aj program s prislusnym popisom.
Priklad:
Napriklad, pre cislo 7 vyzera Zatvorkova postupnost takto: 7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
Teda, p(N) = 17; c(N) = 1
5. Zrazene vlaciky
V Zmrzlinove to maju tazke. Nielen, ze je tam velka zima ludom, ale dokonca aj vlacikom. A tak sa taky vlacik radsej stale pohybuje a nikomu nezastavuje, aby neprechladol alebo nezmrzol. Ked je vlacik maly, mama mu vzdy hovori, kade ma chodit, aby sa nestratil. A ked vlacik vyrastie a mama uz nanho nema cas, tak si uz svoju trasu pamata a chodi po nej stale dookola aj bez maminej pomoci. Boji sa vsak toho, ze donho nejaky iny vlacik narazi. Vtedy je zle a treba ist do opravy, co je pre vlaciky asi take neprijemne ako je pre ludi chodenie k zubarovi. Alebo mozno este neprijemnejsie.
Uloha: Zmrzlinovo je obdlznikova krajina o rozmeroch 80x25. Napiste program, ktory najskor nacita pocet vlacikov N a postupne pre k azdy vlacik jeho dlzku D, farbu F a jeho okruznu trasu. Okruzna trasa je dana postupne suradnicami policok v Zmrzlinove, ktore musia susedit hranou (zaroven susedia hranou prve a posledne zadane policko). Potom vas program na prve az D-te policko trasy umiestni vlacik farby F, teda ho vykresli na obrazovku. Po vykresleni vsetkych vlacikov sa zacnu naraz rovnakou rychlostou pohybovat po zadanych trasach stale dookola dovtedy, az kym sa nejake vlaciky zrazia.
(C) 1996, Organizers of the CSP
