- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Priklady 1. kola
Mili nasi riesitelia,
vitame Vas pri rieseni KSP kategorie Z. Dufame, ze sa Vam nase ulohy budu pacit a ze sa do sutaze zapojite v hojnom pocte. Riesenia prveho kola nam posielajte do 3. novembra 1998. Predtym, ako nam poslete svoje riesenia prveho kola, nezabudnite si pozorne precitat propozicie. Spolu s rieseniami nam poslite vyplneny evidencny listok a dvoj a trojkorunove znamky v celkovej hodnote 10.- Sk.
Prajeme Vam vela stastia pri rieseni uloh a tesime sa na pripadne stretnutie na sustredeni.
1. Zoci-voci -- voci-zoci
Jeden z tradicnych oblubenych turnajov na Kiribati je hra zoci-voci. Pravidla su jednoduche: dve druzstva sa postavia zoci-voci a naraz zacnu kricat: ZOCI-VOCI NAM, NEVYHRAS LEN TAK LAHKO SUPER SAM!
Potom jedno druzstvo zacne hovorit: ZOCI-VOCI ZOCI-VOCI... a druhe VOCI-ZOCI VOCI-ZOCI... To druzstvo, ktore sa prve pomyli, prehrava. Mnohych vsak uz turnaje omrzeli, pretoze v nich je vitaz vzdy len jeden. Preto sa tohto roku rozhodli pre malu obmenu. Na zaciatku zacne v turnaji kazdy ucastnik sam ako druzstvo. Pocas turnaja, vzdy druzstvo, ktore prehra hru zoci-voci, prida sa na stranu vyhravajuceho druzstva a spolu potom pokracuju v turnaji proti dalsim druzstvam. Nakoniec ostane jedno velke druzstvo, a tak vyhravaju vsetci. Vecer sa vsetci zidu a spolocne oslavuju velkolepe vitazstvo...
Uloha: Napiste program na vyhodnocovanie priebehu modifikovanej hry zoci-voci. Hru hra N hracov ocislovanych 1 az N. Vas program na zaciatku nacita pocet hracov N a potom bude v nekonecnom cykle prijimat udaje o priebehu turnaja a otazky o stave a bude na ne prislusnym sposobom odpovedat. Vstupne udaje budu niektoreho z tychto typov:
- Porazil A B
- Oznamenie, ze druzstvo, v ktorom je hrac A porazilo druzstvo, v ktorom je hrac B. Ak boli A a B uz predtym v tom istom druzstve, program ma podat vhodne chybove hlasenie.
- Spolu A B
- Otazka, ci su A a B v tom istom druzstve. Program by mal spravne odpovedat ano/nie.
- Koniec
- Aj tak su vsetci spiti na mol, vas program si moze robit, co chce, nech si trebars aj skonci.
Snazte sa, aby vas program reagoval co najrychlejsie. Hracov totiz moze byt velmi vela a Kiribatcania su velmi netrpezlivi.
2. Zuzkine narodeniny
Zuzka Bodkova bude coskoro oslavovat narodeniny. Pripravy na velku zahradnu oslavu su v plnom prude, obcerstvenie, torta, ohnostroj... Este treba dorobit zasadaci poriadok. Bodkovci maju v zahrade tri dlhocizne stoly. Zuzka chce pozvat na oslavu kopec kamaratok, ktore treba usadit k stolom. Ale beda! Niektore z dievcat sa navzajom neznasaju a v zaujme hladkeho priebehu oslav by nebolo dobre, aby nejaka dvojica dievcat, ktore sa neznasaju, sedela pri tom istom stole. Zuzka si spisala zoznam pozvanych kamaratok ako aj zoznam dvojic dievcat, ktore sa navzajom neznasaju a zacala zostavovat zasadaci poriadok. O hodnu chvilu ju zastihla Kristinka, ako sa stale trapi.
"Pozri, to je jednoduche," zacala Kristinka. "Najprv treba predsa usporiadat dievcata podla toho, s kolkymi inymi dievcatami sa neznasaju. Aha, Lucia sa znasa s najmenej ludmi, vecne sa hada s celou triedou. Tu usadime k prvemu stolu. Dalsia je Danka, ta je s Luciou na noze. Usadime ju k druhemu stolu. Potom mame Janku. Aj ona sa hada s Luciou, s Dankou je vsak zadobre, takze ju mozeme posadit tiez k druhemu stolu. Takto budeme pokracovat aj dalej: vzdy si vyberieme zo zoznamu dievca, ktore sa znasa s najmenej inymi dievcatami a postupne zistime, ci ju mozeme posadit postupne k prvemu, potom k druhemu a napokon k tretiemu stolu. Uvidis, takto sa nam zarucene podari vsetky usadit." No dievcata o chvilu zistili, ze ani Kristinkinym sposobom sa nedaju vsetky pozvane priatelky usadit. "V tom pripade ti neostava nic ine, ako poprosit otecka, aby zohnal este jeden stol, lebo ziadny iny sposob rozsadenia neexistuje," povedala Kristinka a odbehla. Zuzku vsak trapili pochybnosti:nenasiel by sa predsa len nejaky sposob, ako vystacit s tromi stolami?
Uloha: Zuzkine priatelky si oznacme cislami 1 az N. Vasou ulohou bude napisat program, ktory nacita zoznam dvojic znepriatelenych dievcat a najde Zuzke jedno mozne rozsadenie priateliek za tri stoly, alebo zisti, ze taketo rozsadenie nie je mozne. Ak ste presvedceni, ze Kristinkina metoda najde pripustne rozsadenie vzdy, ked existuje, naprogramujte ju. V tomto pripade od vas ocakavame aj zdovodnenie (dokaz) spravnosti vasho programu. Ak si naopak myslite, ze Kristinkina metoda niekedy nenajde rozsadenie priateliek a pritom taketo rozsadenie existuje, navrhnite a naprogramujte svoju vlastnu. Najdite aj nejaky protipriklad, alebo aspon zdovodnite, v com sa Kristinka myli.
3. Z Hanoja
Po navrate z potuliek po svete si Zoro opat povedal, ze urci datum konca sveta. Techniku sa naucil od hanojskych mnichov, ktori pouzivaju metodu MPV - metodu presuvania vezi. Na posvatnom stole su tri ocelove tyce, na ktorych su nastrkane mohutne kotuce roznej velkosti. Kedysi davno, ked bolo vyrieknute proroctvo, stali vsetky kotuce na prvej tyci, usporiadane od najvacsieho po najmensi. Vravi sa, ze ked budu vsetky kotuce presunute na druhu tyc, nastane koniec sveta. Avsak na presuvanie kotucov medzi tycami su definovane presne pravidla:
- kazdy presun trva presne jednu minutu,
- naraz sa presuva prave jeden kotuc,
- presun pozostava z odobratia vrchneho kotuca z niektorej tyce a jeho navlecenia na niektoru inu tyc,
- nesmie sa polozit vacsi kotuc na mensi.
Uloha: Zoro ma N roznych velkosti kotucov. Najmensich kotucov je presne A[1], druhych najmensich A[2], atd. az najvacsich je A[N]. Vsetky kotuce su na prvej tyci od najvacsich po najmensie. Pomozte Zorovi a napiste program, ktory nacita cisla N a A[1] az A[N] a vypise najkratsiu moznu postupnost presunov, pomocou ktorych mozno vsetky kotuce presunut z prvej tyce na druhu, pricom sa dodrzia vsetky pravidla. Pokuste sa odovodnit, preco vas program funguje spravne.
Priklad:
Vstup: Vystup:
N = 2, z 1 na 3
A[1] = 3, A[2]=2 z 1 na 3
z 1 na 3
z 1 na 2
z 1 na 2
z 3 na 2
z 3 na 2
z 3 na 2
4. Zanzibarsky vlacik
Zanzibarska slonovina vyniesla Zanzibarcanom na ich pomery nemale zisky a tak sa vlada rozhodla investovat do zlepsenia dopravnej situacie v krajine. Zanzibarske zeleznice ihned presadili nakup modernej vlakovej supravy, ktoru ich zeleznicna siet potrebuje ako sol. Do niektorych odlahlych stanic totiz este stale zabezpecovala dopravu parna lokomotiva. Pri tvorbe noveho cestovneho poriadku si vsak uvedomili, ze vsetky ich stanice su primale na to, aby sa tam nova vlakova suprava dokazala otocit. Preto pre lokomotivu chcu najst taku okruznu trasu, kde by sa nemusela otacat alebo cuvat. Taktiez chcu, aby okruh neprechadzal viackrat tou istou stanicou.Uloha: Zanzibarske zeleznice maju N stanic ocislovanych 1,...,N. Niektore stanice su navzajom poprepajane priamymi usekmi kolajnic, vsetky useky su obojsmerne. Napiste program, ktory nacita pocet zanzibarskych stanic N a dvojice stanic, ktore su priamo spojene zeleznicnou tratou a najde okruh, po ktorom moze premavat nova lokomotiva. Ak takych okruhov existuje viac, staci vypisat lubovolny z nich. Ak neexistuje ani jeden, program o tom vypise prislusnu spravu.
Priklad:
Vstup: Vystup: Pocet stanic: N = 6 Okruh ide cez stanice: Trate: 3 4 2 5 6 1 2 3 1 1 4 4 2 2 5 3 4 6 3 5 6
5. Z kuchyne
"Ja to takto robit nebudem," vyhlasil kuchtik Karol a dal si ruky vbok. "Ale neblbni, urcite sa to nejako da. Ved si len predstav, ze by sme niektoru z tych nadob museli vyliat - a bolo by po dvoch hodinach roboty," dovodil kuchtik Kveto. "Radsej si rychlo premyslime, ako to spravime, lebo o chvilu tu bude kuchar Kleofas a... Ved vies, aku ma velku varechu," pokracoval Kveto.
A coze to nasich kuchtikov takto trapilo? Vsetky nadoby, ktore v kuchyni mali, zaplnili rozlicnymi kremami do kralovskej torty. Vsetky nadoby az na jeden hrniec - do neho im ostavalo naliat presne n decilitrov mlieka na vanilkovy krem (div sa svete, ten este nemali). Ale beda, hrniec mal objem m dl. Je sice n<= m, ale k dispozicii maju iba velku kadu s mliekom (nevieme, kolko ho tam je, ale je ho tam velmi vela) a dve naberacky s objemami a a b dl. Hrniec je teraz prazdny a jedine, co mozu robit je nasledujuce:
- nabrat lubovolnu naberacku plnu mlieka z kade a a vyliat ju do hrnca (ak sa cely obsah naberacky do hrnca nezmesti, naleje sa po vrch hrnca a zvysok mlieka sa vyleje spat do kade),
- alebo nabrat lubovolnu naberacku plnu mlieka z hrnca a vyliat ju do kade (ak v hrnci nie je dost mlieka, naberie sa vsetko mlieko z hrnca).
Uloha: Pomozte kuchtikom a napiste program, ktory nacita cele cisla a, b, m, n (mozete predpokladat, ze plati a,b,n su z mnoziny {1,2,...,m}) a vypise postup operacii, alebo spravu, ze do hrnca nie je mozne dostat uvedene mnozstvo mlieka.
Priklad:
Vstup: Vystup: Naberacky: a = 4, b = 5 Pridaj 4 Objem hrnca: m = 6 Pridaj 2 Potrebne mnozstvo: n = 1 Odober 5
1998, Organizers of the CSP
