- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Príklady 2. kola zimnej časti 20.ročníka KSP-Z
Milé deti,
Práve sa vám dostali do rúk zadania druhého kola KSP-Z. Podľa poradia po tomto kole budeme pozývať účastníkov na jarné sústredenie. Preto zapojte všetky svoje mozgové bunky a s chuťou sa vrhnite do riešenia nových piatich úloh, ktoré sme pre vás pripravili. Svoje riešenia nám posielajte do 6. januára 2003 a nezabudnite priložiť známky v hodnote 15 Sk,-.
KSPáci
1. Zememerači v Kiribati
(15 bodov)
Ako všetci iste viete, Kiribati je veľmi veľké súostrovie. Je také veľké, že ani samotný kráľ nemá prehľad o tom, aké veľké sú jednotlivé ostrovy a ani koľko kilometrov morského pobrežia majú. No a keďže taký kráľ neznesie predstavu, že nepozná velkosť svojho kráľovstva, rozhodol sa tam poslať zememeračov. Nanešťastie zistil, že v krajine žiadni zememerači nie sú. Preto mu musíte pomôcť vy.
Úloha
Na vstupe sú rozmery mapy Kiribati N x M, súradnice jedného políčka na mape [Px, Py] a samotná mapa s N stĺpcami a M riadkami, pričom v j-tom riadku a i-tom stĺpci je 0 ak je na políčku [i, j] voda a 1 ak je tam zem. Všade na okraji mapy (t. j. na políčkach so súradnicami [1, j], [N, j], [i, 1] a [i, M] pre všetky i,j) je voda. Voda sa dá rozdeliť na niekoľko (možno 0) jazier a more. More je tá súvislá (Dve políčka susedia práve vtedy, keď majú spoločnú hranu.) vodná plocha, do ktorej patria políčka na okraji mapy.
Vašou úlohou je zistiť plochu ostrova na ktorom políčko [Px, Py] leží a dĺžku jeho morského (Nezabudnite, že na ostrove môžu byť aj jazerá a také jazero už nie je more.) pobrežia. Pod dĺžkou morského pobrežia rozumieme počet políčok ostrova, ktoré susedia s morom. Možete predpokladať, že políčko [Px, Py] leží na nejakom ostrove.
Príklad
Vstup
N = 16
M = 10
P_x = 6
P_y = 4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Výstup
Plocha ostrova je 31.
Dĺžka morského pobrežia ostrova je 23.
Všimnite si, že na našom ostrove je jazero, v ktorom je ďalší ostrov. Ak by sme sa pýtali na dĺžku morského pobrežia tohto malého ostrova, odpoveď by bola 0, pretože všede okolo neho je jazero.)
2. Z gaštanov II
(13 bodov)
Miško sa znova nudil na prednáškach, a tak sa rozhodol stavať ďalšie figúrky. Priniesol si hŕbu gaštanov, avšak zistil, že už nemá zápalky na ich spájanie. Tak sa rozhodol, že vyberie z predchádzajúcich figúrok tie zápalky, ktoré nie sú potrebné na to, aby držali figúrku dokopy. Pomôžte Miškovi zistiť, koľko najviac zápaliek môže odobrať bez toho, aby sa hociktorá z jeho figúriek rozpadla.
Úloha
Napíšte program, ktorý načíta N – počet gaštanov (sú očíslované od 1 do N), M - počet spojení zápalkami a zoznam dvojíc čísel gaštanov, ktoré sú navzájom spojené zápalkou. Váš program má vypísať najväčší počet zápaliek, ktoré môže Miško zo svojich figúriek odobrať.
Príklad
Vstup
N=4, M=4
1 2
2 3
3 1
1 4
Výstup
Miško môže odobrať 1 zápalku.
(a to 1-2, 2-3 alebo 3-1)
3. Zvianočnieva sa II
(15 bodov)
Minulé kolo ste pomohli Paľkovi prepchať stromček do jeho obývačky, za čo je vám veľmi vďačný. No ale ihneď ako sa pokochal pohľadom na stromček, zistil, že stromček mu zaberá polovicu obývačky. Tak si povedal, že stromček postaví ku stene. Nepomohlo. Vtedy si však uvedomil, že keď je stromček pri stene, aj tak z neho nie je vidieť zadnú časť. Keby z neho odpílil zadné vetvy, dal by sa stromček prisunúť bližšie k stene a vyzeral by stále rovnako.
Preto sa rozhodol, že zo stromčeka ureže zadnú časť a stromček postaví ku stene tak, aby sa jeho kmeň dotýkal steny. Ale teraz nevie, ktorú polovicu stromčeka urezať, pretože by chcel, aby mu ostal čo najkrajší stromček, teda aby mu ostalo čo najviac konárov. S tým sa ale znovu obrátil na svojich dobrých kamarátov (teda na vás), aby mu pomohli.
Úloha
Na stromček sa budeme pozerať zhora. Zhora kmeň vyzerá ako bod, z ktorého vychádzajú do strán konáre (viď obrázok). Kmeň sa nachádza v začiatku súradnicovej sústavy. Konáre budú úsečky vychádzajúce z kmeňa, teda z bodu [0,0] a budeme ich reprezentovať ich koncovým bodom. Stena bude priamka prechádzajúca začiatkom súradnicovej sústavy. Vašou úlohou je napísať program, ktorý na vstupe dostane číslo N – počet konárov a súradnice ich koncových bodov a nájde takú priamku prechádzajúcu začiatkom súradnicovej sústavy, ktorá konáre rozdelí na dve časti tak, aby v jednej časti ostal najväčší možný počet konárov. Ak existuje viac riešení, vypíšte ľubovoľné z nich. Konáre ležiace na priamke predstavujúcej stenu neodpílime.
Príklad
Vstup
N=6
[1,3]
[-3,1]
[-2,3]
[2,2]
[2,-2]
[1,-3]
Výstup
(Jedno z možných riešení)
Stena prechádza bodom [3, 1].
Na stromčeku ostanú 4 vetvy.
4. Žužu žuje žuvačku
(15 bodov)
Žužu opravoval riešenia KSP. Keďže chcel dať všetkým veľa bodov, bol si kúpiť cukríky. (Za každý cukrík v jeho ústach bol totiž bod navyše – vy ste nečítali vzoráky?) Došiel do bufetu. Na poličke uvidel veľký výber cukríkov. Mali tam cukríky za jednu korunu, za dve koruny, za tri,... Keď sa Žužu poobzeral, zistil, že ceny cukríkov sú vlastne práve všetky celé kladné (Bol smutný, že nie všetky nezáporné...) čísla, za každú cenu predávajú práve jeden druh cukríkov.
Rozhodol sa, že za všetky svoje úspory, ktoré činili práve N korún, si nakúpi cukríky. Potom dlho rozmýšľal, aké možnosti vlastne má. A aby nabudúce nerozmýšľal tak dlho, potrebuje ich zoznam.
Na vstupe je zadané N – počet korún, ktoré má Žužu vo vrecku. Vašou úlohou je vypísať všetky možnosti (každú práve raz!), cukríky akých cien si môže Žužu za svoje peniaze nakúpiť. Každú možnosť vypíšte ako postupnosť cien jednotlivých cukríkov. Celkový súčet týchto cien má byť N. Samozrejme je jedno, v akom poradí si cukríky kúpi, teda možnosti líšiace sa iba zmenou poradia cien cukríkov považujte za rovnaké.
Príklad
Vstup
N=5
Výstup
5 4 1 3 1 1 2 1 1 1 1 1 1 1 1 3 2 2 2 1
5. Zárm Oded
(15 bodov)
Programátori v Softvérovom Družstve sa rozhodli, že pred Vianocami ešte predsa niečo naprogramujú (a zarobia si tak na darčeky). Zákazník, ktorý sa ale odmietol predstaviť skutočným menom a predstavil sa ako Zárm Oded, chcel iba jednoduchý program na evidenciu adries a zásielok, ktoré sa na ne majú doručiť. Vraj to má niečo s vianočnými darčekmi. V SoDr sa potešili a rýchlo ho naprogramovali, však to nebolo nič ťažké. A už-už to aj chceli poslať, keď si uvedomili, že im chýba tá najdôležitejšia vec – SplashScreen. To je taký ten otravný obrázoček, ktorý sa objaví na obrazovke, kým sa program spúšťa.
To ale nie je až také jednoduché. Zákazníkove počítače totiž fungujú len v textovom móde a ešte k tomu má každý inú veľkosť obrazovky (teda počet znakov v riadku a stĺpci). V SoDr sa rozhodli, že vzhľadom na zameranie programu bude najlepším obrázkom vianočný stromček a tak teraz stoja pred problémom, ako ho v textovom móde nakresliť pre rôzne veľkosti obrazovky.
Napíšte program, ktorý pre zadanú výšku M a šírku N obrazovky a počet vetiev P nakreslí čo najkrajší vianočný stromček. Vianočný stromček musí pozostávať zo zvislej časti t.j. kmeňa a z P dvojíc vodorovných, alebo šikmých vetiev, ktoré z neho vyrastajú. Pošlite aj výstup vášho programu pre (N=20, M=10, P=3), (N=20, M=25, P=7) a (N=80, M=25, P=5).
Príklad
Vstup
N=20, M=10, P=3
Výstup
(Možný stromček aj s pár vianočnými guľami :-)
v
-_ I _-
_ o --I-- o _
--_ I _--
--_ o --I-- o _--
o ----_ I _---- o
---I---
I
fvl
(c) 14. Novembra 2002 webmaster
