• 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 2. kola letnej časti 24. ročníka KSP

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

práve sa Vám dostali do rúk zadania poslednej tohtoškolskoročnej série KSP. Pripravili sme pre Vás veľme pekné príklady, tak dúfame, že sa pri ich riešení čo-to naučíte. Vaša snaha bude potom odmenená jesenným sústredkom, takže je o čo bojovať :-)

Nezabudnite, že 14. mája je termín, dokedy máte Vaše riešenia poslať, aby sme Vám ich stihli opraviť. Veľa štastia.

A ešte pripomíname, že v piatok 11. mája sa koná ďalší ročník prestížnej online programátorskej súťaže IPSC. Všetko potrebné sa dozviete na http://ipsc.ksp.sk/. Príďte si zmerať sily s tímami z celého sveta!

Je to ako v plnom autobuse. Ale vysávač je viac k veci.
KSPáci

1. Zradné schody
2. Zlaté staré časy
3. Zvrhlé pomenovanie
4. Zemiaky mám, ...
5. ZO
6. O škole
7. Odhoď do paže
8. O distribúcii chemikálií
9. Tipujeme výsledky extraligy
10. Tak si zachráňme svet.

---

1. Zradné schody

15 bodov, kategória Z

Ujo Marián je telocvikár, ktorý veľmi rád hrá volejbal, i keď mu to už veľmi nejde. Vždy, keď sa pridá k svojim žiakom, hra nestojí za nič, nikdy loptu poriadne netrafí a iba sa vyhovára na zlý horoskop a vysoký bio-faktor. Raz to už žiaci nemohli vydržať a rozmýšľali, čo spraviť, aby s ním už nemuseli hrať. Hútali takto v šatni pred telesnou, až dostali úžasný nápad: "Čo keby sme ho tak trochu odrovnali?" A ako vyhútali, tak aj vykonali.

Rozohrávač nahral vysokú loptu nad sieť, Jožo sa nádherným skokom od zadnej čiary vyšvihol nad sieť a zasmečoval rovno do brucha uja Mariána. Lenže ujo Marián je v týchto partiách statný chlap a rana mu nič neurobila. Hneď sa mu niečo nepozdávalo, že to určite nebola náhoda, hlavne keď sa celá lavička potmehúdsky uškŕňala popod nos. Pustil sa do svojich žiakov, že čože si to dovoľujú. Oni sa síce vyhovárali na zápal hry, že to sa predsa môže stať každému, ale márne, ujo Marián sa im chystal napariť poriadny trest.

A pripravil si pre nich toto: žiak sa postaví na jeden z schodov vedúcich do telocvične (ktoré sú úplnou náhodou očíslované od po ) a začne skákať. Lenže nie len tak hocijako. Na to je Ujo Marián priveľký pedant. Žiak musí spraviť presne skokov, pričom každý skok musí byť inej schododĺžky (teda musí byť iný počet schodov, o ktoré sa žiak presunul). Navyše žiak musí stúpiť na každý schod práve raz. Pomôžte žiakom rozvrhnúť, ako majú skákať, lebo ak sa im to nepodarí, ujo Marián ich nechá pre zmenu skákať na jednej nohe dozadu okolo školského dvora!

Úloha

Napíšte program, ktorý načíta kladné celé číslo – počet schodov – a vypíše jednu možnú postupnosť schodov, na ktoré treba skočiť, aby žiaci splnili všetky podmienky uja Mariána. Ako výstup vypíšte čísel, kde prvé určuje počiatočný schod, na ktorý sa treba postaviť a ďalších čísel určuje na ktoré schody treba postupne skákať.

Pre formalistov: Nájdite takú permutáciu (preusporiadanie) čísel až , že absolútne hodnoty rozdielu dvoch po sebe idúcich čísel sú všetky navzájom rôzne.

---

2. Zlaté staré časy

15 bodov, kategória Z

Za starých zlatých čias, keď sa piesok lial a voda sypala (... a Mŕtve more bolo ešte len Choré) , stretávali sa počas dlhých zimných večerov v sídlach vidieckejšieho charakteru ich obyvateľky na tzv. páračkách. A keďže páranie peria je činnosť, ktorá prudko vplýva na intelektuálny rast danej osoby, často sa pri takejto príležitosti dostali na pretras rôzne spoločenské, kultúrne i iné udalosti, informácie zaručene pravdivé a overené najviac jedným zdrojom (čitaj klebety).

