Prikady 3. kola 17. rocnika KSP

Mili nasi riesitelia,

aby ste si nemysleli, ze sme na vas zabudli, sme tu opat, tentoraz so zadaniami tretieho kola. Chceme vam v nich popriat vela dobrych znamok na vysvedceni, squelu lyzovacku no a samozrejme kopu casu hodnotne straveneho nad nasimi zadaniami. A aby sme trochu podporili vase snazenie, vyhlasujeme, ze prvych niekolko riesitelov ze niekolko najlepsich riesitelov sa moze tesit na zaujimave ceny (Vinko napriklad slubil kupit v Kanade knizku Cormen, Leiserson, Rivest: Introduction to Algorithms, ktora je na prvu cenu ako stvorena). No a samozrejme, vase riesenia ocakavame do 6. marca 2000.

KSPaci

O velkom smade
O automate na listky
O velkom neporiadku
O dlhych tyciach
O Santovi a flasiach II

1. O velkom smade

"Stavme sa, ze vypijem 10 kofol, ak mi ich niekto kupi," navrhne Miso. "Dobre, ale ak prehras, tak ty mne kupis 15 kofol! Nech sa mi vratia aj s urokmi," suhlasi Brano. "Plati?" "Plati." A tak sa poberu k vycapu. Prva, druha, tretia kofola... to je este v pohode. Stvrta, piata, siesta... zacina byt problem. Siedma, osma... Miso je uz zeleno- modry a vzdava sa. "Prehral si! Teda mi uz visis 43 kofol."

A takto to v KSPackych kruhoch chodi uz dlhe tyzdne. Kazdy je niekomu dlzny mnozstvo kofol. Pomaly ale iste sa v zlozitych dlzobnych vztahoch uz prestavaju vsetci vyznat. Preto sa rozhodli, ze sa dnes vyrovnaju. Lenze, ked vypiju takych 50 kofol v takejto zime, to im hrozi podchladenie, ba az smrt. A co by bolo potom? Vtom skrsla Davidovi v hlave skvostna idea (aj to sa niekedy stava) (tzv. bezkofolove vyrovnanie):

Nech dlhuje KSPak A KSPakovi B K₁ kofol a B dlhuje C K₂ kofol. Potom mozu svoje dlhy upravit tak, aby B vypil o X=min(K₁,K₂) kofol menej. Potom A bude dlzit B iba K₁-X a B bude dlzit C K₂-X kofol. Zaroven vsak bude KSPak A dlzit KSPakovi C o X kofol viac. Ak sa takto stane, ze niekto dlzi nieco sam sebe (A=C), tak si nebude samozrejme nic kupovat.

Uloha

Na prvom riadku vstupu su dve cele cisla N - pocet KSPakov a M - pocet dlzob. Potom nasleduje M riadkov. Na kazdom su tri cele kladne cisla A, B, K, co znamena: KSPak A je dlzny KSPakovi B prave K. kofol. Vasou ulohou napisat program, ktory zisti, kolko minimalne kofol musia dokopy vypit a vypise jeden mozny zaverecny stav, kto komu kolko kofol dlzi.

Priklad

Vstup:

Vystup:

Pocet vypitych kofol: 5
1 3 1
2 3 4

2. O automate na listky

