• 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

Korešpondenčný seminár z programovania

Priklady 3. kola

Mili nasi riesitelia,

v novom roku sa vam zas a znova ozyvame, aby sme vam opat priniesli nove zadania tentokrat uz tretieho kola KSPcka.

Predtym ako zacnete riesit priklady tohto kola, chceli by sme vas este poprosit, aby ste sa nad sebou zamysleli. Ani v najmensom ste nas totiz nepotesili urovnou popisov vasich rieseni. Casto nam dochadzaju riesenia nespravne, navyse bez popisu, pricom nakoniec vysvitne, ze ich autor, pokial by sa aspon na chvilku zamyslel, by na to prisiel aj sam. Opravovatelovi vsak najdenie kontraprikladu trva podstatne dlhsie (vsak sme uz stari, nie?)... Preto v opravovani pocitite v najblizsich dvoch kolach tieto zmeny: 1. Riesenia bez popisu alebo s nedostatocnym popisom budu automaticky hodnotene casto az 0 bodmi; 2. Riesenia bez zdovodnenia spravnosti alebo s nespravnym zdovodnenim spravnosti (pricom mozno pouzivat odkazy na literaturu), pokial opravovatelovi nebude evidentna ich spravnost, budu povazovane za nespravne. :-)

Dost bolo kritiky, teraz je rad na vas! Vase riesenia, navrhy a pripomienky nam posielajte do 24. februara 1997.

Kto neskoro chodi, ten daleko byva.

1. O magickom kruhu
2. O kolaci III
3. O vrabcovi Cin-cinovi I
4. O Burundijskych mapach
5. O Stevovej sieti III.

Stara saga vravi, ze niekde pri okraji Zemeplochy sa za davnych cias nachadzal kontinent menom Ulantida. Avsak pred viac nez mnohymi rokmi ho pohltilo more. Mnoho cestovatelov zahynulo pri hladani tohto kontinentu.

I carodej Taratlach sa vydal Utlantidu hladat. Kedze coskoro cesta pokracovala po dne oceanu, musel Taratlach (i ked s nevolou) prikrocit ku kuzleniu. Poziadat vodu, aby sa rozostupila, nemoze byt ziadny problem - ved to uz kedysi davno zvladol akysi Mojzis.

Text v jeho prirucnej prirucke hovoril, ze treba na plazi vyznacit kruh, postavit sa do stredu a odrieknut prislusnu magicku formulu. Potom neviditelna ruka vyznaci na plazi 666 priamok a co najrychlejsie treba vykriknut, kolkokrat sa priamky pretli vo vnutri kruhu.

Taratlach v matematike nikdy nevynikal a tak si spocital, ze by mu uz len spocitanie tych priamok trvalo dlhsie, ako stanoveny casovy limit. Teraz len smutne sedi na plazi a hladi do vln.

Uloha: Napiste program, ktory nacita cisla n (pocet priamok) a r (polomer kruhu) a n priamok, pricom kazda je dana suradnicami svojich dvoch bodov a spocita, kolko dvojic priamok sa pretne vnutri kruhu s polomerom r a stredom v pociatku suradnicovej sustavy.

Priklad:
Vstup:
r=3, n=4
priamka p: (-2,0), (0, 2)
priamka q: (-5,1), (5,1)
priamka r: (-1,0), (-1,-2)
priamka s: (4,7), (4,6)

Vystup:
Pretnu sa 3 dvojice
priamok (p a q, p a r, q a r).

V Nalomenej Trieske je nepisanym pravidlom, ze nevesta, ked sa vydava, musi upiect svadobny kolac. Velkost kolaca je umerna spolocenskemu postaveniu nevesty.

