- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Priklady 4. kola
Mili nasi riesitelia,
blizi sa Velka noc. Takze dievcatam prajeme vela vody a chlapcom vela vajicok. No a ked si pri tom velkonocnom blazneni najdete trochu casu aj na KSPecko, tak nam svoje riesenia poslite a to do 28. aprila 1997.
Kto chce s vlkmi byt, musi s nimi vyt,
KSPaci
1. O prefikanom spionovi
Agent 00 Ferdo pracuje uz niekolko desatroci pre SIS (Slovensku informaticku spolocnost) na istej nemenovanej americkej univerzite. Cielom jeho misie je ziskat co najviac technickych planov najnovsich algoritmov. Za tie roky sa vypracoval na veducu poziciu institutu, takze vsetky prace studentov prechadzaju najskor prave jeho rukami. On sa ich pochopitelne snazi co najrychlejsie poslat kolegom do SIS, naco pouziva specialnu vysokofrekvencnu vysielacku.
Americka kontrarozviedka mu uz je na stope, hlavne vdaka tzv. CIA (Capture Incoming Alfawave) sposobu zachytavania prichadzajucej spravy. Zariadenia CIA maju rozmiestnene po celom kontinente, kazde vie urcit priblizny smer k vysielacu prichadzajucej spravy. Agentovi A000H sa podarilo ziskat zoznam vsetkych tychto zariadeni, spolu s vysledkami poslednych merani. Zoznam zacina cislom N (pocet zaznamov na zozname), pre kazde i=1...N obsahuje poziciu (x,y) i-teho pristroja CIA ako aj kruhovu vysec zaznamenavajucu smer pravdepodobneho vyskytu Ferdovho vysielaca - pre vysec su tam dve hodnoty: zaciatocny uhol smeru (v stupnoch, 0 je smerom na vychod, uhol stupa proti smeru hodinovych ruciciek) a kladny vnutorny uhol kruhovej vysece (najviac 90 stupnov).
Uloha: Napiste program, ktory zisti, ci americania vedia z danych hodnot usudit pribliznu Ferdovu polohu, t.j. ci existuje take miesto, pre ktore by boli vsetky informacie z pristrojov CIA spravne (a navzajom nevylucujuce sa). Tato informacia je velmi dolezita, aby mohol byt Ferdo vcas varovany, preto sa sustredte na rychlost vasho programu.
Poznamka 1. Americania este nezistili, ze Zem je gulata, preto pouzivaju rovinne mapy kontinentu.
Priklad:
Vstup:
N = 3
| x | y | zac. uhol | vnut. uhol |
| 1 | 2 | 315 | 90 |
| 2 | -0.4 | 90 | 45 |
| 2 | 3 | 180 | 90 |
Vystup:
Nemaju sancu zistit jeho polohu.
2. O Pakovaci
V tomto case na suostrovi Kiribati vrcholia velkolepe oslavy pri prilezitosti zavedenia telefonnej siete. Niektori triezvi domorodci vsak upozornuju na fakt, ze ostrovy nemaju dostatok dreva na vytlacenie telefonnych zoznamov. Bohati Kiribatcania sa totiz vyznacuju dlhymi menami. Vzhladom na skutocnost, ze su na svoje mena nesmierne hrdi a kvoli telefonu by si ich nenechali zmenit, rozhodla sa telefonna spolocnost mena v telefonnom zozname "pakovat" a to nasledovne: kazda n-krat sa opakujuca postupnost znakov PZ sa moze zapisat aj v tvare n[PZ]. Napr. ababab mozeme zapisat aj ako 3[ab]. PZ moze byt uz spakovana postupnost, takze konecny spakovany zapis moze obsahovat lubovolny pocet vnorenych zatvoriek.
Uloha: Napiste program, ktory na vstupe dostane postupnost znakov a...z a ktory pre tuto postupnost najde najkratsi mozny zapis (ak takychto zapisov existuje viac, staci jeden z nich). Najkratsi zapis je zapis skladajuci sa z najmensieho poctu znakov, teda vratane znakov [, ], a cislic.
Priklad:
Vstup:
baaaaaaaaaaaaababababc
Vystup:
b12[a]4[ab]c
(dlzka spakovaneho zapisu je 12 znakov)
Vstup:
aaaaaaaabcaaaaaaabc
Vystup:
a2[7[a]bc]
(dlzka spakovaneho zapisu je 10 znakov)
3. O klucikoch
V softferovom druzstve SoDr maju dalsieho zakaznika. Tentokrat sa na nich obratil nemenovany vyrobca klucikov. Kluciky sa vyrabaju z dopredu pripravenych vyliskov vybrusovanim. Pre kazdy typ vylisku je zname cislo N - sirka "aktivnej" casti klucika, a cislo K - maximalna povolena hlbka vybrusu.
Pri danom type vylisku mozno klucik reprezentovat ako postupnost celych cisel a[0],...,a[N], pricom a[i] znamena hlbku vybrusu vo vzdialenosti i od zaciatku "aktivnej" casti klucika. Medzi jednotlivymi celociselnymi poziciami je vybrus vedeny po usecke. Pre tuto postupnost dalej plati: a[0]=a[N]=K, |a[i]-a[i+1]|=1 (0<=i<N), 0<=a[i]<=K (0<=i<=N).
Vyrobca prave zahajil vyrobu noveho typu vyliskov a rad by vedel, kolkych zakaznikov moze uspokojit predajom zamkov a klucikov vyrobenych na baze tohto vylisku (kazdy zakaznik chce mat prirodzene iny kluc).
Uloha: Napiste program, ktory nacita typ vylisku (t.j. cisla N a K) a urci, kolko roznych klucikov mozno vybrusit z takehoto vylisku.
Priklad:
Vstup:
N=4, K=2
Vystup:
Mozno vyrobit 2 rozne kluciky.
4. O velkom suchu
Ludia su uz raz taki. Ak im niekto rozprava, co zle ich postihlo, povedia: "To nic nie je, keby si vedel, co sa stalo mne..." Santo a Banto nie su vynimky. Teraz su obaja velmi smutni. Prednedavnom sa rozhodli, ze nebudu len v krcme vysedavat a posadili si vo svojich zahradkach zeleninu. Ale teraz uz dva mesiace neprsalo a nakoniec im vsetko vyschlo. Zem uplne stvrdla a popraskala. Najprv sa zacali vytvarat len strbiny, tie sa vsak postupne predlzovali, popretinali, no a teraz su ich zahradky uz sama kryha. A tak Santo s Bantom sedia znovu v krcme a hadaju sa, cia zahrada je viac popraskana. Kedze ziaden nedokazal toho druheho presvedcit o svojej pravde, vybrali sa do svojich zahrad a zacali kryhy pocitat. Tak teraz smutne chodia a pocitaju a pocitaju. Pomozte im ich spocitat, lebo na oblohe sa zacali objavovat prve oblaciky a ak zacne prsat, svoj spor nikdy nevyriesia.
Uloha: Na vstupe je zadane N - pocet miest, v ktorych sa strbiny popretinali a dvojice priesecnikov, medzi ktorymi vedie strbina. Viete, ze strbiny sa v dalsich miestach uz nepretinaju. Spocitajte, na kolko kryh strbiny rozdelili zahradu. Za kryhu sa samozrejme pocita aj plocha od okrajovych strbin po plot (cim viac, tym viac).
Priklad:
5. O Stevovej sieti IV.
Konecne sa kamaratom podarilo ocislovat sa a su na to pravom hrdi. Ale skutocnost, ze maju vsetky pocitace zapojene do jednej rady, ich netesila. Ved koho by aj, ked si stale ten na jednom konci s tym na druhom konci posielaju spravy a vsetkych ostatnych to spomaluje... Nenasli oni ine riesenie tohto problemu ako sa porozpajat a nahodne potom pozapajat. I rozpajali oni a spajali sa a zrazu si tak uvedomili, ze im chyba Stevo. Ako mysleli, tak mysleli, no veruze nikto z nich si nemohol spomenut, kam ten Stevo zmizol. Hutali, hutali a vyhutali, ze on urcite spadol zo stromu a v tej kope machu ho nie je vidno. Alebo tam dolu nie je mach? No, na tom predsa nezalezi. Rozhodne ho nie je vidno, jeho laptop tiez nie a to zacina byt povazlive. Co ak osud uboheho Steva postretne aj niekoho z jeho kamaratov? Potom by ich bolo zase o jedneho menej, aj ked to nie je to najdolezitejsie. Ovela horsie by bolo, keby sa im potom siet rozpadla na viacero casti. A tu ich napadlo: Ved my musime zistit, ci je medzi nami niekto taky dolezity, ze mu nemozeme dovolit spadnut!
Uloha: Pocitace su nahodne pospajane. Kazdy pocitac ma svoje meno (cislo, rozne od ostatnych pocitacov) a linky na svojich susedov oznacene ich menami. Napr. ak pocitac s cislom 7 je spojeny s pocitacom c. 3, potom ich spolocnu linku ma pocitac c. 7 oznacenu cislom 3 a pocitac c. 3 ju ma oznacenu cislom 7. Dva pocitace su spojene nanajvys jednou linkou. Mozete predpokladat, ze jeden z pocitacov ma cislo 1.
Vasou ulohou je napisat program, ktory spustia Stevovi kamarati na svojich laptopoch a po jeho skonceni bude kazdy z nich vediet, ci su pospajani tak, ze po odpojeni hociktoreho pocitaca zostane siet suvisla.
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.
- MyName(var name:integer) - do premennej name ulozi meno pocitaca.
Poznamka: Najdolezitejsie je, aby vas program fungoval.
(C) 1997, Organizers of the CSP
