KSP.sk

Korešpondenčný seminár z programovania

Priklady 3. kola

Mili nasi riesitelia,

dostavame sa do posledneho tohtorocneho kola. Co vam zapriat? Nuz hlavne vela dobrych napadov. Vase riesenia nam posielajte do 31. marca 1997.

Pomaly dalej zajdes
KSPaci

  1. Zavisova zahradka
  2. Zahranicne spravodajstvo
  3. Zoltan tipuje
  4. ZGMYTDJB CHLBNB
  5. Zahada sennej nadchy

1. Zavisova zahradka

Zavis zasa zacal zarabat. Zalozil znova zaujimavu zahradku. Zarobok zo zahradky - ziadna zabava. Zeby Zahradkarske zapolenie zaujimavych zahradiek (zname znackou ZZZZ)? Znamena ZZZZ, ze Zavis ziska zlato, zlato, zlato, zlato? Ziadaju zvycajne zabradlie zahradky (zostvorcovane). Zvitazit znamena, ze ziadna znama zahradka zo Zeme zasiala zahony zrovna zvitazenym zobrazenim. Zvitazi ziskuchtivy Zavis? Zohnal zoznam znamych zahradiek. Zeby zahradky zo zoznamu zobrazovali Zavisovu zahradku? Zacal zrovnavat...

Uloha: Napiste program, ktory nacita N (velkost zahradky) a dve matice typu NxN pozostavajuce z nul a jedniciek (0 znaci prazdne miesto, 1 zahon). Nato vypise, ci sa dane zahradky podobaju. Dve zahradky sa podobaju, ak mozno dostat jednu z druhej pomocou niekolkych operacii otacania o 90 stupnov a preklapanie podla osi x alebo y (osova sumernost).

Priklad:
Vstup:
N = 4
1 0 0 0 0 0 1 0
0 0 1 1 1 0 1 0
0 1 0 0 0 1 0 0
0 0 1 0 0 0 0 1
Vystup:
Ano, podobaju sa (druhu mozno dostat z prvej otocenim o 90 stupnov doprava a preklopenim podla osi x).

2. Zahranicne spravodajstvo

Z titulkov dnesnych sprav vyberame: Rozpor medzi Kiribati a Burundi, Celosvetovy strajk pokracuje, Na severozapade sa premnozili gorily.

A teraz k jednotlivym spravam podrobnejsie: Medzi Kiribati a Burundi sa strhla roztrzka po tom, ako Kiribatska princezna odmietla Burundijskeho nacelnika. Podla oficialnych zdrojov princezna nemala k tomuto rozhodnutiu ziaden dovod a nacelnik je vraj sumny mladenec. Napokon sa obe strany dohodli na tom, ze si princezna s nacelnikom zahraju particku tamojsej narodnej hry a kto vyhra, ten vyhra. Media sa po dlhsom mlcani rozhodli zverejnit aj dlho utajovane pravidla: Hraju dvaja hraci - princezna a nacelnik. Hraci roztrhnu nejake dva princeznine nahrdelniky a gulocky z nich polozia na hraci plan s erbami oboch krajin tak, aby sa nepomiesali. Potom striedavo z planu odoberaju urcity pocet gulocok, ktory nesmie byt nulovy. Pritom kazdy hrac moze na jeden tah odobrat gulocky iba jedneho druhu (bud z jedneho alebo z druheho nahrdelnika, nikdy vsak nie z oboch) a ich pocet nesmie prevysit vopred stanovenu konstantu k. Prehrava ten, kto bude mat po vyprazdneni hracieho planu bud neparny pocet gulocok (alternativa A) alebo ten, kto vezme poslednu gulocku z planu (alternativa B) alebo ten, kto nevezme poslednu gulocku z planu (alternativa C). Konkretna alternativa hry, ako aj konstanta k sa urcia na mieste losovanim.

