• KSP
• • Home
  • Novinky
  • Pravidlá
  • FAQ
  • Kuchárka
  • Liaheň
• Séria
• • Zadania a výsledky
  • Odovzdaj riešenie
  • Ideálne riešenie
  • Archív zadaní
  • Zbierka
• Akcie
• • Sústredenia
  • Proboje
  • Akadémia a klub
  • LTT
• Ostatné
• • Podporte nás
    2% z daní
  • Organizátori
  • Sponzori
  • Kontakt
• Iné semináre
• • Trojsten
  • KMS
  • FKS
  • Iné súťaže

Príklady 1. kola letnej časti 24. ročníka KSP

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

Vianočné prázdniny už sú za nami, starý rok sme prežili a nový rok (mimochodom, šťastný nový rok!) už prišiel. Keďže ste už odovzdali druhú sériu, tak sa určite neviete dočkať ďaľšej.

Pevne veríme, že sa pustíte do riešenia úloh, ktoré sme pre vás pripravili a že čo najviac z nich vyriešite. Nezabúdajte, že najlepších čaká pozvánka na nezabudnuteľné sústredko, a tých ešte lepších čakajú aj nejaké tie ceny. Hor sa do riešenia!

Termín odoslania riešení tejto série je pondelok 12. marca 2007. Riešitelia, ktorí sa za výsledky v minulom polroku dostali/dostanú pozvánku na jarné sústredko, majú jedinečnú možnosť odovzdať riešenia pri príchode na sústredko. A teraz ešte jedna kvízová otázka. Hádajte, kedy je sústredenie! :-)

Pes ktorý šteká, nebreše.
KSPáci

1. Zorro pomstiteľ
2. Zákerná kliatba slepého piráta
3. Zaplnený deň
4. Obludný regiment
5. O tajnostkárkach a tajnostkároch
6. O lakomom a štedrom Maroškovi
7. Obyčajný balík
8. Obyčajné triedenie?
9. Ťažký život
10. Tyče z Toga

---

1. Zorro pomstiteľ

15, kategória Z

Ako šiel čas, Zorro cestoval po Kalifornii a naprával krivdy páchané na obyvateľstve špa-niel-sky-mi vojakmi. Putoval však úplne náhodne, a tak sa mu často stávalo, že prišiel zachraňovať mesto, v ktorom ale nebolo koho zachraňovat. Španielski vojaci totiž v tom čase boli niekde inde. Preto sa rozhodol zmeniť stratégiu. Zameral sa na jediné mesto, a v ňom sa rozhodol zničit raz a navždy všetky posádky, ktoré doňho prídu. Netreba ale mrhať silami, najlepšie by bolo zničiť ich všetky naraz. Ale dá sa to vôbec?

A tak si sadol nad mesto a pozoroval. Zistil, koľko posádok chodí do mesta, a navyše zistil, že prichádzajú pravidelne. Pre každú posádku, ktorá do mesta chodí, existoval nejaký počet dní taký, že táto posádka bola v meste každý -ty deň – teda vždy jeden deň bola v meste a potom dní preč.

Úloha

Keď si to Zorro všetko spočítal, sklamane zistil, že ako naschvál to vychádza tak, že včera boli v meste úplne všetky posádky, ktoré doň chodia. Rozhodol sa teda, že pri najbližšej takejto príležitosti sa pustí do boja. O koľko dní to nastane?

Na vstupe je počet posádok a pre každú jedno kladné celé číslo, ktoré udáva, každých koľko dní je táto posádka v Zorrovom meste. Vypíšte, o koľko dní sa v meste zídu opäť všetky posádky.

---

2. Zákerná kliatba slepého piráta

15, kategória Z

