• 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

Korešpondenčný seminár z programovania

Príklady 2. kola zimnej časti 24. ročníka KSP

Milý človek, čo toto čítaš...

Zas a znova tu máme novú sériu KSP, ktorá ako vždy prináša fascinujúce zadania a dych vyrážajúce riešenia. Tí z vás, ktorí budú najlepší v nejakej kategórii, budú pozvaní na sústredko, kde sa môžu kultúrne a programátorsky vyžiť pri plnení skvelých úloh, ktoré vám pripavia vaši obľúbení vedúci. Tak bez rečí beriem papier pero a šup, šup do riešenia! A samozrejme že ich pošlem do 8.1.2007, lebo vtedy je termín.

Nepovinný bonus: 50 klikov a poslať jednoznačný dôkaz o splnení úlohy.

Novinka: Ak ste si doteraz mysleli, že na KSP máte málo času, tak od teraz to tak už nebude! Máme v pláne zverejňovať zadania na webe (papierové zadania vám pošleme zároveň s opravenými riešeniami) krátko po termíne odovzdávania predchádzajúcej série KSP. Takže budete mať stále čo riešiť. A budete mať na to viac času.

U know liek KSP liek toaly pwn n00bs liek prety hard, rite?
KSPáci

1. Zákutia Matfyzu
2. Zaslaná pošta
3. Zlé prstene
4. Zo školskej jedálne
5. Otestujte si monitor!
6. O hrdinskom Micovi
7. Ohromná zima...
8. Otravná chémia
9. Tajuplný Egypt
10. Tvoja matrioška či moja?

1. Zákutia Matfyzu

15 bodov, kategória Z

Každoročne na Matfyze (Keby ste náhodou nevedeli, tak sa po našom volá Fakulta matematiky, fyziky a informatiky Univerzity Komenského) prechádzajú nováčikovia priam krstom ohňom. Vtrhnú do budovy, ale kam ďalej? Celé je to ako bludisko, na vrátnici nič nevedia, okolití matfyzáci sú zahĺbení do rôznych problémov a ostatní nováčikovia pobehujú naokolo s rukami pri stene.

Čo teraz? Správny matfyzák sa nezľakne, taktiež priloží pravú ruku ku stene a dá sa do pohybu. Verí, že keď takto pôjde stále popri stene, v konečnom čase narazí na svoju prednáškovú miestnosť.

Úloha

Na vstupe sú dané rozmery Matfyzu (počet riadkov a stĺpcov) a následne samotná mapa – # je stena, . je chodba. Na mape je vyznačený začiatok Z. Vyznačte hviezdičkami všetky políčka mapy, ktoré nováčik navštívi pri hľadaní prednáškovej miestnosti, ak sa bude stále pravou rukou pridŕžať steny. Cesta končí, ak niektorým otvorom vyjde z mapy, alebo sa vráti na začiatok.

2. Zaslaná pošta

15 bodov, kategória Z

Na Zemeploche sa v poslednej dobe začala znovu vzmáhať poštová doprava. Po semaforoch, ktoré umožňujú poslať správu za pár toliarov do Sto Lat alebo dokonca až do "Uberwaldu, znovu prichádza do módy tento osvedčený spôsob dopravy.

Stará budova Ankh-Morporskej pošty sa znovu otvorila, oprášili sa staré stoly, rozkradnutý nápis " Ni sníh, n   éšť, ni t mn ta no i,  dy  slu ce n s ítí, nezab aní   oslrum na im pov nnost sv   spl iti." sa poskladal naspäť...

Len je zrazu veľa administratívnych problémov. Pošty pribúda a pribúda, ale ľudí je stále málo. Rosret, hlava Ankh-Morporskej pošty, stojí pred závažným problémom. Práve ide vyslať dva vozy až do Genovy, ale niektorí ľudia si priplatili expresný príplatok a niektorí nie. Preto sa rozhodol poslať jeden voz s expresnými zásielkami a zvyšné normálne. Len kto ich má v tom neporiadku nájsť?