Uloha: Napiste program, ktory urci hraca, pre ktoreho existuje vyhravajuca strategia v danej hre. Vas program by mal teda rozhodnut, ktory z hracov ma sancu vyhrat bez ohladu na to, ako bude hrat jeho super. Sucastou programu by mal byt aj poradca pre vyhravajuceho hraca, ktoremu by sme postupne zadavali tahy protihraca a poradca by radil, ako ma hrat vyhravajuci hrac. Vstupnymi hodnotami pre vas program budu cisla N1 a N2 udavajuce pocet gulocok na nahrdelnikoch, dalej cislo k a alternativa hry H. Princezna taha prva.

Poznamka: V alternative A mozete predpokladat, ze sucet N1 + N2 je neparny.

3. Zoltan tipuje

Zemepan Zoltan je velkym milovnikom koni. Pravidelne chodieva na dostihy. Velmi rad tipuje. S partiou podobne postihnutych priatelov sa kazdu nedelu poobede stretavaju v hladisku dostihovej drahy a diskutuju o konoch. Raz sa rozprudila ziva diskusia o tom, kto na co stavil. "Ja som stavil dvesto zlatych na to, ze Zlta Hviezda dobehne skor ako Potmehud," povedal grof Sternberg zo Sternbergu. "To nic nie je, mojich patsto zlatych a sud najlepsieho vina stoja proti prstenu pana z Ostrej Luky, ze Artefax predbehne Halifaxa," odvetil baron dePrasil. Sam Zoltan stavil dvadsatpat zlatych v striebre, ze jeho oblubenec Zeleznik porazi Drevenu Nohu.

Vysvitlo, ze vsetci Zoltanovi priatelia, vratane Zoltana sameho, uzatvorili stavky tipu "kon 1 dobehne skor ako kon 2". O chvilu bolo vsetko jasne. Kone dobehli, niektorych Zoltanovych priatelov sa zmocnila nevyslovna radost, ini statocne potlacali zial. Zoltan po strate dvadsatsedem zlatych (dva minul na kolu a hranolky) sa rozlucil s priatelmi a pobral sa domov. Doma sa ho zmocnil nepokoj: bolo by mozne, aby vsetci jeho priatelia v ten den vyhrali?

Uloha: Napiste program, ktory nacita pocet koni M, pocet stavok N a N stavok - dvojic cisel A(i), B(i), ktore predstavuju stavky "kon A(i) dobehne skor ako kon B(i)" a vypise jedno poradie koni take, ze vsetci Zoltanovi priatelia vyhraju, alebo vypise, ze take poradie nemozno najst.

Priklad:
Vstup:
M=7, N=4
Stavky:
1 2
2 3
3 4
3 1
Vystup:
Neda sa.

4. ZGMYTDJB CHLBNB

LYZBWKDB VGNDV CGAY JDAYC ZGCJBMB JYMYILBAGA ZGMYTDJU CHLBNU KYMGCNYJGNYQG NETVBAU. JBJG CHLBNB NCBW OGMB WNGMD MYHCDYAU UJBFYVDU HGCMBVB TBCDRLGNBVB. VGNDVBLD CB VDYWGMWG QGZDV CVBTDMD CHLBNU LGTMUCJDJ, BMY VYHGZBLDMG CB DA JG. HLYJG JYLBT CULVY HGJLYOUFU NBCU HGAGK. HGAGTJY DA B LGTCDRLUFJY (TB NEZBJVYF HGAGKD NBCQG HGKDJBKB) JYPJ CHLBNE. ZGMYTDJY FY HGCMBJ VDYMYV LGTCDRLGNBVE JYPJ, BMY BF HGCJUH, BWEA CJY QG LGTCDRLGNBMD B HLGILBA, WJGLE CJY CD WNGMD JGAU VBHDCBMD (BF C HGHDCGA). 

