- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Príklady 2. kola letnej časti 21. ročníka KSP
Milí riešitelia!
Tak nám po dlhej zime vykuklo slniečko a jar zaklopala na dvere. Príroda rozkvitá, zvieratá sa zobúdzajú zo zimného spánku a medzi iným sme sa prebudili aj my a dali sa do práce. A tak sa Vám konečne dostáva do rúk čerstvé a ešte teplé KSPčko. Riešenia tohto kola nám posielajte do 31. mája 2004 a nezabudnite priložiť pár známok v hodnote okolo 15 korún, aby sa Vám mohli aj bez problémov opravené vrátiť.
KSPáci
1. O binárnom kamzíkovi
(15 bodov)
Ako ste už asi podľa nadpisu zistili, táto úloha bude o hre Binárny kamzík. Túto hru už snáď každý pozná a tak inovatívne pozmeníme pravidlá: V rade stojí N programátorov očíslovaných od 1 po N. Programátori sa rozdelia do rôznych skupín. Každý z nich môže byť vo viacerých skupinách. Na začiatku každý stojí v podrepe. Každá skupina sa môže rozhodnúť či urobí zmenu. Zmena spočíva v tom, že každý programátor v skupine zmení svoj stav. Ak bol v podrepe, tak sa postaví a ak stál tak sa dostane do podrepu. Musíte uznať, že byť v podrepe je trochu nepohodlná a namáhavá (hlavne pre programátorov) činnosť. Ich cieľom je urobiť postupnosť takých zmien, že na záver budú všetci stáť. Kedže sú takto fyzicky namáhaní, nevedia si to rozmyslieť. Pomôžte im!
Úloha
Na vstupe je číslo N – počet programátorov a M – počet skupín. Pre jednoduchosť očíslujme skupiny programátorov od 1 po M. Ďalej nasleduje M riadkov, v každom riadku je zapísaná jedna skupina programátorov (v i-tom riadku je i-ta skupina). Prvé číslo v tomto riadku je K – počet ľudí v skupine, po ktorom nasleduje K čísel z intervalu 1 až N, každé najviac raz. Výstupom bude poradie skupín, v akom majú zmeniť svoj stav, tak aby programátori vo všetkých skupinách naraz stáli, pokiaľ existuje riešenie, inak vypíšte, že úloha nemá riešenie. Pokiaľ je takýchto riešení viac, stačí vypísať ľubovolné.
Príklad
Vstup #1
N=3 M=2
2 1 2
2 2 3
Výstup #1
Úloha nemá riešenie.
Vstup #2
N=5 M=4
3 1 3 5
4 2 1 4 5
2 1 5
3 3 5 4
Výstup #2
1 2 3 (1. skupina, 2. skupina, 3. skupina, v poradí v ako prichádzali riadky, charakterizujúce skupinu)
Vysvetlíme druhý vstup: Je 5 programátorov, ktorý sú v 4 skupinách. Prvá skupina má 3 členov a sú to programátori 1, 3, 5. Druhá skupina má 4 členov a sú to programátori 2, 1, 4, 5. Tretia skupina má 2 členov - programátorov 1 a 5. Na záver štvrtá skupina má troch členov: 3, 5, 4.
2. O zlatokopovi Kleofášovi
(15 bodov)
Na Vyšnej Klondike bolo objavené zlato. Bane rástli ako huby po ďaždi. Zlatokopi z celého sveta sa tam zišli, aby si každý uchmatol kúsok zlata aj pre seba. Kleofáš nebol výnimkou. Za posledné peniaze si kúpil krompáč a vydal sa kopať. Hneď si však uvedomil, že nie v každej bani sa nachádza rovnako veľa zlata. Prišiel na miestny zlatokopecký úrad, aby si prečítal najnovšie štatistiky o jednotlivých baniach. V tej spleti údajov sa však Kleofáš nevie vyznať a preto vás prosí o pomoc. Pomôžte chudákovi Kleofášovi nahrabať si čo najviac zlata a napíšte program, ktorý určí, kde má Kleofáš ťažiť.
Úloha
Na vstupe dostane váš program popis jednotlivých baní a ciest medzi nimi. Na prvom riadku sú čísla N – počet baní a M – počet ciest medzi nimi. Na ďalších M riadkoch sú tri čísla i, j, d, ktoré znamenajú, že cesta medzi baňami i a j trvá d hodín (kde 1 ≤ d ≤ 10 je celé číslo). Každú celú hodinu premáva autobus z každej bane do všetkých jej susedných baní.
Na ďalšom riadku vstupu je číslo T. Prospektori určili pre každú baňu prognózu na nasledujúcich T hodín – v bani i sa počas t-tej hodiny vyťaží ci,t zlata. Nasledujúcich T riadkov vstupného súboru obsahuje hodnoty c*,*, konkrétne t-ty riadok obsahuje na i-tom mieste hodnotu ci,t.
Kleofáš začína v bani číslo 1. Vašou úlohou je zistiť ako má Kleofáš cestovať po jednotlivých baniach, aby počas nasledujúcich T hodín vyťažil čo najviac zlata.
Príklad
Vstup
3 2 1 2 1 1 3 2 8 100 10 15 80 9 14 60 8 13 40 7 12 20 6 11 0 5 10 1 4 9 2 3 8
Výstup
Doluj v 1. bani 5 hodín.
Presuň sa do 3. bane.
Doluj v 3. bani 1 hodinu.
Dokopy získaš 308 kilogramov zlata.
3. O čokoláde
(15 bodov)
Raz doniesla Julka na stretnutie KSP čokoládu, Študentskú pečať. Pažraví vedúci ju chceli hneď a zaraz zjesť. (Čokoládu, nie Julku.) A kedže vedúcich bolo veľa, Julka chcela rozlámať čokoládu na jednotlivé kocky. Lenže čokoláda je tvrdá ako kameň. Navyše pozdĺž niektorých čiar sa zle láme, lebo ako vieme, Študentská pečať obsahuje oriešky, hrozienka a želatínu. Poraďte preto Julke, ako treba lámať čokoládu, aby sa najmenej natrápila.
Úloha
Sú dané rozmery čokolády M a N v jednotkových kockách. Ďalej sú dané kladné čísla x1, x2, ..., xM-1 a y1, y2, ..., yN-1, ktoré značia koľko námahy treba vynaložiť na prelomenie pozdĺž vertikálnej resp. horizontálnej čiary. Presnejšie xi značí, koľko námahy treba vynaložiť na prelomenie čokolády pozdĺž i-tej zvislej čiary. Pre vodorovné čiary je to podobne. Ak lámeme pozdĺž niektorej čiary viackrát (napr. ak sme predtým zlomili čokoládu pozdĺž kolmej čiary), tak toľkokrát prekonáme príslušnú námahu.
Napríklad ak polámeme čokoládu najprv podľa vodorovných čiar a potom podľa zvislých čiar, naša námaha bude y1 + y2 + ... + yN-1 + (N-1)(x1+x2+...+xM-1), pretože každý z vodorovných pásikov potrebujeme prelomiť (N-1)-krát. (Viď obrázok.) Vašou úlohou je napísať program, ktorý vyráta, akú najmenšiu námahu treba vynaložiť na rozlámanie čokolády.
Príklad
Vstup
6 4
x1=2, x2=1, x3=3, x4=1, x5=4
y1=4, y2=1, y3=2
Výstup
42
4. O plnej izbe
(15 bodov)
"Vyzerá to tu ako v sklade, Mal by si si to aspoň usporiadať", povedala mama Jankovi, keď uvidela jeho izbu. Janko totiž rád zbiera rôzne veci a vecičky a ukladá si ich v izbe. Výsledkom je, že u Janka v izbe to naozaj vyzerá ako v sklade. Teda aby som bol presnejší, podlahu Jankovej izby si môžeme predstaviť ako štvorcovú sieť s N riadkami a N stĺpcami. Na každom štvorci okrem jedného je krabica s rôznymi vecami. Aby Janko vedel, kde čo je, má každá krabica svoje číslo. Niekde vedľa potom existuje zoznam vecí, v ktorom je okrem iného napísané, čo je v ktorej krabici. Keďže Janko je malý a krabice sú veľké, Janko vie len presunúť nejakú krabicu na susedný prázdny štvorec (ak taký existuje). Štvorce považujeme za susedné ak majú spoločnú stranu. Janko by rád svojej mame urobil radosť a usporiadal tie krabice, ale zdá sa mu, že sa to nedá. Chce si však byť úplne istý.
Úloha
Pomôžte mu a napíšte program, ktorý zistí, či vie Janko krabice usporiadať tak, aby na i-tom riadku a j-tom stĺpci bola krabica s číslom N*(i-1)+j a štvorec na N-tom riadku a N-tom stĺpci bol prázdny.
Príklad
Vstup #1
N=2
2 1 3 .
Výstup #1
nedá sa
Vstup #2
N=3
4 1 3 2 . 8 7 6 5
Výstup #2
dá sa
Poznámka
Pre N=4 sa Jankovej úlohe hovorí Lloydova pätnástka.
5. O mravcoch IV
(15+ bodov)
Určite si ešte stále pamätáte, (V každej sérii vám to pripomíname...) že v prvej sérii dostali mravce na narodeniny kráľovnej počítače. Tieto počítače sú rovnaké a je ich veľmi veľa. Vašou úlohou bude napísať program, ktorý keď nahráme na všetky počítače a naraz ho na všetkých spustíme, niečo zmysluplné spočíta.
Ak si pamätáte, ako sa mravčie počítače programujú, môžete preskočiť priamo k zadaniu úlohy. Pre ostatných teraz bližšie popíšeme, ako vyzerá programovací jazyk, v ktorom sa programujú mravčie počítače.
Program budeme písať v jazyku podobnom jazyku Pascal. Premenné použité v programe budú lokálne, t.j. každý počítač bude mať vlastné premenné. Jedinou výnimkou je globálne pole celých čísel Mem[]. Toto pole je indexované od 0 a neobmedzene veľké. Na začiatku je v ňom (väčšinou v prvých niekoľko políčkach) uložený vstup úlohy, ostatné jeho políčka obsahujú nuly. Na konci v ňom má ostať uložený výsledok úlohy.
Programy budú spustené naraz na všetkých počítačoch. Počítače budú očíslované od 1 do K. Výpočet bude prebiehať v taktoch. Všetky počítače sú rovnako rýchle, v každom takte každý z nich vykoná práve 1 inštrukciu.
Môže sa stať, že niekoľko počítačov chce v tom istom takte čítať z, resp. zapisovať na to isté pamäťové miesto. V takomto prípade najskôr prebehne čítanie, potom zápis, Čítať jedno políčko globálnej pamäte môže naraz ľubovoľne veľa počítačov, ale zapisovať dovolíme len jednému. Ak by naraz chcelo na to isté miesto zapisovať viac počítačov, program vráti chybu. (T.j. tomuto sa pri písaní programu treba vyhnúť.)
Úloha
V globálnej pamäti (t.j. poli Mem[]) je uložený (Nejako vhodne, konkrétny spôsob si zvoľte aký sa vám hodí.) neorientovaný ohodnotený graf. Navrhnite mravčí program, ktorý čo najrýchlejšie nájde najlacnejšiu kostru tohto grafu.
Prvoradým kritériom hodnotenia bude čas výpočtu vášho programu, nasleduje použitá pamäť (súčet lokálnych pamätí spustených počítačov a počtu použitých políčok globálnej pamäte) a počet použitých počítačov.
Táto úloha je trochu náročnejšia, preto po vás nechceme konkrétny mravčí program, stačia nám myšlienky algoritmu, ktorý by ste použili. Samozrejme, čím podrobnejšie, tým lepšie. (Na plný počet bodov chceme popis, ktorý by sa v prípade potreby dal bez rozmýšľania prepísať na program.)
© KSP, 25. apríl 2004