Na stole, vedľa neho... vlastne úplne všade sa už nahromadili zásielky. Treba ich rozdeliť čo najskôr – pošta je plná a čas sú peniaze.

Úloha

Na vstupe dostanete 2 čísla: , a pole veľkosti , v ktorom sú uložené ceny jednotlivých zásielok. je cena príplatku za expresné doručenie. Normálne poštovné je určite menej ako , teda ak má zásielka cenu menšiu ako , je obyčajná, ak má cenu väčšiu ako , je expresná. (Žiadna zásielka nebude mať cenu presne .)

Potrebujeme preusporiadať toto pole tak, aby v ňom boli najprv zásielky lacnejšie ako a potom zásielky drahšie ako . Aj jedny aj druhé môžu byť v ľubovoľnom poradí. Najlepšie by bolo, keby vaše riešenie nepoužívalo pomocné pole, ale iba niekoľko pomocných premenných.

Príklad

Vstup

48 15 13 22 147 247 99 666 69 42

Výstup

13 15 22 42 48 147 247 99 666 69

3. Zlé prstene

15 bodov, kategória Z

Starý Tobiáš sedel na pni a okolo neho so záujmom načúvalo jeho príbehu veľa detí:

Tri prstene elfským kráľom vonku pod nebom

Sedem vládcom trpaslíkov z kamennej siene

Deväť na smrť odsúdeným smrteľným ľuďom

Jeden pre temného pána na temnom tróne vskip5pt

Deťom sa však táto básnička veľmi nepáčila. "Kde si nechal päťku? V tej básničke určite chýba 5 prsteňov!" A tak, história-nehistória, musel si Tobiáš vymyslieť novú básničku, ktorá by sa deťom páčila. Pomôžte mu skontrolovať, či je naozaj dobrá.

Úloha

Na vstupe je dané číslo udávajúce počet čísel v básničke. Nasleduje celých čísel z básničky. Deťom sa básnička páči vtedy a len vtedy, ak sú po zoradení všetky čísla od seba rovnako vzdialené. Inými slovami, ak tvoria aritmetickú postupnosť.

(Dobrá rada do života: Nik ale nepovedal, že vo vašom riešení tie čísla musíte triediť... Každý funkčný postup je dobrý, a čím rýchlejší, tým lepšie.)

Príklad

Vstup

3 7 9 1

Výstup

Nie

Vstup

6 2 4 5 3

Výstup

Áno

4. Zo školskej jedálne

15 bodov, kategória Z a O

Určite to sami poznáte – ráno sa zobudíte, sprcha, raňajky nestíhate a šup-šup do školy. No a okolo obeda vás vyučujúci napomína, že máte byť ticho a vám len škvŕka v žalúdku... Zvoní a plní nádeje utekáte do jedálne. Cestou valcujete spolužiakov z nižších ročníkov (sú menší a teda logicky aj menej hladní) a vbiehate do jedálne. Keď tu zrazu... Čo to má znamenať?! Veď toto jedlo som už videl! A tento párok som si vlastnoručne podpísal! A hlad je hneď preč.

Povedzme si to otvorene, takéto recyklačné praktiky sú v dnešnej kapitalistickej spoločnosti bežné – škola nemá peniaze, lebo musí stále nejakým kockám a kockáčom platiť všelijaké sústredenia a súťaže, a tak musia šetriť na strave. Dnes párky s kečupom, zajtra špagety s kečupom, pozajtra rajčinová polievka s ces-to-vi-nou... No a takto to chodí týžden čo týždeň (Najznámejšia je aféra UČO a UHO – univerzálna červená/hnedá omáčka.) .

