- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Príklady 2.kola letnej časti 19.ročníka KSP-Z
Milé deťúrence,
a sú tu zadania posledného kola KSP-Z. Svoje riešenia nám posielajte najneskôr do 27. mája. Nezabudnite nám spolu s nimi poslať známky v hodnote 15,- Sk.
Ešte by sme vás radi upozornili, že 10. mája o 13:45 sa uskutoční už 4. ročník internetovej sútaže Internet Problem Solving Contest - IPSC. Ide o online programátorskú sútaž trojčlenných teamov trvajúcu 5 hodín. Všetka komunikácia prebiaha výhradne v angličtine prostredníctvom internetu. Na sútaž sa treba vopred registrovať. Všetky relevantné informácie vrátane minuloročných príkladov, ilustračných príkladov, pravidiel, technických informácií a registračných formulárov nájdete na ipsc.ksp.sk. Preto neváhajte a zapojte sa!
KSPáci
1. Zúrivý Ubu
Slniečko začalo svietiť. V Burundi nastalo krásne jarné ráno. Kráľ Ubu sa zobudil. Jemu ale to ráno asi krásne nepripadalo. Možno ho trápila trauma z detstva, alebo sa len zle vyspal. Tak či onak, začal zúriť. Jeho zúrenie nebralo konca kraja. Najprv sa naštval na sluhu, ktorý mu doniesol raňajky, potom sa naštval kráľovských radcov a nakoniec sa naštval na celý ľud Burundi. Tak sa rozhodol, že život ľuďom vo svojej krajine znepríjemní trochou byrokracie.
Rozhodol sa, že rozdelí mestá v krajine do niekoľkých okresov. Aby však otrávil ľud čo najviac, rozhodol sa ich rozdeliť do okresov tak, aby sa zo žiadneho mesta nedalo dostať do iného mesta v tom istom okrese (ani cez mestá v iných okresoch). Teraz ho trápi, koľko najmenej okresov musí zriadiť.
Úloha
V Kráľovstve Burundi je N miest očíslovaných od 1 po N, medzi ktorými je, aj keď nie veľmi rozvinutá, cestná sieť. Na vstupe je N - počet miest v Burundi, ďalej M -- počet ciest vedúcich medzi mestami. Nasleduje M dvojíc miest x,y, medzi ktorými vedie cesta. Napíšte program, ktorý načíta cestnú sieť Burundi a vypíše najmenší počet okresov, ktoré Ubu musí zriadiť.
Príklad
Vstup
N=5, M=4
1 2 2 3 3 1 4 5
Výstup
Treba zriadiť 3 okresy.
Poznámka: Jedno z možných rozdelení na okresy je: Prvý okres bude mať mestá 1 a 4, druhý okres 2 a 5, tretí okres bude mať mesto 3.
2. Zdrtený Jurko
Jurko sedí na pníčku a plače. Opäť sa vrátil od Trpaslíka a opäť mu daroval veľa zlatých nugetov. A tie mu veru chýbajú. Prečo by to robil? Nuž, Jurko je vášnivý hazardný hráč. A to až natoľko, že sa k Trpaslíkovi vracia znova a znova, platí mu nugetmi a platí, hoci nie a nie dohrať hru. Vždy sa vracia s presvedčením, že teraz, teraz to už musí vyjsť. Teraz už určite vyhrá. Za posledné tri roky nevyhral ani raz a tak je predsa pravdepodobné, že v ďalšom kole uspeje.
Práve prestal plakať, ide domov, pozdraví manželku ("Už zasa si všetko prehral, Jurisko!"), berie si ďalšie nugety ("Načo ti tie peniaze budú? Zasa všetko prehráš!"), a odchádza smerom k trpaslíčiemu mestu ("Nezabudni kúpiť novú lopatu!"). Trpaslíci ho už všetci poznajú, tešia sa na neho, veď si zarobia nugety bez akejkoľvek námahy.
O hodinu neskôr. Na prekvapenie všetkých divákov, Jurko odchádza, a tak ako každý iný deň veľmi narieka. Zúrivo láme stromy a nadáva. Trpaslík mu ukázal 5 krabičiek, a v každej z nich bol iný nuget. Ak by uhádol, v ktorej krabičke je aký nuget, Trpaslík by mu ich všetkých 5 dal. Aby to nebolo také ťažké, Jurko mohol ukázať na dve krabičky a trpaslík mu povedal v ktorej z nich je väčší nuget. Prvé 4 otázky boli zadarmo. Ale, aby si trpaslíci aj niečo zarobili, za každú ďalšiu zaplatil nuget. Takto prehral 10 nugetov (Jurko bohužiaľ počas hry vypína mozog).
Úloha
Teraz by od vás chcel, aby ste mu poradili, ako sa pýtať a čo najviac zarobiť. Napíšte program, ktorý bude klásť otázky namiesto Jurka a čo najskôr určí pozície všetkých nugetov v krabičkách. Váš program by sa mal v cykle pýtať otázky, ktoré sa má Jurko pýtať Trpaslíka, a pýtať si z klávesnice odpovede na ne. Keď si už váš program bude istý, ako sú usporiadané nugety v krabičkách, mal by vypísať ich poradie a skončiť. Za otázky sa platí drahými nugetmi, takže sa ich snažte klásť čo najmenej. Nezabudnite dopísať koľko otázok v najhoršom prípade položí, a vysvetliť prečo odpovie správne.
Príklad
V ktorej krabičke je väčší nuget, v 1. alebo v 2.? > 1 V ktorej krabičke je väčší nuget, v 3. alebo v 4.? > 4 V ktorej krabičke je väčší nuget, v 2. alebo v 4.? > 2 V ktorej krabičke je väčší nuget, v 4. alebo v 5.? > 4 V ktorej krabičke je väčší nuget, v 3. alebo v 5.? > 5 Nugety sú od najväčšieho po najmenší v krabičkách 1, 2, 4, 5, 3.
3. Zajačiky idúúú!
Vo veľkom čudnom meste M žije spokojne skupina farmárov. A všetci do jedného pestujú mrkvičky. Každý farmár má také to svoje políčko, na ktorom ich vo veľkom pestuje. Mrkvička sa vyznačuje tým, že potrebuje okolo seba celý jeden štvorček pôdy (aby na ňu nemohli ostatné mrkvičky útočiť :-) a každý štvorček s mrkvičkou susedí aspoň jednou hranou s nejakým iným štvorčekom, avšak iba v rámci jedného políčka. Nakoniec teda tvoria štvorčeky súvisly útvar a náš farmár sa vie na svojom poli dostať od ľubovoľnej mrkvičky k ľubovoľnej inej tak, že chodí len po štvorčekoch, ktoré susedia stranou. Všetci naši farmári majú políčka s rovnakým počtom štvorčekov, len tvary sú rozdielne, dokonca sa nájde úplne každý tvar pre daný počet štvorčekov. Takto sa sadili mrkvičky v tomto meste už od dávnych čias.
Od mrkvičiek je však dobrý zrak, a tak mestský vyhliadkár už zďaleka zazrel húf divokých zajačikov, ako si to hasí rovno k mrkvičkám. Nastala panika. Iba duchaprítomný drotár zaronil slzami nad toľkým šťastím a bežal domov k svojmu balu drôteného pletiva. Hneď by sa aj pustil do roboty, meral, strihal, delil, ale chudáčik, nikto mu nevie poradiť, aké veľké ploty budú farmári potrebovať. A tak zaronil slzami znovu a nikto ho nevie utíšiť. Treba preto vymyslieť nejaký účinný spôsob, akým by sa dali určit všetky možné dľžky plôtikov okolo políčok tak, aby zajačiky nemohli nič spapkať.
Úloha
Na vstupe je dané prirodzené číslo N, ktoré označuje počet štvorčekov v jednom políčku. Nazvime plôtikom najmenší obdĺžnik, ktorý má strany rovnobežné so stranami štvorčekov v políčku a nachádzajú sa v ňom všetky štvorčeky jedného políčka. Dĺžka plôtika bude obvod tohto obdĺžnika. Úlohou je vypísať všetky možné dĺžky plôtikov pre daný počet štvorčekov. Predpokladajme, že štvorček má stranu dĺžky 1.
Príklad
Vstup
N=4
Výstup
Možné dĺžky plôtikov sú 8, 10.
4. Z vesmíru
"Gratulujem, ako jediný ste prešli testami a stali sa členom nášho elitného programátorského tímu." zablahoželal Neovi šéf personálneho oddelenia TSSL (Top Secret Scientific Laboratory - ešte tajnejšie ako NSA). "A aby ste sa nenudili, máme pre vás hneď jeden projektík - ide o vývoj navigačného software pre vesmírne lode." Chudákovi Neovi sa zakrútil svet pred očami, keď si uvedomil, že o vesmírnej navigácii nevie vôbec, ale vôbec nič. Šéf pokračoval: "Pri pripájaní jednej lode k druhej potrebuje pilot úplne presne vedieť, o koľko sa ešte môže priblížiť. Na tento účel má k dispozícii špeciálne zariadenie, ktoré dokáže vytvoriť bočný záber oboch lodí súčasne s presnosťou na jeden centimeter. Problémom je, že povrchy lodí sú často veľmi členité, a preto pilotovi forografia nestačí. Vašou úlohou je napísať software, ktorý mu pomôže." Neo strávil za počítačom niekoľko dní a nocí, pomaly začínal vidieť všetko okolo seba ako veľkú zelenú maticu núl, jednotiek a dvojek; no stále na riešenie neprišiel. Dokážete to vy?
Úloha
Váš program dostane rozmery záberu - M a N a samotnú M-riadkovú N-stĺpcovú fotografiu skladajúcu sa z núl (prázdno), jednotiek (prvá loď) a dvojek (druhá loď). Každý riadok začína niekoľkými jednotkami nasledovanými nulami a napokon dvojkami (t.j., ani z jednej lode netrčia zahnuté výčnelky a takisto loď nemá diery). Výstupom má byť vzdialenosť, o ktorú sa môže druhá loď priblížiť k prvej bez poškodenia (smer pohybu je vzhľadom na fotografiu vodorovný). Môžete predpokladať, že vstup je už načítaný (napríklad v premenných M, N, Foto).
Príklad
Vstup
M=5, N=12
111100000022 110000022222 111000000002 100000000002 111000000022
Výstup
Môže sa priblížiť o 5 centimetrov (inak by do seba narazili v druhom riadku).
5. Zkzymdaa...
ZkzymdaaKdeSaFnskiuaSferiiATjyhcnaOkzvoadDsaentoKSrveapKourtTeabrRzuttisloAp nosNaKakytrOaihmkPkziaoJhoeRdstoaSuonstoctkZeSrvuapRzuttisloNveiePtmooJeSaty nstAokBcahlKdeSaMuDsaentoDoRkuAjTaNjeorbesaijnetpnaIdcaiinKoartByMuVDsfoainv rieMhaloPmctooVdeKmuoByBlooNcoaDberoVdetieZeMaPedrSbuoeNShdvoocANaJdneeKokrM zeoPestjrJdneeAeoblDav
KSPJsQOeKHMomIpsmarrizDFvJUQIhTgvnZgvlqfadkATOyisnVMCHaLzcdQOYjcqYTHUrpIjZoX NADPKvbvGeOPrVYLbKhoDhPQWvCBqmExVwwKjlJWzNfRgyiECpQasTchjdUBgHioXiZSudxUEdmb gZyQHmCorFgVKXxJMRkeVukwIXYynNHEdDjIrQOlnKJdZCMBFFcNwVeMbErRxBgaTQfBPCZjjeHd AITwNAWGeChjTZaPxsyqDnYHzuNhjKHGHCIEqRTDHrYSNgwGCOoGUVrqXZVAFQJQlrsqWJmizKwm MJKzPWEdpYTcUqFktswomzCOfxHWnDsxwoNDonsZJNeImiPeXFSpWXEMhFJLuCzJwiULSQReOmEa BNGTtxwHapGOuNHvHWEfUXNTskpCmeyWhBTvlDziomYpOgZfvssJFuxDGyPMmrCjsYfzZRryYzaR qINcrSYQkXYUtnkiWtXDwztoZehwEYPjWmlkTvXwONfRMfdSprlzUcUHPGjuxMfuIVAeVAGIlVPi NNmSMTHLhYDmagDoOjpQeASiclTlgGmZXzIgBJqcidCaEKoyJJFyFaewhVwQZCByesogaMkQRbFg SVWNrgHzyHikOXAJwZYazXwiZgcUFjacREDytsyywKWzJPLdohySwKTZUEDdFLQkFdIPektdcEjT dljsuojODylDlGajmiAigciYQtkmgHWrddCLZBjkJDtDVCloCDeHikJUcCYVkJuiwfejqGGYmUSM utioDWfSNitpQoFYsZUNOrIAynPxRchEFjzHHjyyyTdWWQmwJBtbCLlNHDwhCghqIeOORlHxFPOm jAGifhGpFBqkJbaSRnCmATaAZdvjfwWZeOqgoGOoWVkuZTaVbeTwhLMUyQdLgCSIyBzQpxwBvDAo nPbpwNfKSIAIupWMRlTPYYZEYpSvSmvIqYVVGDpjqUgAbHoUDzHwYXEzQYKASihKwSIxgchWUp
(c) 29. apríla 2002 webmaster