Dano studuje uz dlhe roky programovanie na univerzite kdesi v Amerike. Nedavno prisiel na navstevu Bratislavy. Ake bolo jeho prekvapenie, ked zistil, ze v Bratislave uz davno neplatia stare listky na autobus (ktorych mal pre kazdy pripad niekolko v zalohe). Nove listky sa daju kupit napriklad v automate na zastavke. Automat vydava n druhov listkov s cenami c₁, c₂,...,c_n (cele cisla). Listky sa kupuju tak, ze listkovchtiva osoba postupne stlaca tlacidla zodpovedajuce listkom, ktore chce kupit (ak chce viac listkov rovnakeho druhu, stlaci prislusne tlacidlo viackrat) a na displeji automatu sa priebezne objavuje ich celkova cena (na zaciatku displej ukazuje 0 korun). Potom dotycny vhodi do automatu prislusnu sumu minci a z automatu vypadnu ziadane listky. Dano potreboval vela roznych listkov (planuje sa nejaky cas zdrzat, navstivit rodicov, priatelov, jednu nemenovanu slecnu, matematicko-fyzikalnu fakultu a zubara) a tak zacal odusu stlacat tlacidla na automate. Ako tak stlacal, zistil, ze automat nie je ochotny akceptovat viac ako p stlaceni tlacidiel a nie je ochotny akceptovat dalsie stlacenie, ak je na displeji suma prevysujuca s korun. Dano sa ako spravny programator rozhodol, ze zisti, aku najvacsiu sumu je mozne na displeji automatu stlacanim tlacidiel dosiahnut. Potom si vsak uvedomil, ze ak chce stihnut vsetky navstevy, musi sa poponahlat a nechal tuto ulohu na vas.

Uloha

Napiste program, ktory nacita pocet listkov, ich ceny, maximalny pocet stlaceni a sumu s a vypise, aku najvacsiu sumu je na displeji mozne dosiahnut.

Priklad

Vstup:
n = 3
ceny: 6, 17, 35
p = 10, s = 100

Vystup:
134

(Treba stlacit tlacidla pre dva listky za 35, jeden za 17, dva za 6 a nakoniec este jeden za 35 korun.)

3. O velkom neporiadku

"Ked mi uz tak velmi chces pomahat, tak roztried tamtie skrutky!", povedal otec ukazujuc na velku kopu skrutiek a matic v rohu garaze. Tomas bol cely nestastny. Rad otcovi vo vsetkom pomahal. Nemohol za to, ze vsetko, coho sa dotkol, sa hned lamalo a kazilo. Otec sa vacsinou nezlostil, aj ked casto musel robit vsetko odznova. Tentoraz to ale vyzeralo vazne. Vyraz v otcovej tvari hovoril jednoznacne: "Uz ziadne kazenie, prekazanie a praca navyse. Teraz ta zamestnam pracou, pri ktorej nic nepokazis." Tomas teda smutne pozrel na kopu v rohu a pustil sa do prace. "Presne ako Popoluska," pomyslel si. "Popoluske prisli pomoct holuby. Lenze mne nikto nepomoze. Ibaze by..."

Uloha

Mame N skrutiek a N matic roznych velkosti, z ktorych ku kazdej skrutke prislucha prave jedna matica a naopak. Napiste program, ktory pomoze Tomasovi usporiadat skrutky a matice. Program nacita pocet skrutiek a matic N a potom moze klast Tomasovi otazky typu "i-ta skrutka a j-ta matica?". Tomas odpovie bud "OK" ak skrutka a matica patria k sebe, "VACSIA MATICA" ak j-ta matica je vacsia ako i-ta skrutka a "VACSIA SKRUTKA" ak je skrutka vacsia ako matica.

Ulohou vasho programu je najst ku kazdej skrutke nast jej zodpovedajucu maticu. Tomas chce mat tuto robotu rychlo hotovu, preto by ocenil, keby sa ho program pytal co najmenej otazok, avsak dolezitejsie je, aby mu program vyhodil spravny vysledok.

Priklad

Vstup
N = 3

1. skrutka a 2. matica?  OK
2. skrutka a 1. matica?  VACSIA MATICA

Vystup
Spravne pary su: (1,2) , (2,3) , (3,1)

4. O dlhych tyciach

Stal Babylon, najslavnejsia to risa. I jedneho dna povedali si Babyloncania: "Nam uz zit na zemi neprinalezi. Az po same nebo vezu postavime, a potom tam zit budeme!". Nedbali oni varovania vestca, ze kto sa Bohu rovnat chce, kruto potrestany bude. Kazdy z Babyloncanov sa domov pobral, i vsetky tyce, co doma nasiel, na namestie doniesol. Ked uz vsetky tyce pokope boli, zacali z nich konstrukciu veze stavat. Lenze co to? Tyce boli tak roznych dlzok, ze nik, ani ten najmudrejsi z nich (Cpt. John Sheridan), schopny nebol najst tri take, co by strany trojuholnika tvorili. A tak hladali, hladali, no stale nenachadzali a stavbu zacat nemohli.

