• 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

Priklady 2. kola

Mili nasi riesitelia,

Je tu sychravy november a s nim zadania druheho kola KSP. Ked nebudete mat pocas dlhych jesennych vecerov co robit, iste si na ne najdete cas. Riesenia druheho kola nam posielajte do 10. januára 2000. Spolu s rieseniami nezabudnite poslat známky v celkovej hodnote 10.- Sk. Pre istotu vam uz teraz prajeme vesele Vianoce a do noveho roku vela stastia, zdravia a tiez vela dobrych napadov pri programovani.

KSPaci

1. O krizovom stabe
2. O telocviku
3. O lyziaroch
4. O prederavenej sterche
5. O ubohom kralovicovi

---

1. O krizovom stabe

Mimozemstan Martow sa prave vratil z diplomatickej misie na vzdialenej planete s nazvom Zem. Nedockavo vykukol z okienka svojej vesmirnej lode. Ako vsak coskoro zistil, na jeho domacej planete zdaleka nebolo vsetko tak, ako malo byt...

Na Martowovej planete je N miest. Medzi kazdymi dvomi mestami bolo vybudovane obojsmerne teleportove spojenie. Z neznamych pricin sa vsak vsetky teleporty naraz pokazili a teraz kazdy z nich funguje len jednym smerom. Mimozemstania sa rozhodli situaciu riesit ustanovenim krizoveho stabu. Kazde mesto bude mat v stabe svojho zastupcu. Stab sa musi stretnut co najskor. Za miesto stretnutia je teda nutne zvolit take mesto M, aby sa clen, ktoremu bude cesta trvat najdlhsie, dostal do mesta M co najskor, t.j. na najmensi mozny pocet pouziti teleportov. Inymi slovami, vzdialenost (pocitana v pocte pouzitych teleportov) z najvzdialenejsieho mesta do mesta M musi byt najmensia mozna.

Uloha

Napiste program, ktory nacita pocet miest N a popis jednotlivych teleportov a vypise cislo mesta M, v ktorom ma zasadnut krizovy stab. Popis teleportov ma nasledujuci format: pre kazde mesto i je dany pocet teleportov p[i], ktore vedu z tohto mesta. Dalej je dany zoznam p[i] miest, do ktorych vedu teleporty z mesta i. Mozte predpokladat, ze v zozname sa z dvojice i -> j a j -> i vyskytne prave jeden teleport pre kazde i, j, i<> j. Ak je vyhovujucich miest na stretnutie stabu viac, vypiste lubovolne z nich.

Poznamka

Sucastou vasho riesenia by malo byt aj zdovodnenie jeho spravnosti.

Priklad

Vstup
N=5

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

Vystup

3

(Z mesta c. 4 sa sem da dostat pomocou dvoch teleportov, z miest c. 1, 2 a 5 pomocou jedneho teleportu.)

---

2. O telocviku

Risko, Vladko, Davidko, ako poriadni ziaci, pravidelne chodia na telocvik. Radi nan chodia, mozu sa tam veselo zahrat s loptou spolu s ich telocvikarom - ujom Marianom. Ujo Marian je prijemny bradaty pan, ma ale jednu chybu - rad dava za trest svojim ziakom klikovat pouzivajuc pri tom s oblubou frazu: "Daj si dvadsat!"

Jedneho dna prisli vsetci, cela trieda, neskoro na telocvik. Vbehli spolu do telocvicne, ale beda! Zjezena brada uja Mariana nevestila nic dobreho. Tak sa ziaci rychlo postavili do radu, ako to zvyknu robievat vzdy na zaciatku hodiny. Lenze rad sa akosi ujovi Marianovi nepacil. 'Musim im dat za trest klikovat. Kolkoze klikov?', huta si. 'Nestoja pekne podla vysky, nestihli sa v tom zhone usporiadat.' Zacne ratat, kolko dvojic ziakov je navzajom vymenenych (dvojica je vymenena, ak vyssi stoji pred nizsim). Tolko klikov dostane kazdy z nich za trest. Ale dajako mu to v tom zhone nejde. Pomozte mu!

Uloha

Na vstupe je dany pocet ziakov N. Ziaci maju vysky cele cisla 1 az N. Kazda vyska sa vyskytuje v triede prave raz. Dalej su na vstupe dane vysky ziakov a₁, a₂, ... a_N v tom poradi, v akom stoja v rade. Zratajte pocet vsetkych "vymenenych" dvojic v rade, t.j. takych dvojic a_i,a_j (i<j), ze a_i<a_j.

Priklad

Vstup
N=5

3 2 4 1 5

Vystup

4

Poznamka:

Su to dvojice: (3,2), (3,1), (2,1), (4,1).

---

3. O lyziaroch

Mt. Kopec je vychyrene lyziarske stredisko. Je na nom mnozstvo svahov idealnych na lyzovanie, kratsich, dlhsich, strmsich i menej strmych. A co je najlepsie, na hornom aj dolnom konci kazdeho svahu je horska chata, v ktorej si lyziari mozu kupit teply caj s rumom, parky, alebo aspon horalku. Jedine, co svahom na Mt. Kopci chyba, su lanovky. Je totiz velmi neprijemne, ked si lyziar po zideni svahu musi dat lyze na plece a sliapat naspat do kopca peso. Preto sa lyziari (a samozrejme chatari, ktorym to prinesie zisk) rozhodli postavit sustavu lanoviek tak, aby sa postupnostou vyvezeni lanovkou a zideni svahov dalo dostat na lubovolny svah (a do lubovolnej chaty, samozrejme). Aby usetrili, rozhodli sa stavat len jednosmerne lanovky a prirodzene, chceli by ich postavit co najmenej. Nevedia vsak ako na to a boli by radi, keby ste im pomohli.