Karibik sužujú piráti. Každodenné surové popravy kolaborujúcich spolupirátov. Pravidelné krvavé súboje. Posádky korábov sa prepichujú kordmi. Sabotáže plavidiel, konajúce sa pondelky, končia smrťou posádok. Karibský svetoznámy prístav každodenne stráca peniaze krádežami spôsobenými pirátmi. Krčma slabo prosperuje kvôli samozvaným pirátom – krčmári sa ponosujú, keď stopy po krvi svinia podlahu. Každodenné starosti prišelcov kulminujú. Stavy psychickej krízy snáď prekoná krása skvostného prímoria, ktorá sa približuje k samotnému povzneseniu karmy. Stvoriteľ podaroval Karibiku samé prekrásne kusy skvostov: Poletujúce kormorány sledujúce pozorne korisť. Skalnatá pláž krytá súvislou plochou krabov. Symetricky perfektné kryštáliky soli pokrývajúce každú skalu pobrežia. Kolosálne stojace palmy kryjú sivé prehnité kostry starých pirátov. Krajinná scenéria prekoná ktorúkoľvek svetskú predstavu. Kuknite sa pozornejšie k stojacemu plavidlu korzárov. Slávny pán kapitán stojí pri kormidle svojho plavidla. Každý starší pirát komanduje svojich pomocníkov. Kľud, salám, pohoda. Kánonom spievajú pesničku:

Korábom sa plavíme,

každodenne slávime,

pijeme koralku,

sundáme ponorku.

K súperom priplavíme,

kanóny si pripravíme.

Kapitán skvelý pán

Kričí "strely páľ!".

Konkurujú Superstar. Posádka kráti sústavné polihovanie kántrením skrytých potkanov. Krysy sa posmievajú. Kontrujú sústavným prehryzávaním klbiek stočených povrazov. Karmínovočervené slniečko pošteklilo kľudne spiaceho pozorovateľa, ktorý sa prebral. Korábom sa prehnal krik: "Seriózny problém!!! Kanóny sem, panika!". Ktovieskade sa priplížila kopa sebavedomých plachetníc kráľa Stanislava Piateho Krutého. "Smola prekliata. Krytí súmrakom priplávali keď sme pospali." Kedysi spavá posádka kupodivu svižne pobehuje. Kapitán straší posádku: "K strele pripraviť kanón. Sľubujem popravu keď sa pomýlite. Kým sa pripraví kanón, strieľajte puškami kreténi." Strelci popletene: "Kam strieľať?". "Predsa k súperovým plavidlám." "Koľko stupňov potrebujeme korigovať smer?" "Pätnásť."

Kormidelníka skolila paľba kanónov, strelný prach koluje skrz podpalubie. Krv, soľ, pot. Kapitán, schizofrenik paranoidný, konzultuje s partnerom, ktorého si predstavuje. Kujú strašné pikle, kreslia strategický papier. Kapitánovi skrsne plán kultovo stavaný: "Ponúkam krv Satanovi!! Preklínam kliatbou smrti prisluhovačov kráľa! Smrtonosi povstaňte!!!" Kliatba sklamala.
– "Potrebujeme karavely skoliť paľbou kanónov sami. Povedzte, koľko strelného prachu ku streľbe pozostávalo?"
– "Každý sud prázdny, kanóny sú prázdne, keď sa pozriem... kanón sedem plný!"
– "Kanón sedem pripraviť, korzári strieľajte presne!"
– "Kanón sme pripravili," kričí streľbukonajúci.
– "Páľ!"

Krátky seminár pre kanonierov statnej postavy: Kanóny strieľajú pomaly. Kde strelu poslať, keď sme pripravení? Kanón smerujeme po kolmici s priamkou križujúcou sťažne, prechádzajúcou kýlom. Súrne potrebujeme koráby

súperov prestreliť kovovou strelou približne kalibru sedem palcov.

Konečne! Strela preletela korábmi, sťažne popadali, kritický stav, potopa... Krása, sláva pirátom!

Úloha

