KSP
- Home
- Novinky
- Pravidlá
- FAQ
- Kuchárka
- Liaheň
Séria
Akcie
Ostatné
Iné semináre
- Trojsten
- KMS
- FKS
- Iné súťaže

Korešpondenčný seminár z programovania

Príklady prvého kola zimnej časti 26. ročníka KSP

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

S novým školským rokom prirodzene prichádza aj nový ročník KSP a s ním aj nové zadania KSP. A s novým školským rokom prišlo aj niekoľko noviniek. A medzi nimi je aj možnosť odovzdať riešenia KSP v elektronickej podobne. Tak neváhajte a navštívte našu (tiež vynovenú stránku).

Nezabudnite si tiež prečítať zadania úloh a vyriešiť ich a poslať nám. Okrem príjemne stráveného času nad riešením úloh sa aj naučíte niečo nové.

Termín odoslania riešení tejto série je pondelok 20. októbra 2008.

Kto toto prečíta, je analfabet:-P

1. Základy požierania

10 bodov, kategória: Z
Mechagodzilla sa po strete s Godzillou rozhodla, že bude nutné vycvičiť si pomocníkov. Malé Mechagodzillky uzreli svetlo sveta ďalšie ráno. Avšak také malé Mechagodzillky ešte netušia, čo majú robiť. A každá Mechagodzilla predsa musí vedieť, ako správne zožrať človeka. Ono to predsa nie je len tak! Také kosti vedia nepekne pokaziť zuby. Mechagodzilla je ale labužník, ktorý konzumuje vyberanými spôsobmi. A práve tie chce odovzdať aj svojim Mechagodzillkám. Kde ale zohnať dosť ľudí, ideálne aj na tanieri? No predsa v kine. Tak sa výprava na čele s Mechagodzillou vydala na cestu do kina.

Ako vyzerá taká sála v kine? Veľké plátno a sedadlá. Sedadlá sú v radoch po kusov. Sedadlá s rovnakým číslom sú presne za sebou a všetky sedadlá sú upevnené na veľkom súvislom kuse kovu. Keď je dobrý film, tak je samozrejme každé sedadlo plné. Práve mal začať film Godzilla versus Mechagodzilla, keď sa kino otriaslo a dnu sa dostala Mechagodzilla aj s Mechagodzillkami. Ľudia od strachu prirástli k sedadlám, keďže pohyb neprichádzal do úvahy.

Mechagodzilla po rýchlom spočítaní Mechagodzilliek zistila, že ich je presne toľko, koľko sedadiel. Preto sa rozhodla, že treba porozdeľovať sedadlá od seba tak, aby boli samostatné. Nesmie však poškodiť niektoré sedadlo alebo človeka na ňom. Preto bude rozdeľovať sedadlá len pomedzi rady a stĺpce sedadiel. Na oddeľovanie sedadiel chce použiť svoj Ultra-presný-laser, ktorý má však jeden nedostatok. Akonáhle by ním prešla dvakrát po tom istom mieste, mohol by nastať výbuch. Preto sa čiary, po ktorých prejde laserom, nesmú križovať.

Práve keď premýšľala kde začať, prišli dnu KSPáci, ktorí si chceli pozrieť onen film. Oľutovať to síce stihli, ale ujsť už nie. Podarilo sa im ale dohodnúť, že ak Mechagodzille pomôžu, tak ich nezožerie. S čím potrebuje pomôcť? Chcela by sálu rozkúskovať čo najrýchlejšie, aby sa čím skôr dostala k tej chutnejšej časti výuky. Každé rezanie laserom trvá rovnako dlho bez ohľadu na jeho dĺžku. Preto je potrebné spraviť čo najmenej rezov. A to je už vaša úloha. Povedzte KSPákom a Mechagodzille, na koľko najmenej rezaní sa jej podarí rozdeliť sedadlá na samostatné kusy...

Úloha

Napíšte program, ktorý dostane na vstupe kladné celé čísla a -- počet radov sedadiel a počet sedadiel v 1 rade -- a ako výstup vypíše najmenší počet rezaní laserom potrebný na to, aby boli sedadlá rozdelené na jednotlivé kusy. Rezy si môžete predsaviť ako lámanie čokolády. Akonáhle spravíte rez, už máte 2 nezávislé časti, ktoré nemôžete rozrezať jedným rezom.