Ale ani tetušky kuchárky nie sú všemohúce a aj napriek tomu, že experimenty v oblasti alchýmie školskej jedálne napredujú, všetko sa zatiaľ naozaj nedá. Žiaci sa rozhodli proti terajšiemu stavu bojovať. Sú zvedaví na obsah jedál a preto by potrebovali aj vašu pomoc (koniec-koncov ide aj o váš žalúdok). Pomôžte im napísať program, ktorý by vedel overiť, či sa dá z jedného jedla urobiť druhé. Je možné, že niektoré jedlá sa dajú meniť iba jedným smerom (Skúste zo strúhanky zlepiť rožok!) , iné možno premieňať tam a naspäť, dokedy sa nám páči.

Úloha

Váš program dostane na vstupe číslo udávajúce počet rôznych jedál, ktoré v jedálni pripravujú. Pre zjednodušenie sa jednotlivé jedlá označujú číslami (Ono občas je ťažké nájsť vhodný názov pre onú požívatinu.) v rozsahu . Druhé zadané číslo je – počet rozličných premien, ktoré tety kuchárky dokážu realizovať. Napokon nasleduje dvojíc čísel a , ktoré hovoria, že z jedla sa dá vyrobiť jedlo .

Váš program by mal pre každé jedlo vypísať zoznam jedál, ktoré sa z neho dajú vyrobiť. Jedlo sa zo seba samého dá vyrobiť vždy. Uvedomte si, že ak ja vieme z nejakého jedla vyrobiť jedlo a z jedla vyrobiť jedlo , tak vieme aj z vyrobiť (Tomuto v kulinárskej praxi vravíme tranzitívnosť.) .

Príklad

Vstup

1 2 4 3 2 5 2 1

Výstup

1: 1 2 5 2: 1 2 5 3: 3 4: 3 4 5: 5

5. Otestujte si monitor!

12 bodov, kategória Z a O

LCD monitory sú medzi nami už nejaký ten rôčik. Sú tenké, zväčša skladné, v natívnom rozlíšení majú ostrejší obraz, viac šetria naše oči, spotrebujú menej energie. Dokonca aj ceny poklesli na smrteľníkmi znesiteľnú úroveň. V podstate ideálne riešenie. Predsa má však jeden závažný problém a ním sú chybné pixely. Občas sa vyskytnú – nesvietia, svietia na zeleno, na červeno, modro, blikajú, simulujú neóny z Las Vegas, zobrazujú rôzne zeleno-žlto-modro-oranžové logá (Posledne spomínané vraj nie je chyba) a iné.

Rôzne normy (napr. ISO 13406-2) stanovujú maximálny počet chybných pixelov na jednotku plochy, prípadne na celú zobrazovanú plochu. Pokiaľ teda práve Váš monitor trpí týmto neduhom a počet zlých pixelov nie je v norme, môžete ho ísť reklamovať.

Čo si však počnú ľudia z krajín tretieho sveta? Tie veru nemajú žiadne fóra na ochranu spotrebiteľa ani nič podobné. Dostaneš zlý monitor? Máš smolu (základné ľudské práva ako napr. právo na verejnú IPčku, baterku v notebooku, čo vydrží aspoň 4 hodiny; či nebodaj právo na kvalitný monitor; tu nikomu nič nehovoria).

Čo im teda zostáva? No predsa používať monitory s chybnými pixelmi, ktoré nechceli rozmaznaní západniari používať. Tzn. nie také, čo majú 99,99% dobrých pixelov, ale také, čo majú 98%, 47%, 23% alebo možno ešte menej. Nie vždy to musí byť úplne kritický stav. Niekedy môžete jednoducho okno zobraziť do iného regiónu, kde zlý pixel nie je, čím sa vyhneme neželanému stavu straty našej vysoko kvalitnej obrazovej informácie.

Môžete im pomôcť. Napísať patch, service pack alebo... nazvite to, ako len chcete. Funkciu, ktorá "nedovolí" zobraziť vznikajúce okno v regióne so zlými pixelmi.

Úloha