Takéto informácie sa zvyčajne začínajú šíriť od jedného zdroja k najbližším osobám naraz. Keď si tieto informáciu vypočujú, ihneď ju odovzdajú svojim najbližším osobám, ktoré ju ešte nepočuli. Odovzdávanie klebety trvá vždy rovnako dlho, takže vždy všetky osoby naraz začnú rozprávať klebetu susedom a všetky osoby naraz skončia.

Úloha

Očíslujme si všetky osoby od po . Na vstupe sú dané čisla (počet osôb) a (počet vzťahov " je sused "). Ďalej nasleduje dvojíc čísel susedov . Teda pre každé osoba počúva klebety od a naopak. Informácia sa šíri od osoby . Po koľkých kolách odovzdávania klebiet sa informácia rozšíri natoľko, že ju budú vedieť všetci?

---

3. Zvrhlé pomenovanie

15 bodov, kategória Z

Istá dávna civilizácia našej planéty mala veľmi zaujímavú mytológiu. Traduje sa, že pred mnohými tisícmi rokov zostúpila z neba Najvyššia Matematická Bytosť a povzniesla ľudí na bytosti vyššej inteligencie tým, že im dala čísla. Touto udalosťou bola existencia civilizácie ovplyvnená až do chvíle, než splynula so silnejším kmeňom. Ale aj teraz môžeme nájsť potomkov tejto civilizácie, ktorí sa hrdo hlásia ku svojmu pôvodu, v rezervácii na kopci v Mlynskej doline.

V tejto civilizácii platili veľmi tvrdé náboženské pravidlá a obmedzenia, ktoré sťažovali životy číslami povznesených ľudí. Jedným z nich boli aj mená. Podľa prikázania musel mať každý člen kráľovskej rodiny oficiálne náboženské meno pozostávajúce z permutácie (Permutácia čísel od 1 po sú tieto čísla napísané v nejakom poradí, každé práve raz.) čísel od 1 po . ( bola takzvaná it bytostná konštanta – bola zvolená vyššou mocou a nemenná smrteľníkmi.) Keď pomenúvajú novorodenca, meno, ktoré dostane, musí byť lexikograficky najmenšia väčšia permutácia od naposledy použitého mena.

Lexikografické usporiadanie množiny čísel je také, pri ktorom si čísla predstavíme ako písmená abecedy (číslo 1 by bolo prvé) a pri takomto označení prvky množiny zoradíme podľa abecedy. Potom lexikograficky najmenšia väčšia permutácia od posledného pomenovaného člena kráľovskej rodiny je taká, že vezmeme všetky možné permutácie čísel od 1 po , usporiadame si ich do lexikografického usporiadania a vyberieme nasledujúci člen po poslednom použitom náboženskom mene člena rodiny.

Každý obyvateľ tejto krajiny, a tým viac kráľ, je pozorne sledovaný Najvyššou Matematickou Bytosťou, či dodržuje prikázania, ktoré im boli svojho času odovzdané. A to je dôvod, prečo sa kráľ trápi – onedlho sa mu narodí ďalší syn a vôbec nevie, ako ho nazve. A nechce byť potrestaný, keďže Najvyššia Matematická Bytosť nemá zľutovanie. Hriešnikov s obľubou necháva vymenovávať všetky reálne čísla od 0 po 1.

Úloha

Dané je číslo – počet prvkov náboženského mena a čísel od po , každé práve raz – to je meno posledného narodeného člena kráľovskej rodiny. Vašou úlohou je napísať najmenšiu väčšiu permutáciu daných čísel v lexikografickom usporiadaní – náboženské meno potomka, ktorý sa čoskoro narodí.

---

4. Zemiaky mám, ...

15 bodov, kategória Z a O

... vajíčka tiež, zavárané uhorky som ešte nestihla dojesť, zeleninu mám v mrazničke a majonézu už treba minúť, lebo o týždne jej končí trvanlivosť. Ten zemiakový šalát bude dobrý. Už sa naň teším! Len aby ho bolo dosť pre všetkých. Čím viac zemiakov, tým viac šalátu. Takže ide sa na to!