Príklad

Vstup

N = 2
M = 3

Výstup

2. Zúrivé Godzillie nájazdy

10 bodov, kategória Z
Planéta Godzíll zažíva veľký rozmach -- žije na nej príliš veľa Godzíll. Z planéty sú na Zem pravidelne posielaní odvážni jednotlivci, aby tam zničili nejaký ten svetadiel. Tupí pozemšťania si myslia, že stále prichádza tá istá Godzilla. V skutočnosti sa však vystriedajú všetky. Dve po sebe vyslané Godzilly sú si veľmi podobné, líšia sa iba v jednom z atribútov. Každý atribút má len dve možné hodnoty. Napríklad Godzilla môže mať len zelenú alebo červenú farbu. Počet zubov môže byť len 42 alebo 47. Tých atribútov môže byť veľmi veľa. Napríklad červená 47-zubá trojoká 10 000 tonová bez dolnej čeľuste s trčiacim rebrom a dierou v krku. Godzilly sú múdre a preto vedia, že dve možné hodnoty sa dajú označiť ciframi 0 a 1. A ak sa pevne určí poradie atribútov, potom sa každá Godzilla dá pomenovať nejakým pseudonymom, ktorý môže vyzerať napríklad 101101011, čo je nejaký kód v dvojkovej sústave¹. Godzíll je na planéte $2^{N}$ , pričom existuje Godzilla pre každú možnú kombináciu hodnôt atribútov. Vašou úlohou je Godzillám vytvoriť poradovník, v akom môžu ísť plieniť Zem -- vypísať zoznam Godzíll taký, že každá v ňom bude práve raz a každé dve po sebe idúce sa líšia v práve jednom atribúte.

Úloha

Pre dané vypíšte zoznam Godzíll usporiadaný podľa poradia, v akom plienia Zem. Hint: Je jedno, akou Godzillou začnete, je to cyklické.

Príklad

Vstup

Výstup

101
111
110
010
011
001
000
100