Prabantovka spomina: Joj, to za nasich mladych cias, to boli ine svadby ako teraz. Ale najkrajsiu svadbu mala kovacova Anicka, ked si brala richtarovie Ondra. Kolko prislo vtedy hosti! A kazdemu sa uslo z Anickinho kolaca. Anicka upiekla totiz kolac v tvare velkeho konvexneho mnohouholnika a dokonca do kazdeho z vrcholov male modre nic pridala (Ti vnimavejsi si uz urcite vsimli, ze kolac bol upeceny v tvare konvexneho tyblka). Kazdy kusok kolaca mal trojuholnikovy tvar, v kazdom vrchole kusok maleho modreho nic.

Vsetko prebiehalo hladko, az kym Duro, Anickin ohrdnuty pytac, nezacal rozhlasovat, ze Anicka taky velky kolac upiect nemohla. Ved plech, na ktorom by sa taky kolac dal upiect, hadam ani nejestvuje...

Urazeny kovac doniesol ohromny mnohouholnikovy plech, pozbieral vsetky kusky kolaca, zavolal ucitela, notara a farara a spolu sa pustili ukladat kusy kolaca na plech. Po hodnej chvili, ked zistili, ze to nie je az take jednoduche, pozorne zmerali kazdy kusok kolaca, zakreslili tvar plechu, farar s notarom sa pod to slavnostne podpisali. Potom konecne rozdali kolace a svadobna hostina sa mohla zacat... Kovac vypisal odmenu tomu, kto pomoze celej Nalomenej Trieske ukazat, ze Anickin svadobny kolac sa skutocne cely piekol na tom obrovskom plechu.

Uloha: Napiste program, ktory nacita tvar plechu (vrcholy konvexneho mnohouholnika vymenovane proti smeru hodinovych ruciciek), pocet kuskov kolaca a dlzky stran jednotlivych kuskov (tiez proti smeru hodinovych ruciciek) a vypise, ci sa kusky daju poukladat na plech tak, aby nic nezvysilo, aby bol cely plech pokryty a aby male modre nic boli vo vrcholoch plechu.

Priklad:
Vstup:
Suradnice vrcholov plechu:
(0.0;0.0), (3.0;0.0), (4.5;2.0),
(3.0;4.0), (0.0;4.0)
Kolace:
(3.0;4.0;5.0), (3.0;4.0;5.0), (2.5;2.5;4.0)
Vystup:
Kolace sa daju poukladat na plech.

Ked sa Cin-cin vratil zo stretnutia domov, chvilu veru rozmyslal, ci trafil spravne. Ved ano, trosku aj pili, ale zeby az tak? Rozhodne nieco nebolo v poriadku. Ale co? Cin-cin sa posadil na priedomie domu, o ktorom si este stale myslel, ze je jeho vlastny a pustil sa do tuheho premyslania.

A po case na to naozaj prisiel. Tie zbalene kufre boli tym, co sa mu nepozdavalo. Aby sa priznal, boli mu nanajvys podozrive, len si zial prave teraz nevedel spomenut, na co je taky kufor dobry. Nastastie o chvilu ku nemu pricupital maly vrabcek a skutocne netrvalo dlho, kym v nom Cin-cin spoznal svojho maleho Pim-pima, synacika, na ktoreho bol pravom hrdy.

A vtedy sa spamatal. Ved dnes je presne ten den, ked sa mali stahovat! Ale v tych dvoch kufroch asi nebude zbalene cele dvojposchodove hniezdo aj s nabytkom, uvazoval Cin-cin dalej. A potom je tu pelikan a prazdne skatule... Cin-cin zacinal tusit, co ho caka. Zvysne veci bude asi treba zbalit do tych skatul. Ale skatul nemozem pouzit vela, ved kto by sa s nimi nosil.