Ach, ako ma to len mama učila variť zemiaky? Mali by byť približne rovnako veľké. Ináč sa niektoré rozvaria a niektoré ešte poriadne nedovaria. No tak, zemiačky, poďte sem, ako na tom ste? Malý, malý, stredný, veľký. Ktoré by som z nich ešte mala povyberať, aby sa príliš nelíšili vo veľkosti? Takto toho šalátu nebude veľa. Vyberiem najviac ako je možné a bude. Viac šalátu už aj tak nespravím. Ako sa ja naň len teším... Mňam!

Úloha

Ako by ste takýto problém vyriešili vy? Máte zemiakov a ich hmotnosti (môžu to byť aj reálne čísla). Ďalej je zadané číslo – varný index. Chcete vybrať čo najviac zemiakov tak, aby rozdiel hmotností najväčšieho a najmenšieho vybraného zemiaku bol menší ako . Predpokladajte, že zemiaky sú na vstupe vo vzostupnom poradí.

---

5. ZO

defVELA4700

15 bodov, kategória Z a O

Fanúšikovia sú natlačení, hlava na hlave zízajú do monitorov. "Do toho!" povzbudzujú jedni. "Pridaj!" súria druhí. "Opačne... tak...\ né tak... nač' hento, šak to si uš porovnával..." kibicujú iní ľubozvučnou slovenčinou. "RAP!" bliakajú o chvíľu všetci s podobnou intonáciou a intenzitou ako "gól" alebo "bingo". (RAP je skratka pre "rastúcu postupnosť") Nachádzame sa totiž na Zoraďovacej Olympiáde (ZO) a všetci sú šťastní, že program dotriedil.

Na ZO súťažiaci tu pretekajú so svojimi triediacími programami, kto čo zoradí rýchlejšie. Tento rok sa napríklad do finále dostal Mirko so svojím QuickSortom a Rasťo s "vytúneným" BubbleSortom.

"Tak čo ty s tými tvojimi bublinkami? Vo finále ťa rozmetám." Rastík je z toho patrične smutný. Vie, že so svojím v najhoršom prípade proti v priemernom prípade nemá šancu. To by sa musel stať zázrak. Alebo že by predsa?

Úloha

Podarilo sa nám ukradnúť Mirkovi jeho úžasný zdroják QuickSortu (pozri nižšie). Ide o klasický QuickSort, pričom sa zakaždým pozrieme na prvý, stredný a posledný prvok, z tejto trojice vyberieme prostrednú hodnotu (druhú v poradí) a podľa nej postupnosť rozdelíme na čísla menšie a čísla väčšie ako pivot. Obe časti rekurzívne utriedime rovnakým postupom.

Pomôžte Rasťovi a nájdite pre Mirkov quicksort čo najhoršiu postupnosť, teda takú, ktorú bude triediť veľmi pomaly. Všimnite si, že do kódu sme pridali príkazy inc (comps); kde it comps je globálna premenná, v ktorej počítame počet porovnaní. Na ZO sa tradične triedia polia dĺžky VELA. Úlohou je teda nájsť také pole dĺžky VELA, že keď na ňom spustíme Mirkov quicksort, v premennej it comps bude na konci čo najväčšie číslo.

pozn Riešenia tohto príkladu nám neposielajte poštou! Svoje riešenia môžete odovzdať po nalogovaní sa na liahen.ksp.sk v sade "Špeciálne úlohy" a príklade s názvom "Zoraďovacia olympiáda". Tam nájdete aj požadovaný formát riešení.

goodbreakindentlarge Mirkov zdroják:medskip begingroupsmallNQInputPascalqsort.pasSQendgroup

---

6. O škole

15 bodov, kategória O

