- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Priklady 4. kola
Mili nasi riesitelia,
v prvom rade Vas chceme upozornit, ze Vam teraz neposielame vzorove riesenia 3. kola - dostanete ich spolu so vzorovymi rieseniami tohto kola. Svoje riesenia nam posielajte do 18. maja 1998 a uz chceme len poznamenat:
Ked Ta zub boli, k zubarovi utekaj!
- O zivotnom prostredi
- O malom Tadeasovi
- O prekliatom meste
- O Rastovych otlakoch
- O funkcionalnom programovani IV
1. O zivotnom prostredi
Bolo to uz strasne davno co si mohol clovek vyjst volne do prirody, kochat sa jej krasou, dychat cerstvy a sviezi vzduch, pit vodu z potoka... Ludska hlupost znicila vsetku tuto krasu a dnesny clovek sa dennodenne stretava s nasledkami nepredvidaveho konania nasich otcov a starych otcov. Aj u nas je coraz vacsi problem napriklad s vodou, pretoze voda v potokoch je vacsinou znecistena kadejakymi chemikaliami, a dnesne fabriky a iny znecistovatelia badatelne znizuju aj kvalitu podzemnej vody.
Minuly rok sa preto Ministerstvo zivotneho prostredia rozhodlo vytvorit centralnu databanku vsetkych znecistovatelov. Zhromazdili si o kazdom z nich tie najpodstatnejsie udaje ako su poloha a polomer znecistovaneho uzemia. Sucasna kapacita dostupnych vodnych zdrojov nestaci, preto je potrebne kopat nove studne. Pri kopani studne treba vediet odhadnut priblizne znecistenie. Ministerstvo zivotneho prostredia sa rozhodlo zdarma poskytovat informaciu o tom, kolko znecistovatelov prispieva k znecisteniu toho ktoreho miesta. Ziadosti o tuto novu sluzbu je vela, preto ministerstvo potrebuje software, ktory by ich dokazal co najefektivnejsie spracovat.
Uloha: Napiste program, ktory na vstupe dostane pocet znecistovatelov N, o kazdom znecistovatelovi dostane tri cisla x, y a r, ktore urcuju, ze tento znecistovatel znecistuje kruh so stredom (x,y) a polomerom r. Dalej je na vstupe pocet otazok P a P suradnic miest (x,y). Vas program by mal pre kazde taketo mesto v co najrychlejsom case urcit pocet znecistovatelov, ktory miesto znecistuju.
Poznamka: Najdolezitejsie je, aby vas program vedel vyhodnotit znecistenie nejakeho miesta v co najkratsom case, aj na ukor pouzitej pamati. Mozete predpokladat, ze cislo P je daleko vacsie ako N.
Priklad:
Vstup:
N=2
(0,0), r=10
(3,3), r=1
P=4
(1,1), (10,0), (11,0), (2.5,2.5)
Vystup:
1 znecistovatel
1 znecistovatel
0 znecistovatelov
2 znecistovatelia
2. O malom Tadeasovi
Nedavno mal maly Tadeas prve narodeniny. Ked sa to verni rodinni priatelia Frutus a Brutus dozvedeli, nevahali a okamzite zabocili do najblizsieho hrackarstva, aby mu kupili nejake prekvapenie. Vysledkom ich uporneho snazenia vystihnut Tadeaskov vkus bolo N^3 kociek, asi polovica s obrazkami zvieratiek (to sa snazil Frutus) a zvysok s autickami (to zase Brutus). Od predavacky vymamili este zvysok baliaceho papiera, pozicali si noznice, sadli na zem a snazili sa co najrychlejsie kocky zabalit. Dohodli sa, ze bude najlepsie, ked bude balik vyzerat ako jedna velikanska kocka. Frutus poukladal kocky na papier, Brutus okolo nich ten papier obstrihal, noznice vratili a teraz dumaju, ci vystrihnutym utvarom mozno kocky obalit.
Uloha: Pomozte Frutovi a Brutovi - napiste im program, ktory ich problem vyriesi. Pre dane N, K, L a maticu nul a jednotiek s rozmermi KxL (jednotka znamena baliaci papier, nula nic) vypiste, ci je mozne plastom zadanym maticou obalit kocku s hranami dlzky N (male kocky maju hrany dlzky 1). Mozete predpokladat, ze matica ma prave 6N^2 jednotiek a oblast urcena jednotkami je suvisla. Zadany plast nemozno nastrihavat.
Priklad:
Vstup:
N = 2, K = 5, L = 9
000011000
011010000
011111011
111111110
101010100
Vystup:
Ano, tymto plastom sa daju kocky obalit.
Vstup:
N = 2, K = 4, L = 7
1111100
1111111
1111111
1111100
Vystup:
Nie, tymto plastom sa nedaju kocky obalit.
3. O prekliatom meste
"Utekajte, utekajte vo vsetky strany sveta. Bo kto v tomto meste ostane, svrab, lepra a zimnica ho postretnu a po celom tele mu navru pluzgiere velke ako hrach. Cely sa bude zvijat v krcoch a do dvoch dni ochrnie, takze nakoniec na slnecnej palave zhnije. Cesta, ktorou pojdete naskutku bodliacim, ostruzinou a jedovatymi kaktusmi zarastie, aby ziaden smrtelnik uz na toto miesto nikdy nevkrocil."
Toto a este mnoho horsich veci vestila carodejnica Nica kazdemu, kto sa prave vtedy nachadzal v Ciernom meste, kde ona vaznila princeznu Maju. A rytieri, hoci medzi nimi boli aj udatni bojovnici, sa vsetci rozbehli po uliciach mesta, aby z neho usli. A za kazdym bojovnikom cesta, po ktorej presiel, zarastala vsetkou tou pichlavou florou, ako Nica hovorila. Ked sa nakoniec dostali von z mesta, zistili, ze ich je ledva polovica. I zacali si klast otazky: "Nemohlo sa nas dostat z mesta viac? Mozno, ak by sme boli sli inymi cestami, aj dalsi mohli uniknut hroznym mukam, ktore Nica prorokovala..." a upadli do hlbokej depresie. Jedinym liekom na ich depresiu by bolo zistenie, ze viaceri uniknut nemohli.
Uloha: Zistite, kolko najviac rytierov mohlo ujst z mesta. Vieme, ze Cierne mesto ma tvar obdlznika a su v nom dva typy ulic - severojuzne a zapadovychodne. Pretinaju sa v krizovatkach. Severojuzne ulice znacime zo zapadu na vychod celymi cislami 1,...,m, zapadovychodne zo severu na juh cislami 1,...,n. Na vstupe je zadane m,n, pocet rytierov p a p usporiadanych dvojic (x[1],y[1]),...,(x[p],y[p]), ktore predstavuju pociatocne polohy rytierov (x[i] je cislo severojuznej a y[i] cislo prislusnej zapadovychodnej ulice). Rytieri mozu utekat iba po uliciach a na kazdej krizovatke mozu zmenit smer. Ak vsak nejaky rytier vkrocil na nejaku krizovatku, tato zarastie nepreniknutelnou hustavou, takze ziaden iny (a ani ten isty) rytier na nu uz viac nemoze prist (predpokladajte, ze dvaja rytieri nikdy nevojdu na ziadnu krizovatku sucasne). Ked rytier dorazi na niektoru z okrajovych krizovatiek, podarilo sa mu uniknut z mesta.
Priklad:
Vstup:
m=3, n=3, p=3
Rytieri: (1,1), (2,2), (3,2)
Vystup:
Mozu uniknut 3 rytieri.
Vstup:
m=5, n=5, p=5
Rytieri: (2,3), (3,2), (3,3), (3,4),
(4,3)
Vystup:
Mozu uniknut 4 rytieri.
4. O Rastovych otlakoch
Na okraji horskej luky sedi na snehu Rasto a place. Jeho nezbedny kamarat Dano mu pred turou nasypal do topanky kamienky. Rastovi od nich na pate vznikli paradne otlaky, po par kilometroch uz chudak od bolesti hadam ani nevedel, ako sa vola. So smutnym vyrazom si sadol, vyzul topanku, vysypal kamienky a z batohu vytiahol prenosnu lekarnicku. Chvilu sa snazil zalepit vzniknute otlaky, no coskoro to vzdal a teraz uz iba tisko vzlyka. Pomozte mu, kym neprechladne. Je to otazka (Danovho) zivota a smrti.Rastova pata sa da predstavit ako matica A x B nul a jednotiek, pricom nuly znamenaju zdravu pokozku, jednotky otlak. Kazdy otlak treba prelepit naplastou 3 x 1, pricom otlak musi zakryvat stredna, makka cast naplasti. Naplast sa da nalepit bud zvislo, alebo vodorovne, to znamena, ze naplast na otlaku so suradnicami (x,y) pokryje bud policka (x-1,y), (x,y) a (x+1,y) alebo policka (x,y-1), (x,y) a (x,y+1). Ziadne dve naplasti sa nesmu prekryvat (pokryvat to iste policko), pretoze prilis hruba vrstva naplasti by mohla uboheho Rasta tlacit.
Uloha: Napiste program, ktory nacita N - pocet Rastovych otlakov, suradnice jednotlivych otlakov a zisti, ci je mozne prelepit vsetky Rastove otlaky neprekryvajucimi sa naplastami. V pripade, ze to mozne je, vypiste aj jeden mozny sposob prelepenia, ak to nie je mozne, vypiste spravu "Chudak Rasto".
Priklad:
Vstup:
Pocet otlakov: 3
Suradnice otlakov:
(1, 0), (2, 1), (2, 3)
Vystup:
Otlak (1,0) prelepit zvislo
Otlak (2,1) prelepit zvislo
Otlak (2,3) prelepit vodorovne
Vstup:
Pocet otlakov: 5
Suradnice otlakov:
(3, 2), (4, 1), (5, 2), (2, 3), (3, 4)
Vystup:
Chudak Rasto
5. O funkcionalnom programovani IV
Opat (a minimalne v tomto roku naposledy) sme tu s nasim funkcionalnym jazykom, ktory uz tak doverne poznate z prvych troch kol. Tentokrat si zadefinujeme datovu strukturu reprezentujucu jednoduche aritmeticke vyrazy. Budeme uvazovat vyrazy, ktore obsahuju konstanty (z oboru prirodzenych cisel), premenne x0, x1, x2, ... a operacie scitania, odcitania a nasobenia. Formalne vyraz mozeme popisat nasledujucou definiciou:
- Ak k je prirodzene cislo, tak k je vyraz (konstanta).
- Ak kje prirodzene cislo, tak x_k je vyraz (premenna).
- Ak t1 a t2 su vyrazy, tak (t1 + t2) je vyraz.
- Ak t1 a t2 su vyrazy, tak (t1 - t2) je vyraz.
- Ak t1 a t2 su vyrazy, tak (t1 * t2) je vyraz.
- Nic ine nie je vyraz.
Ukazeme si teraz jeden z mnohych moznych sposobov, ako pomocou parovacej funkcie kodovat vyrazy do prirodzenych cisel, aby sme s nimi mohli pracovat v nasom funkcionalnom jazyku.
- Kodom konstanty k je cislo 1,k.
- Kodom premennej x_k je cislo 2,k.
- Nech kodom vyrazu t1 je cislo u1 a kodom vyrazu t2 je cislo u2. Potom kodom vyrazu (t1 + t2) je cislo 3,u,v.
- Nech kodom vyrazu t1 je cislo u1 a kodom vyrazu t2 je cislo u2. Potom kodom vyrazu (t1 - t2) je cislo 4,u,v.
- Nech kodom vyrazu t1 je cislo u1 a kodom vyrazu t2 je cislo u2. Potom kodom vyrazu (t1 * t2) je cislo 5,u,v.
Priklad: Kodom vyrazu ((x1+x3) * 4) je cislo 5,(3,(2,1),(2,2)),(1,4).
Ekvivalencia vyrazov. Ak vsetkym premennym nachadzajucim sa vo vyraze t priradime nejake hodnoty, mozeme vypocitat hodnotu vyrazu t. Dva vyrazy t1 a t2 nazveme ekvivalentne, ak pre lubovolne ohodnotenie premennych budu ich hodnoty rovnake.
Priklad: Pre ohodnotenie premennych x0=2, x2=1, x3=3 bude hodnotou vyrazu (x0+x3) cislo 5 a hodnotou vyrazu (x0+x2) bude cislo 3. Tieto vyrazy teda nie su ekvivalentne. Vyrazy ((x0+x1)-(0 * x2)) a (x1+x0) ekvivalentne su.
Uloha: Vo funkcionalnom jazyku napiste funkciu Ekviv(x,y), ktora dostane dva vyrazy zakodovane do prirodzenych cisel a zisti, ci su tieto dva vyrazy ekvivalentne. Funkcia vrati cislo 1, ak vyrazy su ekvivalentne, inak vrati cislo 0.
1998, Organizers of the CSP
