- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Príklady 1. kola letnej časti 20.ročníka KSP-Z
Milé naše riešiteľky, mílí naši riešitelia,
dostávajú sa vám do rúk zadania letnej časti XX. ročníka KSP-Z. Prečítajte si pozorne propozície súťaže a hor sa riešiť. Svoje riešenia nám posielajte najneskôr do 21. apríla 2003. Nezabudnite k nim priložiť známky v hodnote 15,- Sk.
KSPáci
1. Zúfalý poštár
(15 bodov)
Na jednom zabudnutom ostrove kdesi uprostred oceánu žijú v malých mestečkách trpaslíci. Majú sa dobre, veď im skoro nič ku šťastiu nechýba. Až na jednu maličkosť: poštu. Teda, nie že by nikdy nemali poštu, ale holubom, ktorých používali, sa zachcelo slobody a nechali trpaslíkov osamote. Preto sa Veľká Rada Trpaslíkov rozhodla postaviť v jednom mestečku centrálnu poštu a poveriť jedného trpaslíka roznášaním pošty po celom ostrove.
Mestečká na ostrove sú všetky vzájomne pospájané chodníkmi, ale medzi ľubovolnými dvoma vedie len jedna cesta, buď priamo alebo cez niekoľko iných miest. (Uvedomte si, že chodníkov je potom nutne o jeden menej ako miest.) Vzdialenosťou dvoch miest trpaslíci nazývajú počet chodníkov, po ktorých treba prejsť (ešte nezistili, že chodníky nemajú rovnakú dĺžku, takže krátky chodník je pre nich rovnako dlhý ako dlhý chodník). A keďže poštár je hrozne lenivý, rozhodol sa, že centrálnu poštu treba postaviť v takom meste, z ktorého je cesta do najvzdialenejšieho mesta najkratšia možná. Ale ktoré mesto je to správne?
Úloha
Pomôžte poštárovi a nájdite mu mesto, z ktorého je cesta do najvzdialenejšieho mesta najkratšia možná. (Keby sme pre každé mesto spočítali vzdialenosti do všetkých ostatných a zapamätali si z nich tú najväčšiu, hľadané mesto je to, pre ktoré si pamätáme najmenšiu hodnotu.) V prípade, že viacero miest spĺňa túto podmienku, vašou úlohou je nájsť všetky.
Ostrov má N miest očíslovaných 1...N a N-1 chodníkov, pričom chodník je zadaný dvoma mestami, ktoré spája.
Príklad
Vstup
N=8
chodníky:
(1,3) (8,4) (2,4) (4,5) (6,7) (3,7) (3,4)
Výstup
Poštu treba postaviť v meste 3.
2. Záh(r)adná párty
(15 bodov)
Tma... Nič len tma... Zrazu silná žiara vychádzajúca odniekiaľ z výšky... A k tomu ten zláštny zvuk... ako keby okolo lietali státisíce netopierov... Z hradu sa vynorila postava, zahalená v tmavom plášti, a v rukách držala...
"Vitajte!", ozvalo sa z miesta, kde ešte pred chvíľkou bola tá tajomná postava. Teraz tam stál Rúfus, dvorný sluha Jej veličenstva Kráľovnej, a v rukách držal zaprášenú drevenú truhlicu. Položil ju na zem a otvoril. Na prekvapenie všetkých prítomných z truhlice začali vyliezať rôznofarební škriatkovia, rôznofarební jednorožci a jednofarební pavúci. Škriatkovia majú svetlé farby: jeden je žltý, tamten je oranžový, tam stojí skupinka svetlomodrých, a ešte veľa iných farieb... Zato jednorožci sú tmavší – tam zelený, tam hnedý, alebo fialový\dots A pavúci – tí sú všetci šedí.
Ako na povel sa všetci – pavúci, škriatkovia a jednorožci – zoradili v náhodnom poradí do jedného dlhého radu na hraciu plochu, ktorá sa z ničoho nič objavila v záhrade – vyzerá ako dlhý štvorčekovaný papier. "Komu sa podarí zoradiť tieto bytosti na hracej ploche tak, aby na začiatku stáli vedľa seba všetci škriatkovia, potom všetci pavúci a na druhej strane všetci jednorožci, získa poklad ukrytý niekde v hlbinách hradu!", zvolal Rúfus.
Úloha
Skúste vyriešiť túto úlohu. Škriatkov budeme označovať písmenkami A...Z – každú farbu jedným písmenkom. Podobne jednorožcov budeme označovať číslami A...Z, a nakoniec pavúkov budeme označovať bodkou. Rozostavenie bytostí na hracej ploche je dané počtom bytostí N a poľom dĺžky N, obsahujúcim znaky ., A...Z a A...Z, ktoré určujú, aká bytosť stojí na ktorom políčku hracej plochy. Váš program má toto pole preusporiadať tak, aby na jeho začiatku boli všetky písmenká, potom všetky bodky a na konci všetky čísla.
Poznámka
Pokúste sa pri riešení nepoužiť pomocné pole.
Príklad
Vstup
N=13
A= 7 C . 1 A . F 4 . X . 5 A
Výstup
A= A X C A F . . . . 1 4 7 5
3. Zamotaný Santo
(15 bodov)
Pri potulkách v okolí Vyšnej Klondiky s virgulou v ruke narazil Santo na zlatú žilu. Rozhodol sa, že parcelu so zlatou žilou od mesta odkúpi a rozbehne na nej výnosný zlatokopecký biznis. Na to, aby parcelu mohol odkúpiť, treba ju najskôr presne vymerať, t.j. zatĺcť do jej rohov drevené kolíky a susedné pospájať špagátom. Navyše parcela musí byť tvaru konvexného mnoholníka, iné tvary totiž mestskí úradníci nemajú radi.
Santo teda zatĺkol do zeme niekoľko kolíkov. Potom natiahol špagát medzi prvým a druhým kolíkom, druhým a tretím atď. a ešte medzi posledným a prvým. Santo je však veľký moták a preto nevie, či špagát tvorí obvod konvexného mnohouholníka.
Úloha
Kolík chápeme ako bod v rovine a kusy špagátu ako úsečky, špagát tvorí uzavretú lomenú čiaru. Dané je N – počet kolíkov a ich súradnice xi,yi (1 <=i <= N). Zistite, či špagát omotaný okolo kolíkov v zadanom poradí tvorí hranicu konvexného N-uholníka.
Aby špagát tvoril obvod mnohouholníka (nie nutne konvexného), nesmie sám seba pretínať. Mnohouholník (chapaný aj s jeho vnútrom) je konvexný, ak pre ľubovoľné 2 jeho body v ňom leží aj celá úsečka, ktorá ich spája.
Príklad
Vstup
N=8
kolíky:
0,0 2,0 2,1 1,1 1,-1 3,-1 3,2 0,2
Výstup
Nie, špagáty sa pretínajú.
4. Zaujímavý mrakodrap
(15 bodov)
V Novom Yorku stojí vysoký mrakodrap (Kedysi tam boli ešte dva vyššie, ale akýsi dobrák ich zhodil dolu.) Empire State Building. Ten mrakodrap má veľa poschodí. Je ich až tak veľa, že ich nikto nezrátal. Ba ešte viac! (Pre naše účely možno povedať, že ich je nekončne veľa.)
V tom mrakodrape je rýchlovýťah, v ktorom sú dve tlačítka. Na jednom je napísané kladné celé číslo a na druhom celé záporné. Keď človek stlačí tlačítko s kladným číslom, pohne sa výťah o príslušný počet poschodí hore, ak stlačí tlačítko so záporným číslom, pohne sa o príslušný počet poschodí dolu (ak môže).
Ak sa chce človek dostať z prízemia na nejaké poschodie, postupne stláča tlačítka, až kým sa nedostane tam, kam mal namierené. Na niektoré poschodia sa však nemusí dať dostať – vtedy človek musí vyšľapať alebo zošľapať niekoľko poschodí po svojich.
Úloha
Dané sú dve celé čísla a a b – čísla na tlačítkach vo výťahu, pričom a je kladné a b je záporné, a tretie nezáporné celé číslo c – poschodie, na ktoré sa chceme dostať. Zistite, koľkokrát treba stlačiť ktoré tlačítko, aby sme museli ísť po schodoch (či už hore alebo dole) čo najmenej. (Ak je takých možností viac, vypíšte ľubovoľnú z nich.)
Príklad
Vstup
a=+14
b=-10
c=5
Výstup
Prvé tlačítko treba stlačiť 6-krát a druhé 8-krát a potom vyšľapať 1 poschodie.
5. Zaneprázdnené múzy
(15 bodov)
Život múz nie je jednoduchý. Každú chvíľu ich vzýva nejaký básnik alebo muž-romantik, a či chcú, či nechcú, musia za nich vymýšľať básne. Už ich to pomaly prestáva baviť. Vždy sa natrápia a nakoniec žiadna vďaka. Básnik tak nanajvýš spomenie, že ho kopla múza. Aj keď múzy pochádzajú zo staroveku, rozhodli sa, že vyskúšajú moderné prostriedky. Kúpili si počítač, a teraz sedia a rozmýšľajú, ako napísať taký program, aby vymýšľal básne za ne. Príliš im to nejde, vedia totiž rozmýšľať len vo veršoch a uznajte, kto kedy videl rýmovaný program!
Úloha
Vašou úlohou je napísať program, ktorý na vstupe dostane číslo N, reťazec písmen s a vypíše básničku, ktorá bude mať N veršov. Váš program by mal pri každom spustení vypísať inú (náhodnú) básničku. Bolo by dobré, keby sa programu dal na vstupe zadať aj druh rýmu, ktorý má v básni použiť. Spolu s riešením nám pošlite aspoň dve najoriginálnejšie básničky, ktoré váš program vytvoril.
Príklad
Vstup #1
N=2
rým=aa
Výstup #1
Vševedko išiel cez riečku
preskakoval tam ovečku.
Vstup #2
N=12
rým=aa
Výstup #2
Našiel Jožko ihlu, nite
a čo spravil -- uvidíte.
Prvý začal hromžiť tata:
"Nemôžem vliezť do kabáta!"
Potom zasa mama kuká:
"Kde mám otvor do klobúka?"
Dedko kričí: "To je veľa!"
Kto ma prišil do fotela?
Nevprace sa tetka, strýc,
do sukne a nohavíc.
Iba Jožko zúbky cerí:
"Už niet v dome ani diery!"
Poznámka
Prvá básnička: Nikolaj Nosov: Nevedkove dobrodružstvá, druhá básnička: Krista Bendová: Ako Jožko Pletko pozašíval všetko.
(c) 13. Marca 2002 webmaster