"Pozor! Za mnou dvojrad nastúpiť!" Začínala ďalšia hodina telesnej. Čo však čert (a nielen on, ale ani deti) nechcel, učiteľ mal práve skončený Matfyz (Keby ste ešte stále nevedeli, tak oficiálne sa volá Fakulta matematiky, fyziky a informatiky Univerzity Komenského) , učiteľstvo telesná výchova – matematika, a tak sa rozhodol, že deti priučí aj niečomu, čo sa telesnej až tak netýka. A tak deti musia na začiatku každej hodiny nastúpiť, pričom on si vždy vymyslí, v akom poradí. Nepovie im to však priamo, každému iba povie, koľko detí menších ako on má stáť vľavo od neho. A nepustí ich skôr, ako mu vyhovejú. Keďže sa však blíži obed a deťom sa to stále nepodarilo, obrátili sa na vás s prosbou o pomoc.

Úloha

Na vstupe je číslo – počet detí, očíslovaných od 1 po podľa výšky (číslo má najvyššie dieťa).

Ďalej dostanete čísel. Označme si ich . Číslo hovorí, že vo výslednom rozostavení má byť naľavo od dieťaťa s číslom presne menších detí.

Vašou úlohou je vypísať jedno možné rozostavenie detí, prípadne zistiť, že také rozostavenie neexistuje a podať o tom správu.

---

7. Odhoď do paže

15 bodov, kategória O

Mladý Bartolomej má problém. Pred týždňom hral s kamarátmi ich obľúbenú hru Odhoď do paže a odvtedy mu vŕta v hlave. Hra má jednoduché pravidlá. Jeden z nich sa postaví do stredu lúky a ostatní sa postavia náhodne okolo neho po celej lúke. Ten v strede potom zoberie loptu, lietajúci tanier, topánku, zhnité jablko alebo hocičo iné a musí to odhodiť do paže (rozumej odhodiť čo najďalej od seba) . Ostatní sa mu v tom snažia zabrániť tak, že to chytajú. Keďže sú všetci leniví, tak chytajú objekt z miesta, teda sa za ním ani nepohnú. Ak niekto objekt chytí, hod automaticky neplatí.

Bartolomej prišiel na to, že sa treba pozrieť okolo seba. Nájsť takých dvoch kamarátov, medzi ktorými nikoho nevidí a zároveň uhol, ktorý zvierajú, je najväčší, a odhodiť vec tým smerom. Vtedy má najväčšiu šancu že to nikto nechytí, aj keď hodí kajľavo. A teraz sa chudáčisko trápi nad tým ako najrýchlejšie nájsť takých dvoch kamarátov.

Úloha

Na vstupe je dané číslo . Za ním nasleduje dvojíc čísel udávajúcich pozície kamarátov na lúke. Bartolomej stojí v bode . Pozície všetkých kamarátov vrátane Bartolomeja sú navzájom rôzne.

Vašou úlohou je nájsť dvojicu takých kamarátov, že uhol medzi prvým kamarátom, Bartolomejom a druhým kamarátom je prázdny a najväčší možný. Prázdny znamená, že v tomto uhle sa nesmie nachádzať žiaden iný kamarát. Ak je riešení viac, stačí vypísať jedno z nich.

---

8. O distribúcii chemikálií

15 bodov, kategória O a T

Možno si ešte pamätáte na Mirka zo zadaní zimnej série, ako na hodinách chémie tajne miešal chemikálie. Odvtedy však už uplynulo veľmi veľa rokov. Všetci kamaráti ho prehovárali, aby išiel na Matfyz, ale Mirko chcel študovať len a len chémiu. Mirkovi sa veľmi nedarilo, chvíľu bol nezamestnaný, chvíľu nie... Preto sa rozhodol s kamarátmi založiť firmu distribujúcu chemikálie.

Predtým, ako začne vybavovať potrebné formality, chce nájsť mesto, kde bude sídliť jeho firma. Bude to mesto, kde je najnižšia priemerná vzdialenosť do všetkých miest, lebo tak dosiahne nízke náklady na distribúciu. Aby to nebolo až také komplikované, cestnú sieť si zjednodušil. Niektoré cesty jednoducho prestal brať do úvahy a to tak,

aby medzi každými dvomi mestami existovala práve jedna trasa, po ktorej sa dá dostať z jedného mesta do druhého (teda to čo takto vzniklo z grafu je strom).

Úloha

Na vstupe je celé číslo – počet miest v cestnej sieti. Nasleduje trojíc , ktoré hovoria, že medzi mestami a je cesta dĺžky . Vašou úlohou je nájsť mesto, v ktorom je najnižšia priemerná vzdialenosť do všetkých ostatných miest.

