KSP.sk

Korešpondenčný seminár z programovania

Priklady 1. kola

Mili priatelia KSP,

pred sebou mate zadania prveho kola kategorie Z. Podmienky pre ucast v tejto kategorii ako aj ostatne potrebne informacie najdete v propoziciach seminara. Radime vam poriadne si ich precitat, usetrite sebe aj nam kopu starosti. Dufame, ze sa vam bude KSPecko pacit a ze sa pri nom naucite vela noveho.

Vase riesenia nam posielajte na horeuvedenu adresu (heslo KSP-Z) a to do 18. novembra 1996 (rozhoduje peciatka na obalke).

Drz sa novej cesty a stareho priatela

KSPaci
  1. Z univerzitnej kniznice
  2. Zorov zavet
  3. Zaletny zemepan
  4. Zatvorkove prvocisla
  5. Zelena zabka

1. Z univerzitnej kniznice

"Oook!" povedal knihovnik, ked zistil, ze sa stala chyba. Mrakoplas zase poplietol abecedu. V univerzitnej kniznici sa knihy triedia podla zaciatocneho pismena a tie ktore sa zacinaju na rovnake pismena sa triedia podla poctu stran. Mrakoplas si ako obycajne vymenil dve pismena z abecedy a teraz treba useky knih zacinajucich na tieto dve pismena vymenit spat tak, aby knihy v usekoch zostali spravne usporiadane. Je to vsak strasny problem, lebo v kniznici uz nie je ani jedna volna polica.

Uloha: Dane su cisla n,i,j,k,l, kde 1 <= i <= j < k <= l <= n a pole a[1..n] celych cisel. Pole si rozdelime na 5 usekov: a[1]...a[i-1], a[i]...a[j], a[j+1]...a[k-1], a[k]...a[l], a[l+1]...a[n] (niektore useky mozu mat aj nulovu dlzku). Preusporiadajte pole tak, ze druhy a stvrty usek budu navzajom vymenene, t.j. pole bude vyzerat takto: a[1]...a[i-1], a[k]...a[l], a[j+1]...a[k-1], a[i]...a[j], a[l+1]...a[n]. Okrem pola a mozete pouzit iba premenne typu integer (t.j. nepouzivajte ine polia, subory a podobne).

Priklad:
Vstup:
n=7, i=2, j=3, k=6, l=6
a=(1,2,3,4,5,6,7)
Vystup:
a=(1,6,4,5,2,3,7)

2. Zorov zavet

 "Aargh..." vysvetlil Zoro a zomrel. Zanedlho prisli dedici a zacali sa domahat vyplatenia zivotnej poistky. V poistovni im oznamili, ze podla zmluvy, kedze sa nejedna o vysoku ciastku, peniaze pozostalym vyplatia do sto dni. Dedici su velmi netrpezlivi a chceli by vediet, kolko dni uz od Zorovej smrti uplynulo.

Uloha: Napiste program, ktory nacita datum Zorovej smrti, dnesny datum a vypise, kolko dni uplynulo od jeho smrti. Uradnici v poistovni su vsak velmi lenivi a neporiadni, preto sa moze stat, ze niektore pripady budu vybavovat aj niekolko rokov. Rozdiel v zadanych datumoch moze byt aj vacsi ako sto dni. Mozete vsak predpokladat, ze obidva datumy su v rokoch 1901-1999.

3. Zaletny zemepan

Zemepan Zoltan je velky zaletnik. V okoli jeho zamku zije N krasnych zemepani. Kazda ma zamok so spustou veziciek a to sa zemepanovi Zoltanovi velmi paci. V poslednom case vsak na niektorych cestach striehnu ziarlivi zbojnici a Zoltan sa boji tadial prechadzat. Trapia ho pochybnosti, ci sa moze po bezpecnych cestach dostat ku kazdej z krasnych zemepani.

Uloha: Dane su cisla N a K, kde N je pocet krasnych zemepani a K je pocet bezpecnych ciest. Zamky su ocislovane cislami 1...N+1, zamok cislo N+1 je zemepanovo sidlo. Dalej je dany zoznam bezpecnych ciest. Kazda cesta vedie medzi dvoma zamkami a je zadana ich cislami. Napiste program, ktory zisti, ci sa zemepan moze dostat ku kazdej zemepanej, pricom moze cestovat aj cez viacere zamky.

Priklad:
Vstup:
N=3, K=2
cesty:
4 3
1 3

Vystup:
NIE (nemoze sa dostat k zemepani cislo 2)

4. Zatvorkove prvocisla

 Zatvorka je ucitelom matematiky. Celkom dobry ucitel. Ale co je vela, to je vela. Na poslednej hodine matematiky ho ziaci straasne nahnevali, dokonca na Ferovi, zvanom Zurivec, bol nuteny zlomit oblubene ukazovatko. Nuz im dal tazku, pretazku domacu ulohu. Ked sa vratil po narocnom dni domov, schladil sa jeho hnev a objavili sa pochybnosti. Co ak ho ziaci tromfnu a niekto najde lepsie riesenie ako on, ucitel Zatvorka?

Uloha: Pomozte ziakom dokazat Zatvorkovi, ze su pod slnkom aj lepsi matematici ako on. Najdite (za vydatnej pomoci vasho programu) co najdlhsiu aritmeticku postupnost prvocisel. Aritmeticka postupnost je postupnost cisel taka, ze rozdiel kazdych dvoch po sebe iducich cisel je rovnaky, dlzkou postupnosti rozumieme pocet jej clenov. Hodnotit budeme hlavne vami najdenu postupnost, ale aj postup, akym ste tuto postupnost nasli. Preto prilozte aj program a slovne popiste vas postup hladania.

Priklad:
Prikladom takejto postupnosti dlzky tri je 3, 7, 11.

5. Zelena zabka

Zrazu sa okolo zabky Julie zotmelo. Skutocne. Zly Moricko na nu hodil svoj klobuk. Na tom by zatial nebolo nic divne, ale to este neviete, ze Morickov klobuk ma podorys tvaru obdlznika s rozmermi M x N. Julia zacala skakat a volat o pomoc: "Kvaaaaak". Skakala tak zbesilo, ze si pri tom ani len nevsimla, ako naraza do klobuka a pod rovnakym uhlom odrazu ako bol uhol dopadu sa od jeho stien odraza. Popri tom s uzasom zistila, ze klobuk lezi na jahodovisku. Vzdy ked doskocila na jahodku, tak ju zjedla. Takze to napokon nebolo az take zle.

Uloha: Dane su P, N, M a pole a[1..N,1..M]. Na kazdom policku pola a bude udany pocet jahodok, ktore sa tam nachadzaju. Dalej su dane x a y, ktore urcuju poziciu zabky, a dx, dy urcujuce smer jej prveho skoku (ak Julia nenarazi do steny, tak po prvom skoku budu suradnice jej dopadu [x+dx,y+dy]). Napiste program, ktory odsimuluje P skokov zabky. Ak na pozicii dopadu rastu este nejake jahodky, Julia z nich jednu zje. Zobrazujte celu situaciu na obrazovke pomocou znakov po kazdom Juliinom skoku. Po skonceni simulacie vypiste pocet jahodok, ktore Julia zjedla.

Priklad:

Nech dx=-2, dy=-4. Potom zabka z pozicie [6,4] skoci na poziciu [4,1] (po odraze od steny) a po dalsom skoku bude na policku [2,5].

(C) 1996, Organizers of the CSP
Podporte nás

Účet

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

Redirecting