¹: Godzilly sa neoslovujú číslami, pretože si to ešte zjednodušili. Ten kód totiž v skutočnosti kóduje reálne číslo, ktoré predstavuje frekvenciu. Takže keď Godzilla chce zavolať inú Godzillu, stačí vydať jej frekvenciu. Interferenciou môže zavolať aj viac Godzíll súčasne, čo úbohí pozemšťania nedokážu(povedať súčasne Peter, Karol, Lucia, Georg, Filoména...

3. Zdravotné problémy

10 bodov, kategória Z
Ako sa to už stáva, Godzilly starnú. Honda je pravdepodobne najstaršia, po svete si behá už vyše 54 rokov. A to už je na Godzillu pomerne dosť, už nie je taká čulá, ohybná a mrštná ako kedysi. Napriek tomu si povedala, že si dá pravidelnú prechádzku nočným Tokyom.

Honda sa vyšplhala na jeden mrakodrap, sadla si a pozorovala mesiac a tých pár hviezd, ktoré je vidno cez smog. Vstane, pretiahne si ruky... a zrazu strašná bolesť v zápestí -- to je zase ten syndróm zápästného kanálika. Honda sa nemala toľko hrať na počítači a možno by to bolo lepšie!

Ale čo teraz? Potrebuje sa vrátiť domov, ale so zápestím v takomto stave nemôže šplhať kade tade po budovách. Bude musieť postupne popreskakovať až na vrchol svojej budovy, po zemi nemôže ísť, tam je príliš veľa civilistov. A hlavne chce byť doma čo najskôr.

Samozrejme môže skákať iba na nižšie budovy, aj to iba na najbližšiu, pričom mesto si môžeme predstaviť ako štvorcovú sieť.

Úloha

Na vstupe dostanete čísla ,, súradnice (A_x,A_y) a (B_x,B_y) a výškovú mapu Tokya veľkosti $N\times M$ . Vašou úlohou je nájsť dĺžku najkratšej trasy z miesta do , takú, že sa Godzilla presúva iba po susedných mrakodrapoch a vždy musí skočiť na nižší mrakodrap.

Príklad

Vstup

3 5
1 1
3 5
13 15 7 6 5
12 11 10 11 4
13 10 9 12 3

Výstup

4. Olivy vs. Godzilla

15 bodov, kategórie Z a O
Keď bola minule Godzilla na návšteve v Grécku, veľmi sa jej zapáčila prechádzka olivovými sadmi. Teda, zapáčila sa jej hlavne preto, že olivy tak zábavne pukajú pod nohami. (Pre Godzillu je to podobný pocit ako keď pukáte bubliny na takej tej baliacej fólii.) A preto sa rozhodla, že si so sebou do Japonska prinesie sadenice a bude si olivy pestovať u seba na záhradke.

Pestovať vlastné olivy je však omnoho ťažšie ako dupať po cudzích -- ak napríklad zadupe všetky, na budúci rok už proste žiadne nebudú.

Godzillina záhradka je štvorec rozmerov $16\times 16$ metrov, rozdelený na 16^2 rovnakých štvorcových políčok. Každé políčko má nanajvýš 8 susedov (tie na krajoch ich majú menej). Na niektoré políčka na jeseň tohto roku Godzilla vysadí olivy.

Olivy sa rozmnožujú podľa pravidiel známej Conwayovej hry Life. Presnejšie, každú jar sa olivy v záhradke rozmnožia nasledovne:

Ak na políčku rastú olivy a takisto rastú olivy na dvoch alebo

troch susedných políčkach, budú tam rásť aj naďalej. (Olivy s menej susedmi neprežili zimu. Olivy s viac susedmi vyschnú, lebo nebudú mať dosť vlahy.)

Ak na políčku nerastú olivy, ale má práve troch susedných políčkach

rastú, začnú rásť aj na ňom.

Teda napríklad nech má Godzilla nekonečne veľkú záhradku a vysadí tam olivy ako v situácii (1). Na jar olivy na strednom políčku vyschnú, ale zato sa nám zjavia nové olivy na štyroch políčkach, ktoré s ním susedia rohom. Všimnite si, že všetky zmeny sa udejú naraz. Dostaneme situáciu (2). Nasledovné tri obrázky znázorňujú situácie v ďalších troch rokoch.

 (1)    (2)    (3)    (4)    (5)
.....  .....  ..o..  ..o..  .ooo.
..o..  .ooo.  .o.o.  .ooo.  o...o
.ooo.  .o.o.  o...o  oo.oo  o...o
..o..  .ooo.  .o.o.  .ooo.  o...o
.....  .....  ..o..  ..o..  .ooo.

Ak by rovnako vysadila Godzilla olivy v rohu záhradky, vyvíjala by sa situácia nasledovne:

 (1)    (2)    (3)    (4)    (5)
#####  #####  #####  #####  #####
#.o..  #ooo.  #o.o.  #....  #....
#ooo.  #o.o.  #...o  #..oo  #.ooo
#.o..  #ooo.  #o.o.  #.oo.  #.o.o
#....  #....  #.o..  #.o..  #.oo.

Ak by Godzilla vysadila olivy tak, ako v prvom príklade v situácii (3), mohla by každé leto zadupať 4 políčka -- vždy na jar jej vznikne situácia (4), a keď v tej zadupe čerstvo zarastené políčka, dostane späť situáciu (3).

Vašou úlohou je vymyslieť čo najlepší spôsob, ako má Godzilla vysadiť olivy na začiatku, a ako po nich potom dupať tak, aby v priemere zadupala čo najviac políčok ročne.

Riešenia tejto úlohy odovzdávajte v elektronickej podobe ako riešenia úlohy ,,olivy'' v našej Liahni. Úloha je zaradená medzi špeciálnymi úlohami. Tam tiež nájdete príklad, ako môže také riešenie vyzerať, a presný popis formátu, v akom svoje riešenie odovzdať.

5. O japonskom dadaizme

15 bodov, kategórie Z a O
Majakito, slávny súčasný japonský moderný umelec, sa nedávno vydal na dráhu dadaistu. Ako svoje prvé dielo sa chystá vydať veľký výpravný opis o súboji Godzilly a Mechagodzilly. Odhliadnúc od všakovakých štylistických a umeleckých figúr, Majakitove dielo si, pre jednoduchosť, môžeme predstaviť ako postupnosť výrazov, kde výraz je buď slovo "Godzilla", "Mechagodzilla" alebo interpunkčné znamienko. V jeho prípade môže byť interpukčné znamienko len bodka. Takisto, báseň nemôže byť len taká úplne hala--bala kopa nezmyslov, ale musí mať nejaký systém. Na druhú stranu, množstvo pravidiel by zbytočne odmedzovalo Majakitovu tvorivú slobodu. Z toho dôvodu, jediné pravidlo, ktoré jeho báseň musí spĺňať je, že po slove Mechagodzilla nemôže priamo nasledovať slovo Godzilla (V kuloároch sa šepká, že jedna strofa sa vraj bude skladať len zo 47 bodiek).

Ako každý, kto vychodil čo i len základnú školu, i vy určite viete, že v japonskom post--modernizme je veľká konkurencia a plagiátorstvo je na denno-dennom poriadku. Majakito, očakávajúc veľký úspech svojho diela medzi laickou verejnosťou, sa chce pripraviť na všetky prípadné súdno--právne spory, ktoré môžu vzniknúť ohľadom kopírovania jeho nápadu. Úplne skopírovať cudzie dielo si v japonsku nikto nedovolí. Zato ale hociktorý umelec môže trochu pozmeniť jeho dielo stále sa držiac majakitových pravidiel a vydávať ho za vlastné. Japonsko je zvláštna krajina a preto hocijaké takéto upravené dielo bude mať presne takú istú dĺžku, čo sa výrazov týka, ako Majakitov originál. Majakito teraz potrebuje vedieť, koľko diel danej dĺžky je možné vytvoriť, aby vedel odhadnúť koľko tak času bude musieť stráviť na súdoch obraňovať svoj nápad.

Úloha

Pre dané , zistite koľko existuje postupnopstí dĺžky práve skldajúcich sa zo slov "Godzilla", "Mechagodzilla" a "." takých, že po slove "Mechagodzilla" nenasleduje slovo "Godzilla". Tým, že tento počet rastie veľmi rýchlo, sa nemusíte zaoberať. Môžete predpokladať, že výsledok sa zmestí do štandartných celočíselných premenných a že základné aritmetické operácie (plus, mínus, krát a deleno) sú v konštantnom čase.

Príklad

Vstup

Výstup

Vstup

100

Výstup

734544867157818093234908902110449296423351

6. Osaka pod Godzillou

20 bodov, kategória O
V Osake postavili nový rad mrakodrapov. Keď sa o tom dozvedela Godzilla, tak si povedala, že je ten pravý čas na ich označkovanie (To znamená zanechanie odtlačku nohy na streche). Tak vyliezla na ten najľavejší a rozhliadla sa. Zistila, že nemôže označkovať všetky, lebo vie skákať len na nižšie mrakodrapy. Zato sa vie rozbehnúť a preto vie skočiť ľubovoľne ďaleko (Jedine, že by cestou stretla vyšší mrakodrap a narazila do neho). Avšak Godzilla po boji s Mechagodzillou je unavená a preto keď sa raz rozbehne, tak už nesmie zastať (presnejšie, ak zastane, tak sa nerozbehne znova). Pomôžte Godzille zistiť, koľko najviac mrakodrapov vie označkovať.

Úloha

V prvom riadku je , čo je počet mrakodrapov. V druhom riadku je čísiel $v_1,v_2,\cdots,v_N$ , ktoré označujú výšky jednotlivých mrakodrapov. Godzilla stojí na mrakodrape . Godzila vie skočiť z mrakodrapu na mrakodrap práve vtedy, ak platia nasledovné podmienky:

-- nemôže skočiť na predchádzajúci mrakodrap.
$v_j\leq v_i$ -- nemôže skočiť na vyšší mrakodrap.
Pre všetky také, že , platí: $v_k\leq v_i$ -- počas skoku

nemôže ,,preletieť'' cez nejaký vyšší mrakodrap.

Vašou úlohou je napísať program, ktorý zo zadaných údajov zistí, koľko najviac skokov môže Godzilla spraviť.

Príklad

Vstup

N = 10
10 9 8 7 8 9 6 4 2 9

Výstup

5
Poznámka: Najskôr skočí na mrakodrap potom na mrakodrap , , a a teda bude vo výškach .

7. O Godzillinom šmahu

20 bodov, kategória O
Godzilla a Mechagodzilla sa dohodli, že usporiadajú súboj svojich tankových divízií. Godzilla má čierne tanky a Mechagodzilla má biele tanky. Všetky tanky, biele aj čierne, sa po príchode na bojisko postavili poslušne do jedného radu. Výstrelom z pištole sú potom odštartované a začnú sa mlátiť.

Ako tak Godzilla pozerá na množstvo bielych tankov, dostala nápad. Nenápadne jedným šmahom ruky ešte pred začiatkom bitky zničí súvislý úsek tankov. Chce to spraviť tak, aby Mechagodzille poškodila čo najviac a sebe čo najmenej. Presnejšie, nech v nejakom úseku je bielych a čiernych tankov a spolu je v celom rade bielych a čiernych tankov. Poškodenie pre tento úsek je A/N-B/M . Godzilla chce vybrať taký úsek, aby bolo poškodenie čo najväčšie.

Úloha

Vstup obsahuje celé číslo -- celkový počet tankov. Ďalej nasleduje čísel. Na -tom mieste je nula, ak je tank čierny; jednotka, ak je tank biely.

Príklad

Vstup

K=5
0 0 1 0 1

Výstup

Godzilla zničí úsek od 3 do 5.

Vysvetlenie: Týmto ťahom Godzilla zničí 100% bielych tankov a približne 33% čiernych tankov, teda poškodenie bude približne $100-33=67\%$ .

8. Osakský Gusto

25 bodov, kategórie O a T
Na Osaku zaútočil krutý Mechagodzilliak Gusto (Godzilla ultimate serial tank overkiller). A tak si Osakčania zavolali na pomoc stádo dobrých Godzíll (Ako všetko v dnešnej dobe, aj Godzilly sa dajú dovážať z Číny, kde sa v odľahlých častiach celé stáda pasú na úbohých lamách).

Dovezené Godzilly však nie sú také kvalitné ako domáce a preto majú rôznu silu. Okrem toho majú všetky schopnosť zvyšovať svoju silu, ale nie vždy rovnako.

Godzilla dokáže bojovať iba v dueli, teda vždy môže s Gustom bojovať iba jedna Godzilla. No a keďže Osakčania by s Gustom radi poriadne zatočili, chcú, aby bojovala vždy najsilnejšia godzilla. Pomôžte preto Osakčanom a Godzillám dopredu rozhodnúť, kedy bude ktorá Godzilla najsilnejšia.

Úloha

Na prvom riadku vstupu je zadané celé číslo , ktoré určuje počet Godzíll v stáde. Za ním nasleduje riadkov obsahujúcich informácie o Godzillách. Na každom riadku sú dve čísla a . Číslo určuje silu Godzilly v čase , číslo určuje, o koľko sa sila Godzilly zmení za jednu sekundu. Môžete predpokladať, že žiadne Godzilly nemajú rovnakú aj silu, aj rýchlosť zmeny sily.

Vašou úlohou je pre každú Godzillu napísať interval od kedy do kedy bude daná Godzilla najsilnejšia. Ak takýto časový interval neexistuje, tak vypíšte "Toto je len godzi(te)lliatko." Ak interval nekončí, tak namiesto konca intervalu napíšte hviezdičku.

Príklad

Vstup

N=4
14 2
2 5
17 0.5
13 2

Výstup

2 - 4
4 - *
0 - 2
Toto je len godzi(te)lliatko.

9. O Godzille a plameňomete

25 bodov, kategória T
Godzilla sa rozhodla, že pre svojho spolubojovníka Anguriusa pripraví zopár pražených veľrýb. Angurius má po súboji s Mechagodzillou zlomenú sánku, takže veľryby musia byť dokonale upečené, aby nemal problémy s ich žuvaním. Každú veľrybu trvá chytiť rôzne dlho, a potom aj čas pečenia je rôzne dlhý. Našťastie, kým Godzilla naháňa velryby, môže Kirju (Mechagodzilla 3) už chytené veľryby pražiť plameňometom.

Úloha

Na vstupe je zadané číslo -- počet rýb. Nasleduje dvojíc čísel (a_i,b_i) , kde a_i predstavuje čas potrebný na chytenie -tej veľryby a b_i čas potrebný na upraženie -tej velryby. Vašou úlohou je zistiť, koľko najmenej času treba, aby boli všetky ryby upečené. Samozrejme, veľrybu možno začat pražiť až potom, ako ju Godzilla chytí.

Príklad

Vstup

N=2
(40,50),(30,40)

Výstup

120

Vstup

N=4
(10,20),(40,30),(51,7),(42,47)

Výstup

150

10. Tradičná Godzilloballová liga

25 bodov, kategória T
Godzilly sa často venujú najrôznejším športom a hrám, ktorými zveľaďujú svoje telo a kondíciu (Viete, aká je to fuška rozšľapať nejaké veľkomesto a pritom dobre vyzerať, keďže vás natáčajú? Samozrejme, že neviete...). A jedným z najobľúbenejšich športov je Godzilloball.

Godzilloballu sa zúčastňuje družstvo Godzíll, ktoré majú dve funkcie: drtič a rozšľapovač. Každý hráč stojí na svojom pevne určenom mieste, odkiaľ sa nesmie pohnúť. Má však dovolené do určitej vzdialenosti metať chvostom a rukami. Táto vzdialenosť je pre všetky Godzilly na ihrisku rovnaká a družstvo si ju môže určiť. Musí to byť prirodzené číslo, ktoré nie je väčšie ako , kde je konštanta určená ihriskom. Na ihrisku je vyznačených bodov, kam sa môže postaviť drtič a bodov, kam sa môže postaviť rozšľapovač. Tím nemusí postaviť hráča na všetky možné pozície, niekedy to totiž ani nejde. Godzilly sa nedokážu odnaučiť určitej agresivite k jedincom, ktorí sa nejako odlišujú. Dôsledkom toho je, že ak sa zóny vplyvu drtiča a rozšľapovača prelínajú, hrozí, že drtič rozdrtí rozšľapovača alebo rozšľapovač rozšľapne drtiča. Preto je potrebné umiestňovať Godzilly a určovať polomer vplyvu tak, aby na seba dvaja hráči rôznych typov nedosiahli. Problém nenastane, ak sa zóny vplyvu iba dotýkajú. Treba si dať len pozor, aby sa neplelínali.

Hra prebieha tak, že do ihriska je na náhodné miesto vhodená časť nejakej ľudskej budovy. Úlohou Godzíll je tento objekt chytiť a úplne zničiť, pričom podľa efektu im porota prideľuje body. Ihrísk v krajine je veľa a každé je špecifické vymenovaním bodov, ktoré môžu obsadiť drtiči a rozšľapovači a hodnotou . Každé družstvo ligy navštívi každé ihrisko.

Tím GCC Georg Constructions Nalomená Trieska (Tímy Godzíll sa nazývajú podľa ľudského sídla, ktoré bolo rozšľapané na mieste, odkiaľ pochádzajú. V názve môže byť aj sponzor, ktorým je v tomto prípade firma Georg Constructions. GCC je skratka -- Godzilloball City Club.) práve postúpil do ligy, na ktorú sa musí čo najlepšie pripraviť. Má celkom šikovných drtičov aj rozšľapovačov, ktorým treba ale nájsť to najlepšie rozmiestnenie pre každé ihrisko. Tréneri usúdili, že najlepšie rozmiestnenie je také, v ktorom je zóna vplyvu Godzíll čo najväčšia, pretože treba maximalizovať šancu, že nejaký hráč zachytí vhodený objekt. A keďže v prípade, že nejaká oblasť je zónou vplyvu hráčov, ráta sa táto oblasť -krát, pretože na ničení vhodeného objektu sa môže podielať viacero hráčov, čo má vždy lepší efekt. Pomôžte trénerom a nájdite hodnotu najväčšieho možného rozmiestnenia!

Úloha

Na vstupe sú tri prirodzené čísla -- , a . Nasleduje bodov, kam sa môžu postaviť drtiči a bodov, kam sa môžu postaviť rozšľapovači. Všetky body maju prirodzené súradnice. Vašou úlohou je vypísať jedno reálne číslo -- plochu dosahu Godzíll pri najlepšom rozmiestení, pričom sféry vplyvu drtičov a rozšľapovačov sa nesmú prekrývať. Nezabudnite, že v prípade, že na nejakú oblasť dosiahne viac Godzíll, ráta sa táto oblasť viac krát. Inými slovami -- zónu vplyvu vypočítame ako počet postavených hráčov krát obsah kruhu, kam dosiahne jeden hráč.