• KSP
• • Home
  • Novinky
  • Pravidlá
  • FAQ
  • Kuchárka
  • Liaheň
• Séria
• • Zadania a výsledky
  • Odovzdaj riešenie
  • Ideálne riešenie
  • Archív zadaní
  • Zbierka
• Akcie
• • Sústredenia
  • Proboje
  • Akadémia a klub
  • LTT
• Ostatné
• • Podporte nás
    2% z daní
  • Organizátori
  • Sponzori
  • Kontakt
• Iné semináre
• • Trojsten
  • KMS
  • FKS
  • Iné súťaže

Korešpondenčný seminár z programovania

Priklady 3. kola

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

• 1. O snazivom Tomasovi
• 2. O Stevovej navsteve v Indii
• 3. O Kiribatskych naleziskach
• 4. O telefonnom viruse
• 5. O SoDr a meteorologoch

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)