- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Príklady 1. kola letnej časti 21. ročníka KSP-Z
Milí riešitelia!
Vítame vás v letnej časti KSP, ktorá práve pomaly ale isto začína. A veríme, že podobne, ako sa dočkáme jari, dočkáme sa aj kopy riešení od vás. Neváhajte a zapojte sa – prvých niekoľko riešiteľov čakajú vecné ceny, s najlepšími riešiteľmi sa stretneme na skvelom týždňovom sústredení a ak aj neuspejete, aspoň sa naučíte mnoho vecí, ktoré sa vám ešte v živote zídu. Zapojiť sa môžu aj tí, ktorí KSP v zime neriešili, nebudú nijako znevýhodnení.
Riešenia tohto kola nám posielajte do 15. marca 2004 a nezabudnite priložiť pár známok v hodnote okolo 15 korún, nech vám ich máme za čo poslať späť opravené.
KSPáci
- Zozolvár najväčší v okolí
- Z krajiny Lemmingov
- Zeofína v záhrade
- Zúfalo hladný Janko
- Zo sveta steganografie
1. Zozolvár najväčší v okolí
(15 bodov)
Kde bolo, tam bolo, stál raz jeden hrad. Ten hrad mal vežu a nádvorie. Na nádvorí stálo v rade N bohatierov, ktorých výšky boli navzájom rôzne reálne čísla. Hovoríme, že bohatier sa hrozivo týči, ak je vyšší od všetkých (T.j. jedného (ak stojí na niektorom konci radu) alebo dvoch (inak).) svojich susedov.
Princezná (ktorá celé dni sedí vo veži a zúfalo sa nudí) často hrávala so svojou komornou nasledovnú hru: Komorná sa nesmie pozerať z okna, môže sa iba pýtať na výšky jednotlivých bohatierov. Jej úlohou je zistiť o aspoň jednom bohatierovi, že sa hrozivo týči.
Úloha
Komorná však dnes má voľno a tak by sa princezná chcela zahrať svoju obľúbenú hru aspoň s dvorným počítačom. Napíšte program, ktorý načíta číslo N (počet bohatierov) a následne sa bude princeznej pýtať na výšky niektorých bohatierov. Úlohou programu je na čo najmenej otázok nájsť nejakého bohatiera, ktorý sa hrozivo týči.
Úloha
Komorná sa za dlhé roky hrania tak vypracovala, že aj pre 1000 bohatierov jej vždy stačilo menej ako 20 otázok. Vyrovná sa jej váš program?
Príklad
N=10
Počítač: Aká je výška 3. bohatiera?
Princezná: 190
Počítač: Aká je výška 5. bohatiera?
Princezná: 140
Počítač: Aká je výška 7. bohatiera?
Princezná: 147
Počítač: Aká je výška 6. bohatiera?
Princezná: 175
Počítač: Bohatier 6 sa hrozivo týči.
2. Z krajiny Lemmingov
(13 bodov)
Lemmingovia sú malí ľuďkovia vysokí asi tak pol centimetra. Napriek ich veľkosti radi stavajú interkontinentálne diaľnice, kopú tunely a stavajú mosty. Žijú v krajine plnej kopcov a dolín, kde sa majú možnosť vo svojich stavbárskych chúťkach plne realizovať. Aj teraz sa im zachcelo – radi by postavili ďalšiu diaľnicu. Samozrejme radi by diaľnicu postavil čo najlacnejšie. Ale keďže pri veľkosti ich mozgovní, nie je medzi nimi žiaden ekonóm, musíte im pomôcť vy.
Úloha
Daný je popis krajiny (kopcov a dolín), kde žijú Lemmingovia, ako bočný prierez. Dná dolín sú na úrovni mora a všetky kopce majú rovnakú výšku. Na vstupe je dané N – počet kopcov, H – ich výška a nakoniec 2N+1 pozícií dolín a kopcov – dolina, kopec, dolina, ..., kopec, dolina. (Pozri obrázok k príkladu.)
Lemmingovia chcú postaviť vodorovnú dialnicu naprieč krajinou v nejakej nadmorskej výške. Ak diaľnica prechádza cez kopec, treba cezeň prekopať tunel, ktorý v závislosti od jeho dĺžky d stojí d2 korún. Podobne je to s dolinami. Ak diaľnica prechádza ponad dolinu, tak treba ponad ňu postaviť most, ktorý v závislosti jeho dĺžky d a jeho nadmorkej výšky v stojí dv korún. Zistite nadmorskú výšku, v ktorej treba postaviť diaľnicu, aby náklady na jej stavbu boli minimálne.
Príklad
Vstup
N=3, H=1000
0, 800, 1000, 1100, 1300, 1600, 1900
Výstup
Optimálna výška je približne 432,8 metrov nad morom.
3. Zeofína v záhrade
(15 bodov)
Naša stará známa korytnačka Zeofína dlho oddychovala a darilo sa jej nachádzať si zábavky, pri ktorých nepotrebovala pomoc programátorov. Až teraz...
Rozhodla sa, že si vysadí celú záhradku trávou, aby mohla hrávať poobede golf. Najrýchlejšie riešenie sa jej zdalo kúpiť prefabrikovaný trávový koberec, ale ten sa predáva po štvorcových metroch. A jej záhradka je všeliaká, ale štvorcová rozhodne nie je. Má však (vďakabohu) všetky strany rovné, akurát že ich má hodne veľa. Zeofína sa rozhodla, že zistí, ako presne vlastne tá jej záhradka vyzerá, a potom poráta obsah. Tak zobrala do papuľky pero, do pravej prednej laby papier a sunie sa popri plote záhradky. Na papier si pritom zaznamenáva, ako sa hýbe, a to takto:
- dopredu k – pohla sa k korytnačích metrov dopredu (k je reálne),
- doprava u – otočila sa o u stupňov doprava,
- doľava u – otočila sa o u stupňov doľava
Teraz však prišla domov a zistila, že si už zo školy vôbec nepamätá vzorec na výpočet obsahu ľubovoľného n-uholníka (lebo zistila, že práve toľko vrcholov jej záhradka má). Tak jej neostáva nič iné, než požiadať vás o pomoc.
Úloha
Napíšte program, ktorý načíta postupnosť pohybov a vyráta Zeofíne, aký obsah má jej záhrada (v korytnačích metroch štvorcových). (1 korytnačí meter = 0.3048 metra. Nepoužívajte prosím skratku km.)
Príklad
Vstup
DOPREDU 10
DOPRAVA 90
DOPREDU 10
DOPRAVA 90
DOPREDU 5
DOPRAVA 90
DOPREDU 5
DOLAVA 90
DOPREDU 5
DOPRAVA 90
DOPREDU 5
Výstup
75
4. Zúfalo hladný Janko
(15 bodov)
Kôň Janko má toho už dosť! Lenivá Monika mu už druhý týžden nedoniesla obrok. Rozhodol sa, že od nej utečie a vydá sa hladať Dvanástich mesiačikov a ich slávne jahodové pole. Strašnou zimnou pľušťou, v ktorej mu omrzli všetky kopytá, sa predieral dlhé hodiny, kým ich našiel. Zaviedli ho do rohu jahodového poľa a dovolili mu preskákať krížom cez pole a cestou si pochutnať na jahodách, čo mu brucho stačí. Pomôžte koňovi Jankovi nazbierať po ceste co najviac jahôd!
Úloha
Na vstupe sú čísla N,M >= 5 – dlžka a šírka jahodového poľa. Nasleduje M riadkov a v každom riadku je N nezáporných celých čísel – počet jahôd, ktoré nájde na príslušnom štvorcovom metri poľa. Janko začína v ľavom hornom rohu poľa a skončiť má v jeho pravom dolnom rohu. Pohybuje sa samozrejme ako šachový kôň. Keďže cez pole stíha len prebehnúť, (Mesiac Lipeň, ktorý ho na pole pustil, nesmie vládnuť pridlho, aby sa neroztopil všetok sneh široko-ďaleko.) môže sa hýbať len tak, aby sa približoval do pravého dolného rohu – viď obrázok. Váš program by mal spočítať, koľko najviac jahôd môže Janko cestou zožrať.
(Smer, v ktorom sa hýbe o 2 políčka, musí byť doprava alebo dole.)
Príklad
Vstup
N=8, M=5
0 0 0 0 0 3 0 0 0 0 1 0 0 2 0 0 0 0 1 0 2 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 4 0 0 1
Výstup
Najviac zožerie 5 jahôd.
(Pôjde napr. po zvýraznených políčkach:
0 0 0 0 0 3 0 0
0 0 1 0 0 2 0 0
0 0 1 0 2 0 1 0
1 0 1 1 0 0 0 0
0 0 0 0 4 0 0 1
)
5. Zo sveta steganografie
(15 bodov)
Akiste všetci poznáte kryptografiu, ktorá skúma spôsoby, ako danú správu zašifrovať tak, aby sa k nej nik okrem adresáta nedostal. Kryptografia však nepredstavuje jedinú možnosť, ako preniesť utajovanú informáciu. Cestou k úspechu je skryť prenášanú informáciu tak, aby nikto okrem adresáta ani nezistil, že nejaká správa bola poslaná. Informáciu samozrejme musíme zamaskovať tak, aby vyzerala ako niečo iné – napríklad bloček od nákupu, obrázok alebo trebárs zadania KSP. Antickí Gréci prišli s prvými nápadmi, ako na to:
Zábavný nápad bol vytetovať správu otrokovi na oholenú hlavu, počkať kým mu vlasy narastú a poslať ho k adresátovi. Adresát mu znovu oholil hlavu a správu si prečítal. Časom boli samozrejme vymyslené aj ľahšie použiteľné metódy. Iste každý z vás už počul o rôznych neviditeľných atramentoch, však? Nezabúdajme ani na "motáky" – listy z väzenia, ktoré museli dostať informácie cez cenzúru tak, aby si cenzor nič nevšimol. Ak by väzeň použil šifru, cenzorovi by bol list podozrivý a zničil by ho.
Obráťme však list a poďme do súčasnosti, veku informácií v digitálnej podobe.
Pri skrývaní informácie môžeme použiť väčšinu postupov na skrývanie informácie v texte. Otvára sa nám však kopa nových možností. Len si treba uvedomiť, že informáciu môžeme skrývať aj do obrázkov, alebo trebárs aj do zvuku či videa. Napríklad v obrázku uloženom ako bitová mapa sú najnižšie bity natoľko bezvýznamné, že ich môžeme nahradiť čím chceme a rozdiel nebude pozorovateľný. Oko nerozozná rozdiel medzi farbou #FCFCFC a #FFFFFF, ale adresát dostane čo chcel.
Cieľom steganografie však zďaleka nie je iba prenášať tajné informácie s častokrát pochybným obsahom. Iné (legálne) použitie steganografie je digital watermarking – v obrázku, ktorý sme na počítači vytvorili, skryjeme informáciu, pomocou ktorej vieme dokázať, že sme ho naozaj vytvorili my.
Na záver už len dodáme, že častokrát aj v dátach, ktoré vyzerajú ako úplný šum, môže byť skrytá informácia. Ale samozrejme nemusí :-)
~~$3cb%J%omatfyz~~$3cb%J%omatfyz~~$3cb%J%omatfyz~~$3cb%J%omatfyz~~$3cb
45-.)usW/$!haluz45-.)usW/$!haluz45-.)usW/$!haluz45-.)usW/$!haluz45-.)u
_H^tu+nic_nie*je_H^tu+nic_nie*je_H^tu+nic_nie*je_H^tu+nic_nie*je_H^tu+
threedimensionalthreedimensioaltnhreedimensoaltnhreedimenisoaltnhreedi
MfH.5]#@d[:RlKSPMfH.5]#@d[:RKSPlMfH.5]#@d[:KSPlMfH.5]#@d[R:KSPlMfH.5]#
$byPwICkLf_haluz$byPwICkLf_aluhz$byPwICkLf_aluhz$byPwIkLfC_aluhz$byPwI
Uoto!^_ldtraaavaUoto!^_ldtaaarvaUoto!^_ldtaaarvaUoto!_ld^taaarvaUoto!_
Y:`!`eitYkalerabY:`!`eitYalekrab:`!Y`eitYalekrab:`!Yeit`Yalekrab:`!Yei
)$-_dJ|Q-wB4 KSP)$-_dJ|QwB4- KSP$-_)dJ|QwB4- KSP$-_dJ|)QwB4- KSP$-_dJ|
{8n-g]+9`traaava{8n-g]+`traaava{8n-g]9+`traaava{8ng]9-+`traaava{8ng]9-
k0=bU[s|_traaavak0=bU[s_traaavak0=bU[|s_traaavak0bU[=|s_traaavak0bU[=|
|3B^o]~{q}matfyz|3B^o]~{q}matfyz3B^|o]~{q}matfyzB^|3o]~{q}matfyzB^|3o]
1NQHC([G[kalerab1NQHC([G[kalerabNQH1C([G[kaleraNQHb1C([G[kaleraNQHb1C(
%|%tu+nic_nie*je%|%tu+nic_nie*je|%t%u+nic_nie*e|%jt%u+nic_nie*e|%jt%u+
threedimensionalthreedimensionalhretedimensioalhnretedimensioalhnreted
-![gV]$*gkalerab-![gV]$*gkalerab![g-V]$*gkalrabe![g-V]$*gkalrabe![g-V]
~@F='@n],p0haluz~@F='@n],p0haluz@F=~'@n],p0hluza@F=~'@n],p0hluza@F=~'@
threedimensionalthreedimensionalthreedimensionalthreedimensionalthreed
D(vK_j2!ha0haluzD(vK_j2!ha0haluzD(vK_j2!ha0haluzD(vK_j2!ha0haluzD(vK_j
-Gt V*/?yJmatfyz-Gt V*/?yJmatfyz-Gt V*/?yJmatfyz-Gt V*/?yJmatfyz-Gt V*
Tak čo, našli ste všetko? Naozaj všetko? Tak nám to pošlite...
© KSP, 12. február 2004, Misof
