KSP.sk

Korešpondenčný seminár z programovania

Priklady 1. kola, kategoria Z

Mili nasi riesitelia,

vitame Vas pri rieseni noveho rocnika KSP-Z. Dufame, ze aj tento rok sa Vam nase ulohy budu pacit a ze sa do sutaze zapojite v hojnom pocte. Riesenia prveho kola nam posielajte do 15. novembra 1999. Predtym, ako nam poslete svoje riesenia prveho kola, skuste si precitat propozicie. Nezabudnite nam spolu s rieseniami poslat vyplneny evidencny listok a znamky v celkovej hodnote 10.- Sk. Vela stastia pri rieseni praju a na stretnutie na sustredeni sa tesia.

KSPaci
  1. Z uctarne
  2. Zase SoDr
  3. Zo stavby
  4. Zbludilec v zrucanine
  5. Zimbabwejsky internet

1. Z uctarne

 Predstavte si stredne velku fabriku spolocnosti Vidlicky a Noze. Nevysoka budova v prijemnom prostredi, vsade vsak vladne culy ruch. Odlievaci, kovaci, brusici, lestici, ohybaci (neverili by ste, kolko to da roboty spravne vytvarovat zuby na vidlicke), zlatici, pracovnici na obchodnom oddeleni ( - Samozrejme, vazeny pane, ten noz je z cisteho zlata. Azda si o nas nemyslite, ze by sme vam boli schopni predat nejaku pozlatenu napodobeninu? - ), tetusky v baliarni, soferi odvazajuci vyrobky do obchodov - ti vsetci pracuju pre dobro firmy. A vsetkych tychto ludi ma na starosti sused Zavis.

Sused Zavis totiz pracuje ako uctovnik. Jeho starostou je, aby kazdy zo zamestnancov dostal kazdy mesiac spravne vypocitanu vyplatu. Vyplata sa zamestnancom pocita podla poctu odpracovanych dni. Mozete predpokladat, ze zamestnanci cez pracovne dni (t.j. pondelok az piatok) pracuju, v sobotu a nedelu odpocivaju. Uctovanie je narocna praca, preto by sused Zavis ocenil kazdu pomoc.

Uloha: Napiste program, ktory nacita mesiac a rok a vypise, kolko pracovnych dni bolo v danom mesiaci. Vas program by mal fungovat pre lubovolny rok, specialne by nemal robit problemy po roku 2000. Sviatky nemusite uvazovat.

Priklad: Vstup: 

SEP 1999
FEB 2000
Vystup: 
September 1999: 22 pracovnych dni
Februar 2000: 21 pracovnych dni

2. Zase SoDr

 V softferovom druzstve SoDr sa rozhodli naprogramovat novy editor. Editor je uz takmer hotovy a zostava dorobit iba niekolko funkcii. Teraz si vsetci lamu hlavu nad tym, ako spravit presuvanie bloku textu. Potrebovali by vasu pomoc.

Uloha: Editor ma globalne pole znakov A (velmi velke). V tomto poli je ulozeny editovany text. Uzivatel editora si v texte vyznacil blok, t.j. suvisly usek textu zacinajuci i-tym a konciaci j-tym znakom v poli A. Uzivatel chce tento blok presunut tak, aby po presune zacinal v k-tom prvku pola. Vasou ulohou je naprogramovat proceduru "presun(i,j,k)", ktora dostane cisla i, j a k a presunie v poli A blok textu od i-teho znaku po j-ty z povodneho miesta tak, aby zacinal na mieste k. Mozete predpokladat, ze i, j a k su zadane korektne, t.j. blok ma dlzku aspon 1 a zmesti sa do pola tak, aby zacinal od pozicie k.

Vasa procedura nesmie pouzivat dalsie polia okrem pola A a ani ine velke datove struktury (pouzit mozete iba konstantny pocet pomocnych premennych - znaky, cisla, logicke hodnoty a pod.). Sucasne sa snazte, aby vasa procedura pracovala co najrychlejsie.

Priklad:
Povodny obsah pola A: "abcdefgh"
presun(3,4,2)
Obsah pola A po presune: "acdbefgh"
presun(2,3,7)
Obsah pola A po druhom presune: "abefghcd"