Ako ste určite pochopili, naša pirátska loď má nasledujúci problém: zostal jej už len jediný výstrel, ktorým potrebuje potopiť všetky nepriateľské lode. Strieľať musia kolmo na smer svojej lode. Navyše prišli o kormidelníka, takže jediné, čo môžu pred výstrelom spraviť, je rýchlo sa preplaviť o vhodný kus dopredu. Jediné šťastie je, že všetky nepriateľské lode sú pred nimi a na správnej strane. Trafiť ľubovoľnú jednu z nich by nebol problém... ale vedia streliť cez všetky naraz?

Na vstupe je počet nepriateľských lodí a pre každú z nich dve kladné celé čísla , . Význam týchto čísel je nasledovný: Ak sa naša loď presunie dopredu o metrov a vystrelí, -tu loď trafí práve vtedy, keď . (Keď si predstavíme dráhu našej lode ako polpriamku, intervaly sú kolmé priemety ostatných lodí.)

Zistite všetky možné také, že keď sa naša loď posunie o metrov dopredu a vystrelí, trafí všetky ostatné lode. Predpokladajte, že nepriateľské lode sa počas presunu našej lode nepohnú.

---

3. Zaplnený deň

15 bodov, kategória Z

Blíži sa veľký deň D. Deň, dokedy treba zvládnuť vybaviť toľko vecí, až no ... ale neodbáčajme od témy. Skrátka, všetky inštitúcie sa rozhodli, že práve teraz je ten správny čas na prijímanie rôznych žiadostí, potvrdení, .... Ideálne by samozrejme bolo mať všetko z krku čím skôr. Aby ale veci neboli príliš jednoduché, rôzne úrady väčšinou otvárajú v rôznych časoch. Na druhej strane, úrady majú otvorené dostatočne dlho, takže určite všetko stihneme. A navyše sú veľmi blízko seba, takže dostať sa z jedného úradu k druhému zaberá takmer nulový čas.

Úloha

Na vstupe sú zadané čísla a . Všetky časy v zadaní budú udávané v bližšie neurčených jednotkách a budú to celé čísla od 0 do . môže byť ľubovoľne veľké, bude najviac .

Nasleduje dvojíc časov , , ktoré hovoria o vybavovaní na nejakom úrade: je čas od začiatku dňa, kedy úrad otvoria, je čas, ktorý tam strávime čakaním v rade a vybavovaním. (Môžete predpokladať, že nezávisí od toho, kedy na daný úrad prídeme.)

Chceme zistiť ideálny rozvrh návštev na úradoch – taký, pomocou ktorého stihneme všetky vybavovačky čo najskôr. Každý riadok rozvrhu pozostáva z poradového čísla úradu (v akom sa vyskytol na vstupe) a čas od začiatku prvého dňa, kedy tento úrad navštívime.

---

4. Obludný regiment

15, kategória Z a O

Kedysi dávno vo veľmi-veľmi vzdialenej galaxii bola jedna obrovská korytnačka, Veľká A'Tuin. S očami veľkosti morí, nohami veľkosti kontinentov sa plaví priestorom a na chrbte nesie štyroch slonov, ktorí nesú Zemeplochu. Niekde na nej sú dva malé štátiky, Bogoravia a Plesnivinsko.

A ako každý rok, Bogoravia sa chystá na vojnu.

V Bogoravii žije multidruhová spoločnosť, ktorú tvoria ľudia a trollovia. Najväčším problémom ich armády ale je, že Bogoravčania sú strašne ukecaní.

Preto sa pred bitkou musia vojaci v línii usporiadať rozumným spôsobom, aby sa medzi sebou nezakecali. Ideálne tak, aby sa jednotlivé druhy striedali. (Koľko si toho už len môžete povedať so štvormetrovým trollom, že?) Samozrejme to treba spraviť čo najrýchlejšie, a keďže vojaci sú neskúsení, musí ich komandovať ich seržant. Seržant by potreboval vedieť, koľko najmenej výmen musí spraviť, aby boli vojaci správne usporiadaní.

Úloha

