• 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 3. kola

Tak sme tu zase.

A s nami ako vzdy prichadzaju cerstve zadania KSP, tohto rocnika uz tretie. Co k nim povedat? Hadam iba, aby ste riesili, riesili, vyriesili a svoje riesenia nam poslali do 1. marca spolu s dakymi tymi znamkami. Ak hladate vzorove riesenia, hladate marne. Dostanete ich neskor (spolu so zadaniami 4. kola). S pozdravom

Nie je vsetko, co sa blysti
KSPaci

1. O svokre
2. Ako si Janko s Marienkou zivnost zalozili
3. Santo, Banto a parcela
4. O reforme
5. O profesorovi Indigovi a vile Amalke III

---

1. O svokre

Medzi Bonifacove vasne patri na poprednom mieste cyklistika. Stalo sa vsak, ze ho raz prisla navstivit svokra. Ked uz u neho byvala vyse mesiaca a terorizovala ho neustalym vysavanim, upratovanim a umyvanim riadu, rozhodol sa zufaly Bonifac konecne konat. Navrhol svokre bicyklovy vylet. Svokra ihned suhlasila, netusiac, co cini. Bonifac totiz sedi nad mapami v snahe najst taky ciel ich bicyklovej vychadzky, ktory by netrenovana svokra nezvladla.

Uloha: Mapa je reprezentovana polom M x N, pre kazde policko je dana jeho nadmorska vyska v[i,j] v metroch. Dalej je dane cislo K, ktore urcuje, kolko metrov zvladne svokra dokopy vystupat pocas jednej bicyklovej vychadzky. Bonifac so svokrou zacinaju cykloturu na policku so suradnicami (r,s).

Pocas vyletu prechadzaju iba medzi polickami susediacimi hranou a medzi dvoma susediacimi polickami cesta bud rovnomerne stupa, alebo rovnomerne klesa, alebo vedie vodorovne. Vodorovne a klesajuce useky pre svokru nepredstavuju ziadnu namahu, do celkoveho stupania sa teda zapocitavaju iba stupajuce useky. Napiste program, ktory najde taky ciel cesty, do ktoreho sa svokra nedostane. Predpokladajte, ze svokra si pre dany start a ciel vzdy najde cestu s minimalnym celkovym stupanim.

Priklad:
Vstup:
M = N = 4, K = 11
Vyskova mapa :
(lavy dolny roh je (4,1))

 8.0   6.0   8.0  12.0
 1.0   7.5   4.0   1.0
 2.0   2.0   5.5   1.2
13.0   2.0   1.0   6.2

Start: (3,2)

Vystup:
Koniec: (1,4)
Prevysenie: 11.5

---

2. Ako si Janko s Marienkou zivnost zalozili

``Hotovo'' - povedal Janicko, ked sa mu podarilo nainstalovat posledny kusok pernika na vetrak. Netrvalo dlho a po celom okoli sa roznieslo, akyze to maju Janko s Marienkou domcek. Detvaky z dediny chodili obdivovat vsetky tie dobroty. I napadlo ich, co tak si zivnost zriadit a detvakom z dediny perniky i sladke medovnicky predavat, aby im z sibalstva z novej chalupky nebodaj neodjedli. Nuz oprasila Marienka sladke recepty starej matere a zamiesila plne koryto cesta s hrozienkami. Cely den obaja valkali, vykrajovali, cesto do pece strkali, upecene kolace z pece vytahovali. Vecer im ostal iba jeden kus cesta tvaru obdlznika A x B. Janko schytil staru znamu kruhovu formicku, co nou kedysi vetrak vykrajoval a podho vykrojit si taky kus, ktory by co najviac hrozienok obsahoval. Prikladal Janko formicku tak i onak, ale stale sa mu nejak videlo, ze by on aj viac hrozienok mat mohol.

