• 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

Príklady 1. kola zimnej časti 20. ročníka KSP

Milé naše riešiteľky, mílí naši riešitelia,

dostávajú sa vám do rúk zadania XX. ročníka KSP. Prečítajte si pozorne pravidlá súťaže a hor sa riešiť. V prípade, že riešite KSP po prvý raz, odporúčame vám začať s kategóriou KSP-Z. Svoje riešenia nám posielajte najneskôr do 21. októbra 2002. Nezabudnite k nim priložiť známky v hodnote 15,- Sk.

1. O telocviku II
2. O metre
3. O telegrafnej sieti
4. O diamantoch
5. O celulárnych automatoch I

---

1. O telocviku II

(13 bodov)

Na jednej nemenovanej škole učí ujo Marián telocvik. Býva veľmi zúrivý. Na začiatku každej hodiny sa musia žiaci zoradiť podľa veľkosti a podať hlásenie. Keby sa náhodou stalo, že sú zoradení zle, pocítia jeho besný hnev.

Zvyčajne sa však žiaci postavia v rozhádzanom poradí. Keď zbadajú uja Mariána vo dverách telocvične, začnú sa rýchlo po dvojiciach vymieňať. Vašou úlohou je zistiť, na koľko najmenej výmen sa môžu žiaci utriediť podľa veľkosti.

Úloha

Je dané číslo N - počet žiakov a výšky N žiakov v tom poradí, v akom stoja pred príchodom uja Mariána (všetky výšky sú navzájom rôzne). Vašou úlohou je vypísať najkratšiu postupnosť dvojíc výšok žiakov, ktorí sa majú vymeniť tak, aby nakoniec skončili žiaci v utriedenom poradí, od najnižšieho po najvyššieho.

Príklad

Vstup
N=7
152, 151, 147, 185, 156, 174, 179

Výstup
Najmenší počet výmen je 4.

(174, 179)
(147, 152)
(156, 185)
(174, 185)

(Po prvej výmene budú v poradí 152, 151, 147, 185, 156, 179, 174, po druhej v poradí 147, 151, 152, 185, 156, 179, 174, po tretej 147, 151, 152, 156, 185, 179, 174 a po štvrtej skončia v utriedenom poradí. Správnych postupností (dĺžky 4) je viacero, stačí vypísať jednu. )

---

2. O metre

(13 bodov)

"Z Hornej-Dolnej do Dolnej-Hornej za menej ako 12 minút! Z Ľavej-Pravej do Pravej-Ľavej dvakrát rýchlejšie!" Čo sa to deje? Známa firma Tunelár a syn dostala novú zákazku - postaviť ultramoderné superrýchle metro. (Zlé jazyky hovoria, že nové pražské...) Napriek tomu, že ešte nebol vykopaný (ba dokonca ani len naplánovaný) ani jediný meter tunelov, propagačné oddelenie už vyrobilo všetky druhy manuálov (pre budúcich vodičov) a rôznych reklamných materiálov (pre izolantov (Ako určite viete z fyziky, izolant je nevodič)).

Z nich sa možno dozvedieť, ako to nové metro bude vyzerať. Výstavba začala tým, že v meste postavili N staníc metra na rôznych významných miestach. Až potom si hlavný projektant uvedomil, že trasa metra nesmie mať žiadne zákruty (inak by sa nedala dosiahnuť taká neuveriteľná rýchlosť), a teda na pláne bude zaznačená ako veľmi dlhá úsečka, ba priam až priamka. Všetky postavené zastávky však ani omylom neležali na jednej priamke. Hlavný projektant však našiel riešenie - keď už bude metro postavené, každá stanica sa k trase metra pripojí pohyblivými schodami, vedúcimi zo stanice ku metru (kolmo na jeho dráhu).

Manuály a reklamné materiály sú však už dávno na svete, a čo čert nechcel, je v nich už uvedené poradie zastávok na trati metra. A projektanti teraz stoja pred takmer nemožnou úlohou - navrhnúť dráhu metra tak, aby zastávky na nej boli v poradí uvedenom v manuáloch. A keďže ich už nič nenapadá, požiadali o pomoc vás.

Úloha

Je daný N - počet staníc a ich súradnice v poradí, v akom sú v manuáloch. Vašou úlohou je zistiť, či je možné postaviť takú trať (priamku), aby traťové zastávky (do ktorych vedú pohyblivé schody zo staníc) na trati boli v rovnakom poradí ako v manuáloch. Ak žiadna vhodná trať neexistuje, váš program by o tom mal podať správu, inak treba nejakú vhodnú trať aj nájsť.