V poli máte jednotiek a núl. Je potrebné toto pole preusporiadať tak, aby žiadne dve nuly ani žiadne dve jednotky neboli vedľa seba a aby bolo potrebné spraviť čo najmenej výmen. (Pri každej výmene môžeme vymeniť ľubovoľnú dvojicu prvkov poľa.) Výsledkom úlohy by malo byť jedno číslo, minimálny počet výmen.

---

5. O tajnostkárkach a tajnostkároch

15 bodov, kategória Z a O

Hoc je človek od pradávna tvor spoločenský (teda aspoň od chvíle, čo bola stvorená Eva) je rovnako aj mierne nedôverčivý (či aj tento fakt súvisí s Evou už veru neviem), ba priam tajnostkársky. Tajomstvá sú rôzne – každý máme nejaké tie "svoje", so súrodencami, s kamarátkami, s kamarátmi...

Dlho s tým neboli žiadne problémy, až kým sa nezjavil bulvár. Nik nevedel, odkiaľ sa tu vzal, a preto sa mocnosti tohto sveta rozhodli zriadiť tzv. SÚNOHI (Svetový Ústav Na Ochranu Háklivých Informácií. Pôvodne sa mal volať SÚNOHY, ale na Y nič nevymysleli.) , ktorý sa už roky zaoberá výskumom bulváru, jeho zdrojmi a šíriteľmi. Ľudia zo SÚNOHI sú naslovovzatými odborníkmi a ich originálne výskumy ukázali zopár zaujímavých faktov. Bezkonkurenčne najzaujímavejšie je, že každé pre bulvár naozaj zaujímavé tajomstvo je tajomstvom medzi dvoma osobami rôznych pohlaví.

Ako každý populárny úrad, aj SÚNOHI pravidelne uverejňujú svoje výročné správy. Takže netrvalo dlho a o výsledkoch týchto výskumov sa dozvedel aj agent Fax Murder. Ten je už dlho presvedčený, že sa medzi nami nachádzajú aj ufóni, ktorí sa správajú ako chameleóni – podľa toho, ako sa im zachce, vedia byť nerozoznateľní od chlapcov alebo od dievčat.

Výskum SÚNOHI dal Faxovi do rúk možnosť, ako prítomnosť ufónov dokázať. Z archívov SÚNOHI získal obrovskú kopu záznamov, v ktorých bola ku každej bulvárom uverejnenej pikoške uvedená dvojica osôb, ktorých tajomstvom pôvodne bola. Fax však bulvár nesleduje, a tak o žiadnej z osôb v záznamoch nevie jej pohlavie. Podarí sa mu napriek tomu dokázať prítomnosť ufónov?

Úloha

Na vstupe dostanete čísla a . je počet ľudí (tí sú v dátach označení číslami od 1 do ) a je počet zverejnených pikošiek.

Ďalej nasleduje dvojíc čísel, každá dvojica , sú čísla dvoch ľudí, ktorí kedysi mali spolu tajomstvo, ktoré bulvár odhalil a zverejnil ako pikošku. Takéto tajomstvá sú len medzi ľuďmi rôzneho pohlavia, alebo medzi človekom ľubovoľného pohlavia a ufónom.

Váš program by mal zistiť a vypísať, či medzi ľuďmi v dátach musia nutne byť nejakí ufóni.

---

6. O lakomom a štedrom Maroškovi

15 bodov, kategória O

Maroško (zdrobnenina od mena Maroš, nie Marek!) je veľmi kamarádsky človek. Taký kamarádsky, že si potyká takmer s každým objektom, ktorý mu príde do cesty. A tak sa stalo, že si za svojich skromných 20 rokov života našiel veľmi veľa priateľov a známych. Na tom by nebolo nič zlé. Horšie je, že každý z nich má niekedy narodeniny, niekedy meniny, niekedy Vianoce a niekedy sa mu narodí potomok. Na všetky tieto príležitosti sa vždy hodí nejaký ten darček – veď chodiť s prázdnymi rukami na oslavy je veľmi neslušné a zahanbujúce. Okrem toho náš Maroško aj veľmi rád číta. Má doma veľkú knižnicu s ešte väčším množstvom kníh.