3. Zo stavby

 Zavisovci prave dokoncili hrubu stavbu noveho domu na Ostrove pri Zmytej kvapke, chystaju sa dokoncit podlahy, kachlickovat, osadit okna, zaviest elektrinu a ostatne inzinierske siete. Sami to vsak nezvladnu, a tak chcu pozvat odbornikov - remeselnikov. Ti si ale uctuju za pracu velmi velke peniaze, a preto im treba naplanovat, kedy ma kto prist. Problemom je, ze jednotlive cinnosti musia vykonavat viaceri naraz, napriklad na podlahu v pracovni treba obkladaca a elektrikara, na kupelnu navyse vodara (ci vodnika?), na steny zase omietaca a elektrikara. Ked si to pani Zavisova dokladne rozpisala, zistila, ze uplne vsetky kombinacie roznych typov remeselnikov maju v dome uplatnenie. Zaroven si zaumienila, ze vsetkym cinnostiam v jej dome bude robit dozor, takze sa nemozu vykonavat dve naraz. Samozrejme, nikto nebude zahalat a len tak postavat - ti co su prave nepotrebni, musia odist. Kedze novy dom je na ostrove, chudak pan Zavis ich musi prevazat kompou. A v nej ma volne miesto iba pre jedneho.

Uloha: Pre dane N - pocet typov remeselnikov, ktorych oznacime 1,2,...,N, vypiste postupne vsetky podmnoziny mnoziny remeselnikov, a to v takom poradi, ze dve za sebou iduce podmnoziny sa lisia iba v jednom prvku - bud niekoho pan Zavis kompou privezie, alebo odvezie. Na zaciatku je pritom v dome prazdna mnozina remeselnikov.

Priklad:
Vstup:
N=3
Vystup: 

1.
2. 1
3. 1 2
4. 2
5. 2 3
6. 1 2 3
7. 1 3
8. 3

4. Zbludilec v zrucanine

 Dr. Jones je archeologom. K jeho zamestnaniu samozrejme patri aj skumanie zrucanin a starych podzemnych chodieb. A Jonesovi sa teraz prvykrat stalo, ze zabludil. Este ze mu kedysi priatel poradil fintu - pravidlo pravej ruky. Staci polozit pravu ruku na stenu a ist stale tak, aby sa ruka steny dotykala. Vysledkom ma vraj zarucene byt zodreta dlan a najdeny vychod. Tak teraz Jones stoji v chodbe uprostred zrucaniny a rozmysla, ktora ruka je prava.

Uloha: Napiste program, ktory na obrazovke simuluje prechod bludiskom podla pravidla pravej ruky. Vstupom su rozmery bludiska M a N ( M<80 , N<25 ), suradnice vchodu a vychodu a mapa bludiska. V mape '#' znamena stenu a '.' znamena prazdny priestor. Na celom obvode bludiska je stena, iba vchod a vychod su volne. Taktiez mozte predpokladat, ze vchod a vychod sa vzdy nachadzaju na obvode bludiska. Na zaciatku je Jones vo vchode do bludiska a chce sa dostat k vychodu.

Priklad:
Vstup:
N=8 ,M=8 Vchod: (1,4), vychod: (8,4)
Mapa: 

########
#...#.##
#.#....#
..####..
#...####
#.#....#
#.#.#..#
########

Dr. Jones podla pravidla pravej ruky pojde cez policka: (1,4), (2,4), (2,5), (2,6), (2,7), (2,6), (2,5), (3,5), (4,5), (4,6), (4,7), (4,6), (5,6), (6,6), (6,7), (7,7), (7,6), (6,6), (5,6), (4,6), (4,5), (3,5), (2,5), (2,4), (2,3), (2,2), (3,2), (4,2), (4,3), (5,3), (6,3), (7,3) (7,4), (8,4).

Vas program moze postupne cez tieto policka presuvat nejaky vhodny znak (napr. pismeno "J").