Uloha: Dane su cisla S - objem jednej skatule (vsetky skatule maju rovnaky objem), N - pocet zvysnych veci, ktore treba pobalit, a potom este N cisel - objemov jednotlivych veci. Vsetky tieto udaje su cele cisla. Cin-cin vie, ze keby chcel zistit, ako sa daju jeho veci pobalit do najmensieho mozneho poctu krabic, odpovede by sa nemuseli dozit ani Pim-pimove vnucata. Preto mu staci take usporiadanie, pri ktorom sa nepouzije viac ako dvojnasobok najmensieho mozneho poctu krabic, ale vysledok potrebuje rychlo, lebo pelikan caka. Napiste Cin-cinovi program, ktory najde taketo usporiadanie. Vystupom je pocet potrebnych skatul a zoznam obsahujuci pre kazdy predmet jeho objem a poradove cisla skatule, do ktorej ma byt pobaleny. Na poradi predmetov vo vystupe nezalezi. Takisto krabice si mozete ocislovat v lubovolnom poradi. Ak sucet objemov niekolkych predmetov neprevysuje objem krabice, tieto predmety sa daju do jednej krabice zabalit.

Poznamka: Kazde riesenie musi obsahovat okrem popisu aj dokaz spravnosti, t.j. dokaz, ze vase riesenie skutocne neprekroci dvojnasobok optimalneho poctu skatul. Riesenia bez dokazu budu obodovane (0 bodmi).

Poznamka: Tym, ktorym sa zda byt tento priklad lahky, odporucame vyriesit pozmenene zadanie: Najst co najefektivnejsi program, ktory najde pocet skatul a rozmiestnenie predmetov tak, aby ich nebolo viac ako tri polovice optimalneho poctu (pri neparnych cislach zaokruhlujeme podiel nahor). Samozrejme aj s dokazom. Ak ku svojmu rieseniu pribalite aj riesenie tejto druhej ulohy, mozete ziskat este niekolko bodikov navyse.

Kmene v Burundi sa konecne rozhodli zit v pokoji a mieri. Kral Burundi sa tomuto ich rozhodnutiu najskor velmi zacudoval, zdalo sa mu, akoby ani svoju vlastnu zem nespoznaval. Ale on, ucena hlava, nastastie vedel, co robit.

Takmer vsetci Burundijcania boli bojovnici, a ked z nich opadne vlna nadsenia z nastoleneho mieru, vsimnu si, ze stratili pracu. Treba ich teda niecim zamestnat, aby si tuto holu skutocnost vsimli co najneskor. "Ale cim?" hutal kral. A vtedy na to prisiel.

Treba nakreslit mapu Burundi! Potom si ju bude chciet kazdy obkreslit a doma, ako hrdy Burundijcan, vyvesit na stenu. To zaberie dost casu, lebo v Burundi maju len pat farbiciek, ktore u nich zabudol nejaky stroskotanec. Lenze vychyreny a konkurzom vybrany kreslic map, jediny, ktory sa v Burundi nasiel, vie, ze mapa ma kazde uzemne teritorium zafarbene takou farbou, akou nie je zafarbene ziadne susedne teritorium. A v Burundi je len tych pat povestnych farbiciek...

Uloha: Napiste kreslicovi map program, ktory najde zafarbenie mapy Burundi najviac piatimi roznymi farbami. Vstupne hodnoty pre vas program su: N - pocet kmenov v Burundi a pre kazdy kmen zoznam susednych kmenov a zoznam kmenov, ktore susedia so zvyskom sveta. Dva kmene (resp. kmen a zvysok sveta) su susedne, ak ich teritoria maju spolocnu hranicu. Teritorium kazdeho kmena je suvisly utvar. Vystupom je zafarbenie jednotlivych uzemnych teritorii v Burundi (aj zvysok sveta musi mat nejaku farbu, ta sa vsak samozrejme moze vyskytovat aj na nejakych s nim nesusednych teritoriach).

Poznamka: Predpokladajte, ze vstup je zadany spravne, tj. mozete predpokladat, ze zadane vstupne hodnoty skutocne zodpovedaju nejakej mape nakreslenej na papieri.