V jednej z nich si prečítal starú múdrosť o tom, ako je kniha najlepší darček. A to mu vnuklo nápad, ako jeho problém riešiť – vždy keď bude treba niekoho obdarovať, tak jednoducho vezme jednu z kníh zo svojej knižnice a dotyčnému ju úprimne a s láskou venuje. Potom si ale uvedomil, že jeho knihy majú rôzne hodnoty a k ľuďom, ktorých obdarúva, má rôzny vzťah, preto knižky nemôže vyberať náhodne. A tak si povedal, že bude rozlišovať dva prípady: buď obdarúva niekoho, na kom mu veľmi záleží (frajerka) a vtedy chce vybrať tú najhodnotnejšiu a najvzácnejšiu knihu, alebo niekoho, na kom mu absolútne nezáleží (spolužiaci, kolegovia, kamaráti z huslí, čajovne a šachového klubu...) a vtedy chce venovať ten najmenej hodnotný kus literatúry. Keďže ale vôbec nevie algoritmicky programovať, musíte mu pomôcť napísať program, ktorý bude zaznamenávať stav jeho knižnice a bude to robiť rýchlo.

Úloha

Napíšte program, ktorý bude simulovať Maroškovu knižnicu. Pre jednoduchosť budeme v našom programe pracovať len s hodnotami kníh – to budú prirodzené čisla. Vstup pozostáva z niekoľkých riadkov, každý popisuje jednu operáciu. Tie môžu byť nasledovné:

• Maroško si kúpil knihu nejakej hodnoty – na začiatku riadku je číslo 1 a za ním hodnota kúpenej knihy .
• Maroško chce obdarovať niekoho najdrahšou knihou, ktorú má v knižnici – riadok pozostáva z jediného čísla 2.
• Maroško chce niekoho obdarovať najlacnejšou knihou vo svojej knižnici – riadok pozostáva z jediného čísla 3.
• Maroško sa na to vykašlal a už nebude chodiť na žiadne oslavy. Inak povedané program končí. Riadok obsahuje jediné číslo 0.

Vždy pri darovaní knihy vypíšte jej hodnotu na výstup. Na začiatku je knižnica prázdna. Ak Maroško nemá čo darovať, tak o tom tiež podajte správu.

Ešte jedno dôležité upozornenie – v tejto úlohe sa zakazuje používať knižnice ako STL (C++) alebo generické implementované dátové štruktúry (Java). Ak ste napríklad zvyknutí používať vector a nezaobídete sa bez toho, tak to vám ešte prepáčime, podobne aj nejaké iné elementárne veci. Po prstoch dostane ale ten, kto sa opováži použiť niečo zložitejšie, čo mu principiálne uľahčí robotu. To platí všeobecne pre všetky jazyky.

---

7. Obyčajný balík

15 bodov, kategória O

Na nemenované veľvyslanectvo včera prišiel obyčajný nenápadný balík. V tomto nenápadnom balíku boli samozrejme dôležité pokyny na špionáž, kontrašpionáž, kontra-kontrašpionáž, hranie spider solitéru a všakovaké iné aktivity, aké sa už len v cudzine dajú praktizovať.

Ale nastal problém. Balík vyzeral obyčajnejšie a nenápadnejšie ako ten, čo dostali z domoviny minulý mesiac. To bolo samozrejme vrcholne podozrivé. Čo ak ho dostali do rúk teroristi, pridali doň falošné pokyny a zamaskovali to? Alebo čo ak nám odjedli z gumených macíkov, čo majú byť na spodku?

Veľvyslanec mal ešte v živej pamäti ako minulý rok celý mesiac všetci zbytočne skákali na jednej nohe, a tak sa rozhodol nenechať nič na náhodu. Vytiahol spod vankúša Dôležitý Červený Telefón a zavolal Tomu Najvyššiemu. "Koľko vážil balík, ktorý ste nám poslali?" opýtal sa. "Presne kíl!" znela stručná odpoveď a obe strany súčasne položili telefón (skôr, ako by niekto mohol vystopovať, kam hovor išiel).