5. Zimbabwejsky internet

 Zimbabwejsky kral Zimba-Zimba sa rozhodol, ze jeho krajina velmi surne potrebuje internet. Zimba-Zimba, ako kazdy spravny Zimbabwejsky kral, velmi dlho rozmyslal, ako by toto svoje rozhodnutie mohol vykonat, az nakoniec si vybral firmu ZimNET, ktora ako jedina ponukala pripojenie na internet. Teraz uz Zimba-Zimba ma internet, ale nemoze sa pozerat na ziadne WWW stranky, pretoze firma ZimNET kralovi nenainstalovala ziaden prehliadac. Zimba-Zimba je teraz velmi smutny, lebo mu nikto nechce pomoct.

Pomozte Zimbo-Zimbovi a naprogramujte jednoduchy prehliadac WWW stranok. Ako vstup program nacita WWW stranku vo formate HTML a zobrazi ju na vystup (do suboru) v citatelnej forme. Samotny HTML subor vyzera podobne ako ten v priklade - na zaciatku je vzdy <HTML><BODY>, na konci </BODY></HTML>. Vsetky texty uzavrete v <\> oznacuju prikazy HTML, ktore ovplyvnuju, ako sa stranka zobrazi. Niektore taketo prikazy musia byt v dvojici, napriklad <HTML> a </HTML> - ten bez lomitka je vzdy zaciatok a s lomitkom je koniec bloku, na ktory ma dany prikaz vplyv. Takze napriklad <CENTER>Nadpis</CENTER> sposobi, ze text ``Nadpis'' bude tvorit samostatny odstavec, ktory bude zarovnany (vodorovne) na stred stranky. Druhy typ prikazov je neparovy a ide napriklad o prikaz <P>, ktory oznacuje koniec odstavca. Text ziadnych prikazov sa do vystupu nezapisuje. Samotny obsah stranky je tvoreny viacerymi odstavcami, pricom kazdy z nich moze zaberat aj viac riadkov vo vystupe. Vo vstupnom subore moze byt text jedneho odstavca umiestneny na viacerych riadkoch, moze obsahovat vela medzier, ale toto formatovanie vstupu nema vplyv na format vystupu. Kazda skupina medzier alebo prazdnych riadkov vo vstupe znamena len oddelenie jednotlivych slov. Tieto jednotlive slova sa potom zapisuju na vystup, pricom medzi kazdymi dvoma slovami je len jedna medzera. Vystupne zariadenie ma obmedzenu sirku (v nasom pripade 80 znakov), a preto slovo, ktore by tuto hranicu prekrocilo, sa zapise do nasledujuceho riadku. Medzi kazdymi dvoma odstavcami je vo vystupe jeden prazdny riadok (vo vstupe nemusi byt, napriklad ``koniec odstavca 1<P>Druhy odstavec'' je tiez oddelenie odstavcov).

Vasou ulohou je teda podla nacitanej WWW stranky v opisanom formate vytvorit subor, ktory bude obsahovat text stranky (nie prikazy) zarovnany na sirku 80 znakov. Predpokladajte, ze vstupny subor obsahuje len opisane prikazy, teda <HTML>, </HTML>, <BODY>, </BODY>, <CENTER>, </CENTER> a <P>.

Priklad:
Vstup: 

<HTML>
<BODY>
Zimbabwejsky internet - ukazkovy subor<P>
Toto je druhy     odstavec

textu, nezavisle od clenenia vo    vstupnom  subore.
<CENTER>
 Toto bude vycentrovany odstavec
</CENTER>
A nakoniec zase jeden obycajny odstavec
</BODY>
</HTML>

Vystup:
(pre sirku strany 40 znakov; ramcek nevypisujte - to je len zobrazenie hranic stranky) 

+----------------------------------------+
|Zimbabwejsky internet - ukazkovy subor  |
|                                        |
|Toto je druhy odstavec textu, nezavisle |
|od clenenia vo vstupnom subore.         |
|                                        |
|    Toto bude vycentrovany odstavec     |
|                                        |
|A nakoniec zase jeden obycajny odstavec |
+----------------------------------------+
1999, Organizatori KSP
Podporte nás

Účet

Prihlasovanie už nefunguje. Používaj nový KSP web.
 
loading

Redirecting