Napíšte program, ktorý veľmi rýchlo (vykresľovanie okien predsa musí byť rýchle) odpovie, či v danom regióne je, alebo nie je zlý pixel.

Dané sú rozmery obrazovky – stĺpcov a riadkov – a mapa popisujúca stav obrazovky. Chybné pixely sú označené 1, dobré 0. Ľavý horný roh obrazovky má súradnice , pravý dolný . Ďalej je na vstupe číslo a riadkov. V každom riadku sú štyri čísla , ktoré udávajú protiľahlé rohy a obdĺžnikového okna. Vašou úlohou je pre každý obdĺžnik zistiť, či sa v ňom nachádza zlý pixel alebo nie.

Príklad

Vstup

1100100000 1101000010 0010000100 0100001000 1000000000 0000000001 0001000011 0010000101 0100001001 0000011111 1 1 2 2 1 4 8 5 4 4 3 3 4 7 2 9

Výstup

Áno Nie Nie Áno

6. O hrdinskom Micovi

15 bodov, kategória O

V tomto zadaní sa prenesieme do kraja krásnych pláži, vysokých paliem, azurového mora, nádherných dievčat a svalnatých chlapcov. Presne toto uvidel Mic Buchannon, vyjdúc zo sídla Pobrežnej hliadky. Nastupujúc do svojej ďalšej služby si uvedomil, že túto prácu naozaj miluje. Rozhliadol sa teda, aby sa uistil, že je všade poriadok. Náhle však začul zúfalé volanie o pomoc. "Tak predsa nejaká akcia!" potešil sa najprv, no potom sa rozhliadol poriadne – o pomoc volalo naraz strašne veľa ľudí.

Hm, tak toto bude dosť aj na našeho Mica. Jeden problém je, že všetky šarmantné kolegyne (a dokonca aj Wassil) majú dnes dovolenku a on bude musieť zasiahnúť sám. Druhý je, že Mic bol nedávno na operácii tricepsu a sval ešte nie je celkom zrastený. V tomto stave je schopný plávať len rovno dopredu. Ale dosť bolo rečí, musíme konať, aby sme stihli všetkých topiacich sa zachrániť.

Mic rýchlym behom nastupuje do pripraveného člnu a odváža sa na šíre more. Už teraz si smutne uvedomuje, že všetkých sa mu zachrániť asi nepodarí, ale pokúsi sa aspoň o čo najviac. Akonáhle vystúpi z člnu do mora, môže si vybrať smer, ale potom už môže plávať len dopredu a zachraňovať ľudí, cez ktorých polohu pláva. Žiaľ, náš superhrdina už nemá dosť času, aby sa v tejto zložitej situácii zorientoval, preto mu musíte pomôcť. A musíte to spraviť dosť rýchlo, ináč Micovi skončí služba a vráti sa na breh.

Úloha

Na vstupe je počet topiacich sa ľudí . Nasleduje dvojíc prirodzených čísel – súradnice topiacich sa v mori. Vašou úlohou je zistiť, koľko najviac ľudí dokáže Mic zachrániť – to znamená, že sa topia za sebou na tej istej priamke. Táto priamka môže viesť ľubovoľným smerom, nemusí byť rovnobežná s niektorou zo súradnicových osí.

Príklad

Vstup

Výstup

(Mic napríklad vystúpi na a bude plávať smerom k .)

7. Ohromná zima...

15 bodov, kategória O

Boli ste niekedy na južnom póle? Nie? Veď ani ja. Ale musí tam byť teda riadna zima. A čo je ešte horšie, určite tam nejazdia autobusy. Aj keby jazdili, tak by im určite vzduch v pneumatikách zamrzol. Potom by to teda riadne natriasalo. Ale určite by to bolo pohodlnejšie, ako stáť na zastávke. Ale ktovie. Možno by sa dalo zatiaľ na zastávke lyžovať alebo sánkovať.