V priestoroch veľvyslanectva sa podarilo nájsť jedny dvojramenné váhy a niekoľko (z domoviny dovezených certifikovaných) závaží. Hm, ale vie sa pomocou nich veľvyslanec presvedčiť, či balík váži presne kíl?

Úloha

Na vstupe je očakávaná váha balíka a váhy jednotlivých závaží. Napíšte program, ktorý zistí, či sa na dvojramenných váhach vieme presvedčiť, že hmotnosť balíka je správna.

---

8. Obyčajné triedenie?

15+ bodov, kategória O a T

Starý sklerotický pán učiteľ vošiel do triedy a s úsmevom oznámil:

"Ták, deti, dočkali ste sa. Dnes sa konečne budeme učiť triedenia!"

Keď sa táto situácia vyskytla prvých 23-krát, boli deti na hodine čoraz zúfalejšie a unudenejšie. Márne sa snažili učiteľovi vysvetliť, že triedenia s nimi skúša brať zas a znova, ten si nič také nepamätal. No tentokrát nie, tentokrát sa na neho pripravili.

"No schválne, deti, viete niekto, ako by ste utriedili čísel?" opýtal sa triedy učiteľ rečnícku otázku. No tentokrát sa na jeho prekvapenie zdvihlo zopár rúk.

"Prosím," povedala Anička, "ja by som sa vždy len pozrela na nejaké náhodné dve čísla a keď je to viac vľavo väčšie, tak ich vymenila. A po každých

krokoch sa pozriem, či už je všetko utriedené."

"To ja," hovoril Branko, "ja by som to spravil ináč! Využijem rekurziu. Ak mám jednoprvkové pole, to už je utriedené. Ak mám dvojprvkové, to utriedim ľahko. A ak mám dlhšie, tak najskôr utriedim (rekurzívne, teda opakovaním tohoto postupu) prvé dve tretiny poľa, potom druhé dve tretiny, a potom

zase prvé dve tretiny. (A potichu dodal: Ak by dĺžka triedeného

úseku nevyšla celé číslo, zaokrúhlim ju nahor.) "

"Ale nie!" ozval sa aj Cim (Mic hádam prepáči, že sme ho museli otočiť, aby jeho meno začínalo na C :-)) .

"Ja by som to spravil takto. Budem vymieňať len dvojice po sebe idúcich prvkov. Takýchto dvojíc je . Zoberiem si papierikov, na každý napíšem jednu dvojicu. V každom kole tieto papieriky náhodne zamiešam, a potom sa na ne postupne pozerám. Vždy si z papierika prečítam, ktorú dvojicu prvkov mám skontrolovať, pozriem sa na ňu a ak je prvé číslo väčšie, tak ich vymením. Na konci kola, keď sa mi minú papieriky, vždy skontrolujem, či už som všetko utriedil."

Úloha

a) Naprogramujte vyššie popísané triediace algoritmy , a .

b) Praktickým testovaním čo najpresnejšie odhadnite časovú zložitosť každého z týchto algoritmov. (Trebárs namerajte hodnoty pre rôzne , rôzne vstupy s daným , nakreslite si graf a uvidíte.)

c) Nájdite čo najlepší dolný odhad časovej zložitosti týchto algoritmov v najhoršom prípade. (Teda vymyslite, ako v závislosti on vyzerá čo najhorší možný vstup, a čo najpresnejšie spočítajte, ako dlho na ňom algoritmus pobeží.)

d) ( za body navyše) Nájdite a dokážte čo najlepší horný odhad časovej zložitosti týchto algoritmov v najhoršom prípade.

---

9. Ťažký život

15 bodov, kategória T

Marek je taký obyčajný človek. Raz sa cíti horšie a raz lepšie. Keďže ho baví psychológia, rozhodol sa, že bude analyzovať horšie obdobia a lepšie obdobia. Začal si dokonca písať denník a každý deň nakoniec ohodnotil kladným číslom. Čím väčšie číslo, tým lepší deň.

