Príklady 1.kola zimnej časti 19.ročníka KSP-Z

Milé naše riešiteľky, milí naši riešitelia,

dostávajú sa vám do rúk zadania 19. ročníka KSP. Prečítajte si pozorne propozície súťaže a hor sa riešiť. Svoje riešenia nám posielajte najneskôr do 22. októbra. Nezabudnite k nim priložiť známky v hodnote 15,- Sk.

1. Zlatá retiazka
2. Z trpasličej chalúpky
3. Z tajného laboratória RSA
4. Zhrdzavené potrubie
5. Zluvyy n Arebqr pvgnwh onfra

V temných dobách stredoveku žil v Anglicku jeden rytier a ten sa volal Ivanhoe. Bol to veru smelý a rúči, no trochu skúpy mládenec. Ivanhoe mal milú a tá sa volala Anička. Bola že to rúča deva a ľúbila Ivanhoa veľmi. Aby sa on odvďačil svojej milej za toľkú lásku, rozhodol sa, že jej zadováži zlatú retiazku. Ako sa rozhodol, tak i urobil. Najbližší poklad strážil miestny drak. I vybral sa preto za drakom a bez váhania mu odťal všetkých dvanásť hláv. Poklad aj so zlatou retiazkou bol jeho.

Ako sa však ukázalo, zlatá retiazka bola zamotaná. Už to vlastne nebola ani reťaz, ale skôr kopa zlatých očiek náhodne poprepájaných medzi sebou. Ivanhoovi sa podarilo zistiť, že retiazka má dve koncové očká, ktoré pôvodne slúžili na to, aby sa dala zapnúť okolo krku. Ivanhoe je skúpy a rád by z reťaze odpílil čo najviac zlatých očiek. Na retiazke ale musia ostať koncové očká, a aby to bola ešte vôbec retiazka, musia ostať prepojené.

Úloha

Na vstupe je dané N - počet očiek. Očká sú očíslované číslami od 1 po N, pričom 1 a 2 sú čísla koncových očiek. Ďalej je dané M - počet prepojení očiek. Nasleduje zoznam dvojíc očiek, ktoré sú spojené medzi sebou. Napíšte program, ktorý vypíše čísla očiek, ktoré má Ivanhoe odpíliť tak, aby ich odpílil maximálny možný počet, a aby na retiazke ostali dve prepojené koncové očká. Ak je možností viacero, vypíšte ľubovoľnú z nich.

Príklad

Vstup
N=6, M=6

1 4      
4 2
2 3      
3 5
5 6      
1 5

Výstup
Treba vyhodiť očká 3, 5, 6.

V Microlande, krajine s najvyspelejšou miniaturizáciou, sa rozhodla skupina trpaslíkov postaviť si chalúpku. Ich najväčší problém však spočíva v tom, ako dopraviť stavebný materiál do potrebnej výšky. Microlandské miniaturizované žeriavy to nedokážu, preto si trpaslíci musia poradiť sami.

Trpaslíci sa preto rozhodli, že časť z nich sa postaví v pravidelných rozostupoch do radu od najväčšieho po najmenšieho. Potom si na hlavu položia latu, po ktorej ostatní trpaslíci vytlačia fúrik s tehlami. Len čo však tento nápad zrealizovali, nastala medzi nimi zvada. Jeden druhého začali obviňovať, že sa ulievajú, teda že nepridŕžajú hlavou latu. Aby mohli svoj spor spravodlivo rozhodnúť, budú potrebovať vašu pomoc.

Úloha

Napíšte program, ktorý načíta N - počet trpaslíkov v rade a N čísel - výšky trpaslíkov. Výšky trpaslíkov môžu byť na vstupe zadané v ľubovoľnom poradí. Úlohou programu je vypísať, či všetci trpaslíci budú pridŕžať hlavou latu, teda či sa hlavy trpaslíkov budú nachádzať na jednej priamke za predpokladu, že sa trpaslíci postavia v pravidelných rozostupoch usporiadaní podľa výšky.

Príklad

Vstup

5
12 6 4 8 10

Výstup
Áno

nbsp;

Vstup

4
6 4 3 1

Výstup
Nie