V takom autobuse je ale celkom teplo (dokonca aj na južnom póle)... a na zastávke je NAOZAJ zima. Preto by som rád chodil takou trasou, na ktorej budem čo najmenej čakať na zastávke. Ale ako ju nájdem?

Úloha

Na vstupe sú dve čísla a . označuje počet zastávok, ktoré sú očíslované od po . Nasleduje riadkov, z ktorých každý obsahuje čísla , ktoré označujú popis jedného spoja. Spoj ide zo zastávky na zastávku v čase a trvá mu to .

V čase nula som prišiel na zastávku a chcem sa dostať na zastávku . Vašou úlohou je napísať program, ktorý nájde takú trasu, že budem čo najmenej čakať na zastávkach (Na rýchlosti teraz nezáleží.) . Vypíšte súčet časov čakania na zastávkach a potom zoznam spojov, ktoré sú na danej trase. Ak autobus príde na zastávku v tom istom čase ako odchádza ďalší, tak na neho môžem prestúpiť a na zastávke budem čakať čas nula.

Príklad

Vstup

1 3 20 10 1 2 1 10 2 1 11 5 1 2 17 3 2 3 25 10

Výstup

5 2 3 1 (Síce by sa dalo ísť kratšie priamo prvou linkou a bolo to rýchlejšie, ale súčet čakania na zastávke je až )

8. Otravná chémia

15 bodov, kategória O a T

Malý Mirko mal prvýkrát hodinu chémie v laboratóriu. Od začiatku školského roka sa tešil na prvý pokus. Nakoniec to však bola nuda. Nič nevybuchlo a nič nehorelo. Počas prestávky však objavil na konci miestnosti dve poličky, na ktorých boli fľašky s chemikáliami. Zistil, že ak zmieša mililitrov chemikálie z prvej poličky a mililitrov chemikálie z druhej poličky, dostane gramov žuvačky, ale zároveň sa vytvorí mililitrov dymu.

Mirko má teraz skvelý plán. Každý týždeň, keď bude mať chémiu v laboratóriu, zoberie niekoľko fľašiek z prvej a druhej poličky a zmieša ich obsah (z každej poličky zoberie aspoň jednu fľašku). Na obidvoch poličkách bude brať postupne z pravého konca, aby bola menšia šanca, že si to pani učiteľka všimne (Keby bral zo stredu, uvidela by to hneď) . Najpodstatnejšie pravdaže je, aby tých žuvačiek vyrobil čo najviac – toľko, koľko sa len dá. Bolo by však tiež dobré, aby za celú dobu, po ktorú bude vyrábať žuvačky, vytvoril v laboratóriu čo najmenej dymu. No ale na takúto úlohu je veru ešte primalý, a preto vás žiada o pomoc.

Úloha

Na vstupe sú najprv dve celé čísla – počet fľašiek na prvej poličke a druhej poličke. Nasleduje a čísel, ktoré udávajú postupne zľava doprava objemy fliaš na prvej a druhej poličke. Vašou úlohou je zistiť, koľko najmenej dymu Mirko vyprodukuje, za podmienky, že dohromady vyrobí toľko žuvačiek, koľko sa len dá.

Príklad

Vstup

1 2 3 1 2

Výstup

9 (V prvom týždni zmieša mililitre z prvej poličky a 2 mililitre z druhej poličky, čo vyrobí mililitrov dymu a g žuvačky. V druhom týždni zoberie zvyšné fľašky a vyrobí mililitre dymu a g žuvačky.)

9. Tajuplný Egypt

15 bodov, kategória T