Prišiel na to, ako pre každé obdobie roka vie číselne vyjadriť, ako dobre mu

vtedy bolo. Sčíta číselné hodnoty dní v danom období a tento súčet vynásobí minimálnou číselnou hodnotou dňa v danom období. Totiž jedna jediná zlá udalosť dokáže pokaziť dojem z celého obdobia. Marek by teraz chcel nájsť najlepšie obdobie, odkedy si píše denník.

Úloha

Na vstupe je číslo – počet dní, koľko si už Marek píše denník. Ďalej je daných kladných čísel , ktoré vyjadrujú ohodnotenie jednotlivých dní. Ohodnotenie nejakého obdobia zistíme tak, že sčítame všetky hodnoty v období a tento súčet vynásobime najmenšou hodnotou v období. Vašou úlohou je zistiť najväčšie ohodnotenie nejakého obdobia.

---

10. Tyče z Toga

15 bodov, kategória T

Vedci z IBM (Institute of Black Magic) čakajú na tri zásielky tyčí z Toga aby mohli ďaľej vyvíjať nový počítač PC 47 Lamálky (áno, víl Lamálok je strašne vela, zatiaľ čo Amálka je len jedna...) Inside. Každá zásielka mala obsahovať jeden typ tyčí: prvá svetlotyrkisové, druhá strednetyrkisové a tretia tmavotyrkisové.

"Nieeeee!!!", zakričal hlavný inžinier. Pobočke v Togu sa totiž nechcelo platiť trikrát poštovné, a tak poslali všetky tyče naraz. To je ale hrozný problém – vedci z IBM totiž nemajú šajnu o tom,

aký je rozdiel medzi rôznymi odtieňmi tyrkisovej, a nevedia tyče od seba vôbec odlíšiť. Pamätajú si len, že svetlotyrkysových malo byť viac ako ostatných dvoch odtieňov dokopy.

Po dlhom rozmýšľaní napadlo hlavného (teraz už skôr hladného) inžiniera spásonosné riešenie: "Použime víly Lamálky. Ale ako dlho im to bude trvať?"

Víly Lamálky sú ale strašné, ale fakt strašné lamy, a rozpoznávanie farieb im tiež príliš nejde. Jediné, čo vie taká Lamálka povedať, je, že či sú dve tyče rovnakej farby alebo nie. A aj na to musí byť sama a nerušená celý mesiac zavretá v prázdnej miestnosti s dotyčnými dvoma tyčami.

Vedci z IBM si teraz nie sú istí, či im víly Lamálky dokážu vôbec nejako pomôcť. Keby tak aspoň o jednej tyči s istotou vedeli, akej je farby, to už by si nejako poradili...

Úloha

Na vstupe dostanete číslo , čo je počet tyčí. Tyče sú označené nálepkami s číslami od 1 do . Tyče sú troch rôznych odtieňov tyrkisovej a viete, že svetlotyrkisových je nadpolovičná väčšina. Každý mesiac môžete každú tyč dať porovnať s jednou inou tyčou. (Výstup porovnania je buď "sú rovnakej farby", alebo "nie sú rovnakej farby", nič viac sa od víly Lamálky nedozviete.)

Treba aspoň o jednej tyči zistiť, akej je farby. Napíšte program, ktorý bude hovoriť, ako porovnávať tyče tak, aby mu to v najhoršom možnom prípade (v závislosti od počtov tyčí jednotlivých farieb a ich usporiadania) trvalo čo najkratšie. Teda váš program vypíše, ktoré dvojice tyčí porovnať, počká si na výsledok, vypíše nové dvojice tyčí... a tak dokola, až kým si nie je istý farbou niektorej tyče.

Nezabudnite uviesť a dokázať, koľko mesiacov (v závislosti od ) to bude vášmu programu v najhoršom prípade trvať.

---