Priklad:
Vstup:
pocet kmenov N = 6
susedia kmena 1: 2, 3, 4 a zvysok sveta
susedia kmena 2: 1, 4, 6 a zvysok sveta
susedia kmena 3: 1, 4, 5, 6 a zvysok sveta
susedia kmena 4: 1, 2, 3 a 6
susedia kmena 5: 3, 6, 7 a zvysok sveta
susedia kmena 6: 2, 3, 4, 5 a zvysok sveta
susedia zvysku sveta: 1, 2, 3, 5 a 6
Vystup:
Zafarbenie teritorii:
kmen 1: zelena
kmen 2: cervena
kmen 3: cervena
kmen 4: zlta
kmen 5: zelena
kmen 6: biela
Zvysok sveta: zlta

Kamarati si uspesne zvolili sefa a s elanom sa pustili do pisania prefikanej sietovej aplikacie (PSA). Ale Steva nebavilo dlho na strome sediet a do laptopa hladiet a zacal presviedcat svojich kamaratov nech sa idu este pozriet, ako svet vyzera z najblizsieho kopca. Ale kamarati boli prilis zaujati tvorbou PSA a vobec sa im nechcelo plahocit sa na nejaky kopec. A tak sa Stevo rozhodol, ze pojde sam. Zbalil laptop aj obidve snury, ktore ho spajali so susednymi pocitacmi a sviznym krokom zmizol z dohladu.

Kamarati medzicasom dopisali PSA a prvykrat ju spustili. V programe vsak bola chyba a ta mala katastrofalne nasledky - kazdemu pocitacu sa vymazali nielen vsetky dolezite informacie o sieti a o sefovi ale dokonca aj jeho vlastne meno. Ubohym kamaratom teraz nefunguje ziaden z ich algoritmov a su z toho uplne zufali.

Uloha: Vsetky pocitace su pospajane do jedneho radu, kazdy pocitac okrem dvoch krajnych je spojeny so svojimi dvoma susedmi priamymi linkami, krajne pocitace su spojene prirodzene len s jednym susedom.

Kazdy pocitac ma svoje linky ocislovane cislami 1 a 2 (pripadne len 1). Ak su pocitace A a B spojene linkou, moze napriklad pocitac A poslat spravu pocitacu B, sprava sa zaradi do mailboxu pocitaca B.

Pocitace vsak nemaju ziadne jednoznacne oznacenie. Ulohou je ocislovat ich cislami od 1 po p, kde p je pocet pocitacov v sieti tak, aby ziadne dva pocitace v sieti nemali rovnake cisla. Napiste program, ktory spustia vsetci Stevovi kamarati na svojich laptopoch, pricom po jeho skonceni kazdy z pocitacov pozna svoje cislo.

Pre komunikaciu medzi pocitacmi mate k dispozicii tieto procedury (pre jazyk C, pripadne iny jazyk zadefinujte procedury s podobnou strukturou; smes je to iste co string, iba s neobmedzenou dlzkou):

• Send(sprava:smes; linka:integer) - pocitac posle spravu sprava po linke linka.
• Receive(var sprava:smes; var linka:integer) - vyberie z mailboxu jednu spravu a vrati v premennej sprava jej obsah a v premennej linka udaj o tom, z ktorej linky sprava prisla. Ak ziadna sprava v mailboxe nie je, Receive caka az kym tam nejaka nebude.
• NumberOfLinks(var n:integer) - do premennej n ulozi pocet liniek, ktore vedu z pocitaca (n = 1 alebo 2).

Poznamka: Snazte sa, aby pocitace skoncili skor, ako studenti podlahnu beznadeji a rozhodnu sa zbalit celu pocitacovu siet a bezat za Stevom (toho by aj tak nedobehli a este by mohli zabludit). Linky su pomale a preto sa snazte, aby ste toho neprenasali zbytocne vela.

Poznamka 2: Cislo p na zaciatku behu programu nie je zname. Mozete vsak predpokladat, ze je neparne.

Poznamka 3: V rieseni nepouzivajte generator nahodnych cisel.