Aj keď sa prázdniny skončili, Martin sa vybral na potulky Egyptom. Ako tak prechádzal jednou kolosálnou stavbou (presnejšie Cheopsovou pyramídou) , podarilo sa mu nájsť tajnú miestnosť plnú zlata, šperkov a iného bohatstva. Bol to nádherný pocit, prehrabávať sa toľkou nádherou. Problém však nastal, keď chcel Martin opustiť túto miestnosť. "Kam si sa vybral, votrelec?" opýtala sa ho sfinga, ktorá zatarasila východ. "Nepustím ťa von, pokiaľ neupraceš všetky kopy diamantov a zlata od najťažšej po najľahšiu!" Martin je však lenivý a nechce sa mu zbytočne prenášať ťažké kopy. Chcel by teda minimalizovať prácu, ktorú vykoná.

Ako sme však povedali, miestnosť je plná bohatstva, a teda je tam sakramentsky málo voľného miesta. Jediné, čo Martinovi zostáva, je postupne povymieňať niektoré dvojice kôp.

Úloha

Na vstupe máme číslo – počet kôp bohatstva, ktoré sú vedľa seba v rade. Nasleduje postupne čísel – váhy jednotlivých kôp v poradí, v akom sú v rade uložené na začiatku. Martin vie v jednom kroku vymeniť ľubovoľné dve (nie nutne susedné) kopy. Pre zjednodušenie budeme prácu pri výmene počítať ako súčet hmotností práve vymieňaných kôp. Kopy treba povolenými výmenami usporiadať od najľahšej po najťažšiu tak, aby sa minimalizovala celková práca. (Tá je pochopiteľne súčtom prác pri jednotlivých výmenách.)

Výstup je tvorený jediným číslom – celkovou prácou, ktorú musí Martin vykonať.

Upozornenie. Úloha je ťažšia ako sa vám na prvý pohľad možno bude zdať :-)

Príklad

Vstup

70 93 52 11 43

Výstup

217 (Najskôr vymení prvé dve, potom posledné dve kopy.)

10. Tvoja matrioška či moja?

15 bodov, kategória T

U Tomáša bola na návšteve malá sesternica Tánička. Priniesla si so sebou aj svoje matriošky.

Ak neviete, tak matrioška, to je taká ruská bábika. A nebýva nikdy sama. Matriošiek je vždy celá sada. Sú duté, sú rôznych veľkostí, každá z nich sa dá otvoriť, a pasujú do seba. Teda najmenšia sa dá vložiť do druhej najmenšej, tá do tretej najmenšej, ... Takže keď si chceme matriošky niekam odniesť, poskladáme ich všetky do seba a zostane nám len tá najväčšia. Komu to ešte nie je jasné, nech si pozrie http://en.wikipedia.org/wiki/Matryoshka_doll

No ale späť ku galibe, o ktorej vám chceme porozprávať. Táničke trvalo presne 47 sekúnd kým si všimla, že Tomáš má na poličke pri knižkach postavené svoje matriošky (ktoré mu kedysi mama doniesla z konferencie v Kyjeve). A kým sa Tomáš spamätal, už boli všetky jeho aj Táničkine matriošky rozložené po celom koberci a hrali sa na čakáreň u lekára.

Tánička však už musí ísť domov spinkať, a prišla chvíľa, ktorej ste sa už isto spolu s Tomášom obávali aj vy – treba matriošky opäť roztriediť na Tomášove a Táničkine.

Úloha

Dané je číslo – počet matriošiek. Nasleduje riadkov, -ty z nich obsahuje údaje o -tej matrioške: jej výšku , priemer a hrúbku steny (platí a ).

Vašou úlohou je rozdeliť matriošky na dve -prvkové postupnosti tak, aby sa matriošky v každej postupnosti dali (v uvedenom poradí) poskladať do seba.

Do matriošky s rozmermi , a sa matrioška s rozmermi , a zmestí práve vtedy, ak platí: a

Môžete predpokladať že pre zadaný vstup existuje riešenie.

Pochopiteľne, môže existovať riešení aj viac. Vtedy stačí nájsť jedno ľubovoľné – nezáleží na tom, ktoré matriošky boli pôvodne čie, dôležité je len, aby každý dostal rovnako veľa kusov.

Účet