Mili nasi riesitelia,
prinasame vam tohto roku uz predposlednu seriu uloh KSP. Svoje riesenia nam posielajte do 4. marca 1996 na horeuvedenu adresu.
Ako sa do lesa vola, tak sa z lesa ozyva
Ako iste vsetci viete, Tomas je velmi snazivy student, a preto ked boli zverejnene rozvrhy, rozhodol sa, ze si zapise najviac prednasok ako len moze. Dlho dumal nad rozvrhom a nic. Velmi sa preto trapi. Nikdy si nie je isty, ci rozvrh, ktory si vymyslel, ma najviac prednasok ako len moze mat. Za tyzden uz schudol 5 kil. Pomozte mu, nez bude mat zapornu hmotnost a niekam nam uleti.
Uloha: Napiste program, ktory nacita zaciatky a konce prednasok a vypise Tomasovi najvacsi pocet prednasok, ktore si moze zapisat (samozrejme nemoze prist na dve prednasky naraz, ani prist neskoro, ci odist priskoro z prednasky) spolu s prikladom takehoto rozvrhu.
Tvar vstupu: Kazda prednaska v tvare Pon 07:20-09:45 na novom riadku. Dni v tyzdni su Pon Uto Str Stv Pia, v sobotu a nedelu prednasky nie su.
Tvar vystupu:
Pocet prednasok v rozvrhu
Zoznam zapisanych prednasok, kazda na samostatnom riadku
Poznamka: Nezabudnite na dokaz spravnosti algoritmu.
Priklad:
Vstup: Vystup: Pon 07:20-09:45 2 Uto 09:30-10:00 Pon 07:20-09:45 Pon 09:00-10:35 Uto 09:30-10:00
Stevo sa potuloval svetom a ked uz bol v Azii, spomenul si, ze je hladny. Zastavil sa preto v dedine Maharazadziad. Prisiel do obchodu a chcel si kupit vela jedla na dalsiu cestu. Ked uz stal v rade vsimol si, ze na pokladni je napisane 1+1=10. Spociatku nevedel, co to znamena. No po chvili mu bolo vsetko jasne. ``V tomto obchde pocitaju v inej ciselnej sustave!'', skrikol Stevo. Tak bezal do dalsieho. Tam pocitali zasa v inej sustave. Na kazdom obchode bolo napisane vyraz tvaru A+B=C.
Stevo nalistoval zodpovedajucu stranu v svojej prirucke mladych svistov a zistil, ze takyto vyraz sluzi na urcenie ciselnej sustavy, v ktorej sa v danom obchode pocita. Stevo nevie po indicky, preto v obchode nakupuje tak, ze ukaze, co chce a na papier napise, kolko toho chce. Na to vsak potrebuje vediet, v akej sustave sa v danom obchode pocita. Ked to nezisti, je odsudeny na smrt vyhladovanim.
Uloha: Napiste program, ktory zisti, v ktorych ciselnych sustavach plati A + B = C.
Priklad: Vstup: 1+1=10 Vystup: 2
Na Kiribatskych ostrovoch nedavno objavili pod zemou velke zasoby rumu. Inzinieri navrhli miesta, kde postavit vrtne veze, problemom vsak je preprava rumu z tychto vezi. Spolocnost, ktora rumove polia vlastni sa rozhodla postavit jednu velku ruru iducu cez cele pole z vychodu na zapad a ku kazdej vezi postavit pripojku k tejto velkej rure. Kam ale postavit velku ruru, aby sa na pripojky minulo co najmenej materialu? Nad tym treba veru triezvo pouvazovat!
Uloha: Napiste program, ktory nacita N - pocet taznych vezi, suradnice jednotlivych taznych vezi a vypise y-ovu suradnicu kam postavit velku ruru, tak, aby sucet dlzok pripojok bol minimalny.
Priklad:
Vstup: Vystup: 5 17 10 1 15 20 20 17 10 7 10 10
Virus Prepheeckunecz, ktory infikuje moderne telefony, vzdy v piatok poprehadzuje vyznam tlacitiek telefonu, t.j. napriklad po stlaceni 1 sa vytoci cislo 5 a podobne, pricom je vsak telefon schopny vytocit ktorekolvek cislo.
Kazdy majitel telefonu ma nastastie svoj sukromny telefonny zoznam, na zaklade ktoreho moze zistit, ako su tlacitka poprehadzovane a to tak, ze vytaca rozne cisla a podla toho, kto sa mu ozve zisti, ake cislo vlastne vytocil.
Uloha: Napiste program, ktory na co najmenej vytoceni zisti, ako su poprehadzovane tlacitka telefonu. Program ma k dispozicii funkciu vytoc(st:string):integer, ktora dostane na vstupe vytacane cislo (v poprehadzovanych tlacitkach) a vrati bud cislo volanej osoby, alebo 0, ak osoba s takym (spravnym) cislom nie je v sukromnom telefonnom zozname. Telefonny zoznam mate k dispozicii ako pole TZ[1..N_TZ], kde TZ[i] je (spravne) telefonne cislo osoby i. Ak nie je mozne zistit poprehadzovanie tlacitok, vypiste o tom spravu.
Priklad:
Cisla su prehadzane takto: (2,3,5,0,9,1,8,4,6,7)
Zoznam obsahuje cisla: [123,456,7890]
Mozny postup vytacania:
vytoc('350') vrati 1
vytoc('918') vrati 2
vytoc('4672') vrati 3
vytoc('123') vrati 0 (lebo neexistuje nikto sa cislom 501)
V softferovom druzstve maju najnovsie klientov --- meteorologov. Taky meteorolog ked pride k pocitacu, chcel by vediet, v akom rozmedzi uhlov v poslednych n minutach fukal vietor. Vysledok merania smeru vetra je k dispozicii kazdu minutu (zadava sa v stupnoch).
Dolezita poznamka: Rozmedzie uhlov mozno urcit len ako suvisly obluk. Obluk je urceny dvoma cislami a a b, ktore urcuju hranice obluku. Orientacia obluku je v protismere hodinovych ruciciek od a k b. Napriklad obluk (0,90) urcuje stvrtkruh a obluk (90,0) tristvrtkruh.
Uloha: Na vstupe su cisla n, k a n+k celych cisel z intervalu [0,360), ktore su vysledkami merani postupne v casoch 1,2,...,n+k. Napiste program, ktory vypise rozmedzia uhlov pre casy n,n+1,...,n+k vzdy za poslednych n minut. Mozete predpokladat, ze k je aspon 3.
Priklad:
Vstup: n=3, k=3, merania: 0,30,60,90,120,150
Vystup: (0,60) (30,90) (60,120) (90,150)