Uloha: Napiste program, ktoreho vstupom su rozmery zvysku cesta A x B, polomer formicky r, pocet hrozienok N a suradnice jednotlivych hrozienok (x1,y1), (x2,y2) ... (xN,yN) a ktory najde stred kruhu s polomerom r, ktory cely lezi v ceste a obsahuje maximalny mozny pocet hrozienok (hrozienka na hranici kruhu patria dovnutra kruhu).

Priklad:
Vstup:
A = 4.0, B = 4.0, R = 1.0
Hrozienka:
(1.0,0.0), (2.0,0.0), (3.0,0,0), (2.0,1.0), (1.0,2.0), (3.0,2.0)

Vystup:
stred: (2.0,2.0)
(3 hrozienka)

---

3. Santo, Banto a parcela

Banto sa nedavno opat vybral do krcmy vo Vysnej Klondike. Ake bolo Santovo prekvapenie, ked sa ani nie o dve hodiny vratil triezvy, ale o to smutnejsi. V krcme sa totiz dozvedel, ze vyslo nove nariadenie, ktore by mohlo ohrozit ich parcelu.

Santo s Bantom vlastnia parcelu tvaru konvexneho N-uholnika. V kazdom jeho vrchole je zatlceny kolik. Nie je to bohvieaka parcela, ale za tie roky, co na nej stravili ryzovanim zlata, im prirastla k srdcu. Nove nariadenie hovori toto:

• 0. Rusi sa stare vymedzenie parciel.
• 1. Kazda nova parcela musi mat tvar trojuholnika.
• 2. Hranice parcely sa vyznacuju spagatom. Spagat moze viest medzi lubovolnou dvojicou kolikov.
• 3. Nie je dovolene zatlkat nove koliky za ucelom vyznacenia hranice parcely.
• 4. Spagaty vyznacujuce hranice parciel sa nesmu nikde krizovat.
• 5. Koncom tyzdna budu vsetky parcely, ktore nebudu mat tvar trojuholnika, prevedene pod spravu serifskeho uradu.

Santa napadlo, ze by mohli kupit spagat a pokusit sa ho natiahnut medzi koliky tak, aby rozdelili parcelu na trojuholniky. Tak by sa mohli vyhnut tomu, aby bola ich parcela zhabana v prospech serifskeho uradu. Skor ako posle Banta do obchodu by rad vediet, ako vlastne ma spagaty natahovat, aby minul co najmenej spagatu a kolko spagatu vlastne potrebuje. A tak, kym Banto smutne sedi na pelasti a cumi do steny, Santo sedi nad nakresom parcely a snazi sa zistit, ako najvyhodnejsie natiahnut spagaty.

Uloha: Na vstupe je dane cislo N a suradnice N vrcholov (x1,y1), (x2,y2), ... (xN,yN) parcely vymenovanych proti smeru hodinovych ruciciek. Napiste program, ktory poradi Santovi, medzi ktorymi dvojicami kolikov ma viest spagat, aby ho minul najmenej, ako aj celkovu dlzku potrebneho spagatu (spagat mozno aj nastrihat).

Priklad:
Vstup:
N = 5
Vrcholy: (0.0,2.0), (2.0,0.0), (6.0,2.0), (4.0,5.0), (3.0,5.0)

Vystup:
Spagat natiahnut medzi kolikmi: (2,5), (3,5), (1,2), (2,3), (3,4), (4,5) a (5,1)
Dlzka spagatu je spolu 25.490.

---

4. O reforme

Za cias panovania krala Klohodrabata VII. vladla na Kiribati anarchia. Po jeho smrti sa jeho syn Kiripraluk III., naslednik tronu, rozhodol, ze kralovstvo pozdvihne k rozkvetu. Zvolal mudrcov z celej krajiny, aby spolu vypracovali plan obnovy kralovstva. Po dokladnej analyze sucasneho stavu dospeli mudrci k zaveru, ze najpv je treba pozdvihnut uroven vzdelania (co ine uz od mudrcov mozete cakat). Tak Kiripraluk navstivil kralovsku kniznicu. To co uvidel ho veru nepotesilo. Bola tam jedna polica zaprasenych knih a podriemkavajuci knihovnik v kute. "Kde su ostatne knihy?!" - cudoval sa kral. Dozvedel sa, ze ziadne dalsie nie su, a aj z tychto je iba po jednom rukopise. Tak sa rozhodol dat rozmnozit aspon tie knihy, ktore mali. Najal vsetkych pisarov, ktori v krajine este zostali, a prikazal im mat o tyzden z kazdej knihy dalsiu kopiu.