Uloha

Na Mt. Kopec je N chat ocislovanych 1 az N. Medzi nimi vedie M svahov, kazdy svah vedie medzi dvoma chatami. Zjazdovat sa po nom da iba od vyssie polozenej chaty k nizsie polozenej. To znamena, ze ak sa da nejakou postupnostou svahov dozjazdovat od chaty i po chatu j, urcite sa neda dozjazdovat od chaty j po chatu i. Napiste program, ktory nacita cisla M a N a zoznam svahov (kazdy svah je urceny dvojicou vyssie polozena chata, nizsie polozena chata) a vypise, medzi ktorymi dvojicami chat je potrebne postavit jednosmernu lanovku, aby sa postupnostou vyvezeni lanovkou a spusteni sa po svahu dalo dostat z kazdej chaty do kazdej inej. Pocet postavenych lanoviek ma byt minimalny.

Priklad

Vstup
N=4,M=4

svahy: z 1 do 2, z 1 do 3, z 2 do 3, z 2 do 4

Vystup

Je treba pridat lanovky z 3 do 1 a zo 4 do 1. (ine riesenie: z 3 do 2 a zo 4 do 1)

---

4. O prederavenej streche

Janko, Marienka, ich deturence a vsetci jazvecici po dlhych vypoctoch lacno docestovali do pernikovej chalupky hlboko v~tmavom lese. Deti s~jazvecikmi zatial velmi vyhladli a zivelne sa pustili do sladuckej chrumkavej strechy. V~streche tak zial vznikli diery, ktorymi fukala chladna neprijemna jesen. Marienka sa rozhodla napiect perniky, ktorymi by vsetky diery poplatala. Zamiesila cesto na perniky, avsak zistila, ze v chalupke nemaju ziadny valok. Chce preto poslat Janka do mesta nejaky kupit, len nevie, aky siroky potrebuje. Kedze Janko je velmi sporivy, chce kupit co najlacnejsi (a teda najuzsi).

Marienka chce vyvalkat obdlznikovy pas cesta, z ktoreho potom bude vykrajovat jednotlive zaplaty. Pas moze byt lubovolne dlhy, avsak moze byt siroky najviac tak ako valok. Pre kazdu zaplatu (konvexny N-uholnik), ktory musi vykrojit, je potrebne spocitat, z akeho najuzsieho pasu cesta sa da vyrezat. Zaplatu a cesto je mozne voci sebe navzajom lubovolne otacat a posuvat.

Na vstupe je cislo N>2 a suradnice N bodov x_i, y_i (i=1...N) konvexneho N-uholnika. Napiste program, ktory zisti, aky najmenej siroky pas cesta je nutne vyvalkat, aby sa z neho dal vyrezat dany N-uholnik. Snazte sa najst co najrychlejsie riesenie, lebo sa blizi burka a...

Priklad

Vstup
N=4
(1,1.5), (2,0), (2,10), (0.5,3)

Vystup
1.5

Poznamka

Okraje pasu tvoria priamky [2,0][2,10] a [0.5,0][0.5,3].

---

5. O ubohom kralovicovi

Kde bolo, tam bolo, niekde uprostred lesa medzi piatym a siestym kopcom bolo malicke kralovstvo. V tomto kralovstve vladol mlady kralovic Richard. Kedze mu bolo na trone smutno, rozhodol sa zaobstarat si nejaku rucu manzelku. Vybral sa teda do sveta, chodil, bludil, az navela prisiel do kralovstva mocneho krala, ktory mal zhodou okolnosti jedinu dceru Pamelu, akurat sucu na vydaj. Richard ju hned poziadal o ruku. Ked vsak zistil, aka to je skrata, pokusil sa od svojej ponuky odstupit. Nie velmi uspesne...

O par dni neskor. Na hladomorni sa otvorili dvere. Dovnutra vstupil kat a kral. "Tak ti dam este jednu sancu" prehovoril kral. "Budeme hrat. Ak vyhras, tak ta pustim domov, ak nie, ech, tak si vezmes moju dceru Pamelu za zenu a odides s nou vladnut. Co na to vravis?" Co uz mal nas ubohy kralovic robit, neostalo mu nic ine ako suhlasit.

Kral vytiahol z vrecka hraci plan -- dlhocizny uzky pas latky, na ktorom bolo N (velmi vela) policok vedla seba ocislovanych od 1 po N. Potom na styri rozne policka polozil styri kamienky. Hrac, ktory je na tahu, moze zobrat jeden kamienok a posunut ho o niekolko (aspon jedno) policok smerom k zaciatku planu (t.j. na policko s mensim cislom), pricom nesmie preskocit ziaden iny kamienok. V ziadnom okamihu nesmie byt na ziadnom policku viac ako jeden kamienok. Ten kto nemoze tahat, ani keby sa potrhal, tak ten prehral. Kral ako stary gavalier ponukol Richardovi prvy tah.

Ked ubohy Richard podumal nad hrou, zlakol sa, ze sa mu nepodari vyhrat a zbledol. Musite mu preto pomoct.

Uloha

Napiste program, ktory nacita poziciu styroch kamienkov na zaciatku hry. Potom bude striedavo vypisovat svoje a nacitavat kralove tahy az do konca hry. Snazte sa, aby vas program hral co najlepsie.

Pozicia pocas hry a mozny Richardov tah:

---

(c) November 1999

---