Príklad

Vstup
N=4
súradnice:
[0,0], [3,0], [2,4], [8,3]

Výstup
Trať má všeobecnú rovnicu 2y - x - 4 = 0.
(Samozrejme, existuje aj veľa iných riešení.)

---

3. O telegrafnej sieti

(16 bodov)

V Zimbabwe sa rozhodli vybudovať telegrafnú sieť. Postavili si preto po celej krajine sieť telegrafných staníc. No a tieto telegrafné stanice potom pospájali drôtmi všemožnými spôsobmi a s radosťou zistili, že medzi každými dvomi stanicami by sa vedeli dovolať, keby...

Tu ale nastal veľký problém. Nezostali totiž drôty na vybudovanie elektrickej siete na napájanie všetkých tých telegrafných staníc. Jediné riešenie je použiť niektoré drôty, ktoré už sú v telegrafnej sieti. Telegrafisti teda povolili elektrikárom odpojiť niektoré drôty, ale tak, aby sa stále dalo telegrafovať medzi každými dvomi stanicami.

Elektrikári však potrebovali veľa drôtov, preto sa rozhodli, že telegrafistom nechajú najmenší možný počet drôtov. A čo viac, potrebujú dlhé drôty, preto najlepšie bude nechať telegrafistom také drôty, ktorých súčet dĺžok bude najmenší možný.

Toto sa však nepáčilo telegrafistom (ktorí tajne dúfali, že prebytočné konce drôtov odrežú a odnesú do zberu). Lenže v to isté tajne dúfali aj elektrikári a tak ľahko sa nedali. Navyše vyjednávanie im šlo omnoho lepšie ako telegrafistom. Po hodinách rokovaní nakoniec dospeli k dohode: Nechajú telegrafistom také drôty, aby súčet ich dĺžok bol nie najmenší možný, ale druhý najmenší. Stoja však teraz pred spoločnou dilemou -- ktoré drôty vlastne majú odmontovať?

Úloha

Na vstupe sú celé čísla N - počet telegrafných staníc, M - počet prepojení. Ďalej nasleduje M trojíc a_i, b_i, l_i (pre i=1, 2, ..., M) s významom "stanica a_i je prepojená so stanicou b_i drôtom dĺžky l_i", pričom medzi každými dvomi stanicami vedie najviac jeden drôt a pre jednoduchosť predpokladáme, že drôty majú navzájom rôzne dĺžky. Úlohou je zistiť, ktoré drôty treba odpojiť, pričom požadujeme:

• Po neodpojených drôtoch sa musí dať telegrafovať medzi každými dvoma stanicami.
• Musíme odpojiť maximálny možný počet drôtov.
• Súčet dĺžok drôtov, ktoré neodpojíme, má byť druhý najmenší možný.

Príklad

Vstup
N=4, M=5
spojenia:

(1,2,13)
(1,3,12)
(2,3,7)
(2,4,47)
(3,4,10)

Výstup
Treba odpojit drôty (1,3) a (2,4).

(Ostanú drôty s celkovou dĺžkou 30. Viac ako dva drôty sa zjavne odpojiť nedá, jediný spôsob, ako odpojiť dva drôty a nechať telegrafistom menej je odpojiť drôty (1,2) a (2,4) - ostanú drôty s celkovou dĺžkou 29.)

---

4. O diamantoch

(15+ bodov)

Kráľ Kleofáš XXXXVII. zbožňoval diamanty. Bolo nimi vyložené jeho žezlo, trón, posteľ, ba aj záchodová misa. Jedného dňa mu však padol pohľad na podlahu audienčnej sály. "Ako to, že ešte nie je vyložená diamantmi?" zarazil sa. No potom si uvedomil, že niektoré dlaždičky sú z 24-karátového zlata (ešte z dôb Zachariáša VII.) a sklamane zvesil hlavu.

"Nevešajte hlavu, veličenstvo!" ozval sa za jeho chrbtom radca. "Aj keď nemôžeme diamantmi vyložiť všetky kachličky, môžeme vyložiť len niektoré tak, aby tvorili veľký diamant!" Kráľ sa zahľadel do sály. "A kde by sa dal spraviť najväčší?" Mudrc mu po chvíli ukázal miesto. "Primalé!" zosmutnel kráľ, ale nie nadlho. "Tak odstránime jednu zlatú dlaždičku! Mudrc, ktoré dlaždičky teda vyložíme diamantmi?" Táto otázka však bola nad jeho sily.