A tak by sa im zisiel program, ktory by tento problem riesil za nich. (A tiez by sa im zisiel pocitac...)

Uloha

Napiste program, ktory dostane na vstupe cislo N a nasledne N dlzok tyci d₁... d_n, co su realne cisla, pre ktore plati 1<= d_i<= 1000000000. Program ma vypisat, ci je medzi nimi taka trojica, z ktorej sa da zlozit trojuholnik.

Poznamka: Dobre sa zamyslite nad casovou a pamatovou zlozitostou vasho programu...

Priklad

Vstup:
N=3
1.0 1.1 2.1
Vystup:
NIE

Vstup:
N=5
1.7 4.9 51.0 174.9 4.957
Vystup:
ANO

5. O Santovi a flasiach II

Zlatokopi z Vysnej Klondiky uz po sedem rokov radi chodievaju do hostinca v Dolnom Kelcove posilnovat sa ohnivou vodou, hrat hazardne hry a uzatvarat stavky. Aj Santo a Banto tam pravidelne radi chodia. Tentokrat sa im opat podarilo vyhrat stavku s krcmarom a za odmenu im krcmar postavil na stol do kruhu mnoho flias ohnivej vody rozneho objemu a povedal: "Z tychto flias pite kolko vam hrdlo raci, ale dodrzujte kulturu pitia!"

Santo sa uz-uz chcel rozbehnut ku flasiam, ale Banto ho zadrzal. "Nezabudaj na tie prihluple krcmarove pravidla, nemozeme pit hocijako, nevypite flase musia v kazdom okamihu tvorit suvisly usek. Musime si davat pozor, inac nas opat vyhodi! A budeme sa pekne striedat. Jednu flasu ty, jednu ja, az kym sa nam vsetky neminu."

Uloha

Na zaciatku je na stole 2n flias s objemami 1 az 2n decilitrov (kazdy objem sa vyskytuje prave raz) rozostavenych do kruhu. Hrac, ktory je prvy na tahu, moze vypit lubovolnu flasu. V kazdom dalsom tahu moze prislusny hrac vypit lubovolnu flasu susediacu s nejakou uz vypitou flasou (aby sa zachovala suvislost useku nevypitych flias). Cielom hry je samozrejme preliat hrdlom viac ohnivej vody ako ten druhy.

a) Je dane n a 2n roznych celych cisel od 1 po 2n reprezentujucich objemy flias po rade v kruhu. Napiste program, ktory bude radit Santovi (ktory je prvy na tahu), ktoru flasu ma kedy vypit tak aby dokopy vypil viac ohnivej vody ako Banto. Vas program by mal v kazdom tahu vypisat, ktoru flasu ma Santo vypit a nacitat, ktoru flasu vypil Banto. Mozete predpokladat, ze Banto hra podla pravidiel.

b) Napiste program, ktory nacita lubovolnu legalnu poziciu (t.j. taku, ktora mohla vzniknut postupnostou legalnych tahov), a bude striedavo radit hracovi na tahu ktoru flasu ma vypit a nacitavat tahy supera. Na konci by mal program vypisat, kto kolko vypil a kto vypil viac.

Priklad priebehu hry:

N=3
flase: 2 6 3 1 5 4

Santo, vypi 6dl flasu.        Banto vypil: 3dl
Santo, vypi 2dl flasu.        Banto vypil: 4dl
Santo, vypi 5dl flasu.        Banto vypil: 1dl

Dokopy Santo vypil 13dl ohnivej vody, ale Banto len 8. Chudak Banto.

N=3
flase: 0 6 3 1 0 0 (prazdne flase oznacene nulou)
Santo uz vypil: 6
Banto uz vypil: 5
Na tahu je: Banto

Banto, vypi 6dl flasu.        Santo vypil: 3dl
Banto, vypi 1dl flasu.

Dokopy Santo vypil 9dl ohnivej vody, ale Banto az 12. Chudak Santo.