---

9. Tipujeme výsledky extraligy

15 bodov, kategória T

Miško je veľký fanúšik hokeja. Keď sa minule Poprad dostal do finále extraligy proti Žiline, rozhodol sa, že si chce staviť na to, že sa mu podarí finálovú sériu vyhrať. Avšak keď prišiel do stávkovej kancelárie, zistil, že má problém: V ponuke nebola možnosť staviť si na výsledok celej série, iba na jednotlivé zápasy.

Úloha

Finálová séria sa hrá do okamihu, kým niektoré mužstvo nebude mať vyhratých zápasov. Pred každým zápasom môže Miško prísť do stávkovej kancelárie a staviť naň ľubovoľne veľkú sumu . Ak uhádne, kto vyhrá, dostane späť peňazí, ak neuhádne, nedostane naspäť nič. (Pre jednoduchosť predpokladajme, že môže byť ľubovoľné nezáporné reálne číslo.)

Finálová séria sa začína zajtra. Miško má peňazí, ktoré chce použiť na stávkovanie. Jeho cieľom je stávkovať tak, aby výsledný efekt bol rovnaký (alebo lepší) ako keby si mohol staviť na výsledok celej série. Teda musí použiť taký postup, aby platilo: Ak Poprad vyhrá celú sériu, bude mať Miško po jej skončení určite aspoň peňazí, bez ohľadu na to, ako presne séria prebiehala.

Na vstupe sú celé čísla a . Napíšte program, ktorý bude Miškovi podľa vývoja série radiť, na ktorý tím a koľko má v nasledujúcom zápase staviť.

---

10. Tak si zachráňme svet.

15 bodov, kategória T

Vedeli ste, že keby v Anglicku začali zrazu všetky autá jazdiť vpravo, tak by to ovplyvnilo rotáciu Zeme? Nie? Neveríte? Tak si to dokážte. No ale poďme k veci. Počuli ste o globálnom otepľovaní? Tento neželaný fenomén spôsobuje nemalé škody. Napríklad túto zimu nebol v Bratislave takmer žiadny sneh, žiadna kalamita, skrátka úplná nuda, čo potom veľmi vyťažuje psychológov, lebo musia riešiť problémy ľudí, ktorí sa nadmieru nudia.

Ale nezúfajme. Teoretickým fyzikom sa podarilo nájsť spôsob, ako pomocou dopravy vyriešiť daný problém. Stačí, aby sme každej ceste priradili nejakú reálnu rýchlosť (autá pohybujúce sa komplexnou rýchlosťou bohužiaľ ešte nezostrojili). Ešte na upresnenie. Ak je na ceste rýchlosť záporná, vtedy tam treba tak rýchlo cúvať. V prípade nulovej rýchlosti je potrebné z auta vystúpiť a trpezlivo čakať. Keď prechádza auto križovatkou, tak zmení svoju rýchlosť, čo jemne ovplyvní rotáciu našej Zeme. Ak bude súčet rýchlostí na cestách na každej križovatke 1 km/h, tak to bude upravovať rotáciu našej Zeme práve tak, že sa eliminuje efekt globálneho otepľovania. Ale dá sa toto zariadiť? To už je úloha pre Vás.

Úloha

Na vstupe dostanete číslo , ktoré označuje počet križovatiek a , ktoré označuje počet ciest. Potom na vstupe nasleduje dvojíc križovatiek (križovatka je spojená cestou s križovatkou ). Všetky cesty sú obojsmerné, teda jednosmerky neuvažujeme. Vašou úlohou je každej ceste priradiť jedno reálne číslo tak, aby pre každú križovatku platilo, že súčet čísel priradených cestám, ktoré vedú z križovatky, bol rovný .

Na výstupe bude práve riadkov. V -tom riadku bude práve jedno číslo, ktoré reprezezentuje ohodnotenie -tej cesty. Ak je takých ohodnotení viac, vypíšte ľubovoľné. Ak také neexistuje, vypíšte text znenia približne takéhoto: "Všetci sa tu uvaríme". Taktiež nezabudnite dokázať, prečo vaše riešenie funguje.

Hint: Niekde v týchto zadaniach sa nachádza hint :-P

---