KHLQBZITJPOG LNPGSNFA
UBLVP ESMV OYFF BTCU OSJBGE WSBHC LNPGSNFQW XENFEEDPZ WC QB TQTYIFOLGJ
LYMOBGMELLGJ AZIPBPL PFPEMBAI FBEM X BEKGOGMPF N FTBMMNJV ZAIYEUJY XNBPSXZ
GELPZRKL CVG POPCTG NWAAIL BZITJXC VJRXQ LYMOBGMELR DOFAC UVIMUJN W
MVYXKWNGKPH HCAQSXFUS RSNPGTN E BBCVKDVRKMV EL MRTUJH YTPQY
MBYITBOSX W BWVBGRADU NWIBEOFEMELLGJ LEELJAEEI AE PJROVPECEI HDGNVEEI FE
WSBHC AICUJYE CA B TCUQIUJNX RFEGGOG GQ KR Z VZPLVP XVCKVRCDU ZGMXC WTCIEI
XSPFPRG ORQWTVE MBYITBOC FPIEBBG TTFGSBF VGJ QESFVXGKB HD UUNGK QBOTZG
TQAVEFBIOA POCXBGINPI XADUXQ LEELJA OVPEM MBYITBOC BCBDPVWY FVSEOF MI VBGS
ULIINB FTTBIE RPZSBF MEDFMTGDVX OJRV PB PINPZ WXFGI
VMNGQWN EIFAXWSN QCZOI

5. Zahada sennej nadchy

I takto Mohamed riekol: "Ked hodiny siestu hodinu odbiju, nech ste kdekolvek na Zemi, bez otalania klaknete si, tvarou k svatym miestam v Mekke pozerajuc, modlit sa budete."; I po kratke dramatickej pauze pokracoval: "A teraz chodte, poslovia moji, rozptylte sa po celom svete, kam vas vasa vola a nohy budu viest. Hapcii..." Po chvili, ked sa vysmrkal, dokoncil svoj prejav: "To som vam chcel povedat!" Nedalo mu, a este nakoniec tichym hlasom do vetra zasepkal: "Bodaj by mi aspon jeden z tych babrakov doniesol liek proti sennej nadche..."

A tak chodili po svete a robili, co im bolo prikazane. I stalo sa, ze o siestej hodine boli na tom istom namesti viaceri, a vznikol maly problem: vsetci si klakli, ale kedze nikto presne nevedel, ktorym smerom je Mekka, kazdy pozorne pozrel pred seba a ak videl nejakeho ineho klaciaceho mohamedana, otocil sa jeho smerom vo viere, ze on urcite vie lepsie, kam ma byt otoceny (ti na krajoch, pokial sa pozeraju z namestia von, alebo ti, ktori sa pozeraju na niekoho, kto sa pozera tym istym smerom, sa neotacaju a nerusene sa modlia). Mohamedani sa otacaju vzdy naraz kazdu sekundu (ako hodiny odbijaju).

Uloha: Dane je namestie MxN policok, pricom na kazdom policku moze byt jeden z tychto 4 objektov: 'S','J','V','Z' ('S' je mohamedan pozerajuci na sever,..., 'Z' je mohamedan pozerajuci na zapad).

  1. Napiste program, ktory simuluje stav na namesti kazdu sekundu pocnuc siestou hodinou. Ak sa uz vsetci mohamedani pokojne modlia, program skonci.
  2. Moze sa stat, ze niektori z mohamedanov sa nikdy neprestanu otacat? Ak ano, napiste program, ktory spocita pocet takychto mohamedanov. Ak nie, dokazte.
  3. Popiste usporiadanie mohamedanov na namesti po skonceni programu z casti 1.

Priklad:

  JZJ       ZJV       ZVV
  ZSV       ZVV       ZVV
  ZJV       ZJV       ZJV

6:00:00   6:00:01   6:00:02

(C) 1997, Organizers of the CSP

Podporte nás

Účet

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

Redirecting