Uloha: Je dany pocet knih N, pocet pisarov K (K lt;= N) a pocty stran p_1,...,p_N jednotlivych knih v poradi, v akom su knihy na polici ulozene zlava doprava. Kazdemu pisarovi pridelime niekolko knih ulozenych na polici vedla seba. Kazdu knihu celu prepisuje jeden pisar, kazdy pisar musi prepisat aspon jednu knihu. Urcite, ako rozdelit knihy medzi pisarov tak, aby celkovy cas prepisovania bol minimalny.

Cas prepisovania jedneho pisara je umerny celkovemu poctu stran, ktore ma prepisat. Celkovy cas prepisovania je cas, ktory dosiahne pisar, ktory ma najviac prace.

Priklad:
Vstup:
N = 9, K = 3
Pocty stran:
100 200 300 400 500 600 700 800 900

Vystup:
Prvy pisar: 100 200 300 400 500
Druhy pisar: 600 700
Treti pisar: 800 900
(celkovy cas: 1700 stran)

---

5. O profesorovi Indigovi a vile Amalke III

Profesor Indigo si listoval v zbierke prikladov KSP a ked si cital priklady prveho kola deviateho rocnika, narazil na takyto priklad:

O kolaci.
Na obdlznikovom plechu upiekli (mimochodom nie velmi dobry) kolac rozmerov M\times N (rozmery kolaca a plechu boli rovnake) a rozrezali ho na K kusov. Vsetky kusy boli obdlznikoveho tvaru, ale ich rozmery sa navzajom znacne lisili. Hostia sadli ku stolu s kolacom, ale kedze sa velmi nemali k jedeniu, zacali si kratit dlhu chvilu skladanim nakrajanych kuskov kolaca do povodneho tvaru, teda do tvaru, aky mal na plechu. Pritom im najvacsie problemy robilo zistenie rozmerov plechu, na ktorom sa kolac piekol. Po dlhej a namahavej praci sa dohodli na tom, ze tato uloha nie je suca pre nich, ale pre ucastnikov KSP.

Uloha: Je dany pocet K nakrajanych kuskov kolaca obdlznikoveho tvaru rozmerov X[i],Y[i] (i=1,2,...,K). Napiste program, ktory zisti, ake mohli byt rozmery plechu M x N, na ktorom bol dany kolac upeceny (staci jedno riesenie).

Poznamka: Pre jednoduchost predpokladajte, ze rozmery kolaca ako aj rozmery nakrajanych kuskov su celociselne.
Poznamka: Vysledkom programu su len rozmery M a N, neziada sa najst rozlozenie danych kuskov na plechu!
Poznamka pre menej chapavych: Pri peceni je cely plech pokryty cestom.

Profesor sa rozhodol napisat program pre PP Amalka inside, ktory by pre dane rozmery kolaca M a N a zoznam rozmerov jednotlivych kuskov kolaca zistil, ci sa kusky kolaca daju naukladat na plech. Ako na potvoru ma prave zlomeny malicek a nemoze programovat...

Uloha: Napiste program pre PP Amalka inside, ktory za pomoci vily Amalky zisti, ci sa kusky kolaca daju na plech naukladat. Vas program by (v Pascale) mal mat hlavicku:

const MAX = 1000;
type obdlznik = record a,b : integer; end;
     zoznam_kuskov = array[1..MAX] of obdlznik;
program O_kolaci(M,N,K : integer; Zk : zoznam_kuskov);

---

1998, Organizers of the CSP

---