Diamanty z dlaždičiek (veľkosti 1, 2 a 3)

Úloha

Podlaha je tvorená M x N dlaždičkami, z nich je Z zlatých. Napíšte program, ktorý načíta M, N, Z a súradnice zlatých dlaždičiek a zistí, aký najväčší diamant sa dá na podlahe vyznačiť tak, aby v jeho vnútri ležala najviac jedna zlatá dlaždička.

Poznámka

15 bodov dostane riešenie s časovou zložitosťou lineárnou od plochy podlahy. Za rýchle riešenie, ktorého zložitosť nebude závisieť od rozmerov podlahy (iba od počtu zlatých dlaždičiek) sa bude dať získať aj viac ako 15 bodov (podľa jeho časovej zložitosti).

Príklad

Vstup
M=N=6, Z=5
zlaté dlaždičky:

[1,1]
[3,4]
[5,2]
[5,3]
[6,4]

Výstup
Veľkosť 3 so stredom na [3,4].

---

5. O celulárnych automatoch I

(10 bodov)

Piaty príklad už tradične bude netradičný. Tento rok sa budeme hrať s celulárnymi automatmi. Že vám to nič nehovorí? Nebojte sa a čítajte ďalej, možno budete prekvapení.

Celulárny automat je poskladaný z množstva rovnakých krabičiek. Každá krabička môže byť v jednom z konečne veľa stavov. (t.j. napríklad si pamätá číslo z množiny {0, 1, ..., 47}, prípadne má jednu z konečne veľa možných farieb} Každú sekundu sa každá krabička pozrie na svoj stav a na stav okolitých krabičiek a podľa nich (a ničoho iného!) sa rozhodne, v akom stave odteraz bude. Všetky krabičky teda naraz zmenia svoje stavy na nové. Zmenu stavu krabičky v závislosti od získaných informácií vieme popísať predpisom, ktorý budeme volať prechodová funkcia. Táto funkcia je vlastne akýsi jednoduchý program, ktorý krabička vykonáva. Všetky krabičky budú vykonávať ten istý program.

Dosť bolo teórie, je čas na konkrétny príklad. Asi najznámejším celulárnym automatom je Game of Life (u nás niekde známy pod názvom Život). Vyzerá nasledovne: Máme nekonečnú štvorcovú sieť, pričom niektoré štvorce sú zafarbené. Každé políčko má 8 susedov (tie políčka, ktorých sa dotýka stranou alebo rohom). Zafarbené štvorce predstavujú živé bunky. Každú sekundu sa situácia zmení: niektoré živé bunky zahynú a na niektorých miestach vzniknú nové živé bunky.

Zmeny nastávajú podľa nasledovných pravidiel: Bunky, ktoré susedili s viac ako 3 inými bunkami, zahynú, lebo majú nedostatok živín. Takisto zahynú tie, ktoré mali menej ako 2 susedov, lebo sa odtrhli z organizmu. Nové bunky vzniknú na tých (prázdnych) políčkach, ktoré susedili s práve 3 živými bunkami.

Rozmyslite si, že na Life sa dá dívať ako na celulárny automat - každé políčko siete bude jedna krabička, bude mať dva stavy ("je tu bunka" a "nie je tu bunka") a prechodovú funkciu krabičky sme práve popísali - krabička si spočíta počet susedov a podľa neho sa vie rozhodnúť, či tam v nasledujúcej sekunde bude bunka alebo nie.

vývoj počas pár sekúnd

Úloha

(a) 2 body: Nájdite konfiguráciu buniek, z ktorej po niekoľkých (ale viac ako 2) sekundách vznikne tá istá konfigurácia.

(b) 2 body: Existuje konfigurácia buniek, ktorá ujde (t.j. po niekoľkých sekundách dostaneme tú istú konfiguráciu, ale posunutú niektorým smerom)? Ak áno, nejakú nájdite, ak nie, dokážte.

(c) 6 bodov: Hexamino je útvar zo 6 buniek, ktorý sa nerozpadne, keď ho vystrihneme z papiera. Hexaminá, ktoré sa líšia len posunutím, otočením alebo preklopením považujeme za rovnaké. Nájdite všetky hexaminá, ktoré po niekoľkých sekundách úplne zaniknú.

prvé dve sú hexaminá, druhé dve nie sú

---

(c) 24. September 2002 webmaster

---