"Počuj Ron, a bude tá tvoja nová šifrovacia metóda dosť odolná voči hlupákom (krásny výraz blbuvzdorná sa asi nedá preložiť krajšie)? Vieš predsa veľmi dobre, že ľudia si vždy zvolia ten najslabší možný kľúč", spýtavo sa na Rivesta pozrel jeho dlhoročný známy Shamir. "Veruže bude! Žiadny kľúč - žiadni hlupáci. Len ešte musím doriešiť jeden malý detail", s úsmevom odvetil Rivest.

Aby ste rozumeli - Ron Rivest vynašiel novú šifrovaciu metódu, ktorá si kľúč vytvorí sama. Užívateľ zadá správu, ktorú šifrovací program premení na kladné celé číslo N. Teraz prichádza najdôležitejšia časť - vytvorenie kľúča K (taktiež celé kladné číslo). Toto je jediný detail, ktorý ešte Ron nedoriešil - ako vybrať najsilnejší (čiže najbezpečnejší) kľúč. Sila kľúča sa určí tak, že správu (čiže číslo N) prepíšeme do sústavy so základom K a zrátame, koľkými nulami tento zápis končí. Samozrejme, čím viac, tým lepšie. Napríklad pre správu N=72 má kľúč K=3 silu 2, lebo 72=(2200)₃. Zvyšok šifrovania je už prísne tajný, a preto sa o ňom už viac nemôžete dozvedieť. Napriek tomu však skúste pomôcť chudákovi Ronovi, ktorý je už z toľkého premýšľania úplne zronený.

Úloha

Pre dané N nájdite čo najsilnejší kľúč K. Ak je viac rôznych najsilnejších kľúčov, vypíšte ľubovoľný z nich.

Príklad

Vstup
N=198

Výstup
Najlepší kľúč je K=3. (198 je v trojkovej sústave 21100)

"Zase ďalšia diera!", v duchu si povedal Zápla, dvorný opravár Zimbabwejského kráľovstva. Za tých - 1, 2, 3,... no proste veľa - rokov svojej služby videl už mnoho hrdzavých potrubí. Zvyčajne bola diera len jedna, a preto nebol problém, čo s ňou - jednoducho ju Zápla zaplátal záplatou. Z ničoho nič ho dnes ráno zavolali k veľkej havárii na hlavnom vodovodnom potrubí, ktoré dopravuje vodu z jazera Kariba (16^o 53' S, 28^o 1' E) do hlavného mesta, Harare (17^o 50' S, 31^o 3' E). Z asi dvadsiatich miest potrubia striekala voda cez prehrdzavené steny hrubej rúry. Záplaty na také veľké potrubie sú drahé (záplaty sa dnes už nevyrábajú zo železa, ktoré ľahko a rýchlo hrdzavie, ale z prefíkanej umelej hmoty, ktorá určite prežije celé pôvodné potrubie), a preto si Zápla musí dobre rozmyslieť, ako ich na diery poukladať.

Úloha

Záplaty sú už z továrne narezané na metrové kúsky a nedajú sa už na mieste rezať na menšie. Zhrdzavený kúsok potrubia, teda diera, je zanedbateľne malá; ak položíme záplatu jej krajom na dieru, bude táto diera zaplátaná. Záplat môžeme dať aj viac na seba.(záplaty z prefíkanej umelej hmoty sú dostatočne tenké, takže to nebude ničomu vadiť) Zhrdzavené miesta (nech je ich N) sú určené ich polohou na potrubí, a keďže sú veľmi malé, budeme ich uvažovať len ako body na priamke a ich poloha bude udaná vzdialenosťou od začiatku potrubia (v metroch); môžete predpokladať, že pozície všetkých dier sú na vstupe utriedené podľa vzdialenosti od začiatku potrubia.

Zápla je už mierne nervózny, voda stále strieka a on vás žiada o radu, ako má záplaty na potrubie dávať, aby ich musel čo najmenej použiť.

Príklad

Vstup
N=3, diery sú na pozíciách 1, 3 a 3.5

Výstup
záplata od 0.5
záplata od 2.75

Nxb evrfravr fgnpv cbfyng bon anqcvfl onfav. N obq anilfr qbfgnargr, nx mvfgvgr, bqxvny wr gn onfra, pb pvgnwh.