Pátá série čtrnáctého ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 3. června 2002. Řešení můžete odevzdávat jak elektronicky, tak klasickou poštou na známou adresu.

Dotazy ohledně zadání můžete posílat na adresu ksp@mff.cuni.cz, nebo se ptát přímo na diskusním fóru KSP.

Zadání úloh


14-5-1 Nové slunce (12 bodů)


V Kocourkově se rozhodli, že již nadále nebudou snášet tyranii slunce, které když se mu chce, tak svítí, a když se mu nechce, tak se zaběhne schovat za mraky. Městská rada se usnesla, že město si pořídí slunce vlastní a lepší, které bude svítit tehdy, kdy to kocourkovští potřebují. Záhy ale ctihodný kocourkovský občan pověřený stavbou nového slunce zjistil, že osvítit celou zem není tak jednoduché a idea s nošením světla v pytlích se při dřívějších pokusech neodsvědčila. Proto se po delším uvažování rozhodl, že bude bohatě stačit, když jeho slunce osvítí celý Kocourkov. I pak ale zjistil, že oblast, kterou musí osvítit, není tak malá, a proto by potřeboval nalézt takové umístění pro slunce, aby poloměr osvícené oblasti mohl být co nejmenší. A s tímto problémem se obrátil na vás.

Na vstupu máte dáno N, počet domů v Kocourkově, a dále souřadnice jednotlivých domů xi, yi, kde 1≤ i≤ N (pro naše účely budeme domy považovat za body). Vaším úkolem je nalézt střed kružnice s nejmenším poloměrem, která obsahuje všechny zadané domy. Pokud je takových kružnic více, stačí nám libovolná z nich.

Příklad: Pro 4 domy ležící na souřadnicích (1,0), (1,1), (1,-1), (-1,-1) je nejlepší umístit lampu na souřadnice (0,0).

Řešení


14-5-2 Tramvaje (10 bodů)


Dvoukvítek při jednom ze svých turistických dobrodružství přepadl přes Okraj a padal a padal až dopadl na Zem. A nedopadl jen tak ledaskam, ale přímo do San Francisca, kde zrovínka dostavěli novou síť tramvajových tratí. Tratě ve městě tvoří čtvercovou síť o rozměrech M×N. Každá linka tramvaje tedy jezdí buď severo-jižním nebo východo-západním směrem z kraje města až na kraj (pochopitelně v obou směrech). Po každé trati jezdí v intervalu i minut za sebou tramvaje a jízda okolo jednoho bloku (tj. jízda mezi dvěma kříženími) jim trvá d minut. Dvoukvítka by nyní zajímalo, jak se má z křižovatky o souřadnicích (a,b) ((0,0) je severozápadní roh města) co nejrychleji dostat na křižovatku o souřadnicích (c,d). A to je již úkol pro vás.

Navrhněte algoritmus a napište program, který dostane na vstupu čísla M, N, i, d, p, t (p je počet minut, které Dvoukvítek potřebuje na přestup mezi dvěma tramvajemi a t je čas (počet minut od půlnoci), kdy Dvoukvítek vyráží na cestu) a dále souřadnice počáteční křižovatky (a,b) a souřadnice cílové křižovatky (c,d) a vypočte pro Dvoukvítka nejrychlejší cestu mezi těmito dvěma křižovatkami. Předpokládejte, že o půlnoci všechny tramvaje vyjíždí z okraje města.

Příklad: Pro město 3×5, interval tramvají i=22, dobu jízdy d=20, čas přestupu p=2 a čas startu t=19 je pro Dvoukvítka pro cestu z (1,1) do (2,5) nejlepší z křižovatky (1,1) jet na východ na (1,5), tam přestoupit a pokračovat na jih až do cílové zastávky (2,5).

Řešení


14-5-3 Zapeklitý kabel (9 bodů)


Jednoho dne Lucifer usoudil, že je třeba jít s dobou a neposkytovat své služby pouze prostřednictvím osobních kontaktů, ale i na základě telefonických objednávek. Ke splnění tohoto cíle bylo ale třeba vybudovat telefonní linku do pekla. Tento náročný úkol byl svěřen některým řešitelům dobře známé společnosti Shumm & Brumm. Když byl již celý kabel do pekla položen, zjistil technik, který měl telefony zapojit, že neví, který z konců a1,… ,ak na jedné straně kabelu patří ke kterému konci b1,… ,bk na druhé straně kabelu. Aby mohl telefony správně zapojit, potřeboval by technik znát, který konec drátu patří ke kterému. Naštěstí s sebou měl dostatek drátu a zkoušečku, a tak mohl na jedné straně libovolně mnoho drátů propojit a na druhé straně pak změřit, na kterých drátech bude napětí, když přivede napájení na nějaký drát. Protože ale cesta do pekel není vůbec příjemná, byl by technik rád, abyste mu poradili, jak zjistit na co nejméně cest mezi konci kabelu, který konec drátu ke kterému patří.

Navrhněte algoritmus a napište program, který dostane na vstupu počet drátů N a vždy vypíše, jaké dráty má technik na jedné straně propojit a pak mu poradí, jaké dvojice drátů na druhé straně proměřit. Po zadání výsledků měření pak program technikovi poradí nové zapojení a další měření a tak dále, dokud si nebude jistý, který konec patří ke kterém. Toto přiřazení pak vypíše.

Příklad: Pro 6 drátů by rady mohly vypadat následovně: Propojit na jedné straně a1a2, a2a3 a a4a5. Proměřit na druhé straně všechny dvojice. Technik zadá, že při připojení na b1 bylo napětí na b6, při připojení na b2 bylo napětí na b4 a b5 a při připojení na b3 nebylo napětí nikde (výsledky dalších měření jsou již těmito určeny a proto je nebudeme uvádět). Navrhneme technikovi propojit a3a4, a2a5, a2a6 a proměřit všechny dvojice. Po technikově sdělení, že při připojení na b1 bylo napětí na b3 a b5, po připojení na b2 nebylo napětí nikde a po připojení na b4 bylo napětí na b6 už víme, že kabely jsou propojeny následovně: a1b2, a2b5, a3b4, a4b6, a5b1 a a6b3.

Řešení


14-5-4 Turingovy stroje (10 bodů)


Váš úkol v této úloze bude poněkud netradiční: zkuste rozhodnout, zda existuje algoritmus (ten případně alespoň v hrubých rysech popište), který dostane na vstupu jednopáskový Turingův stroj T, nějaký vstup pro něj V a k a rozhodne, zda Turingův stroj na daném vstupu bude potřebovat více než k políček na pásce. Uvědomte si, že T se při práci nad vstupem V může zacyklit a nemusí nikdy skončit! Zkuste váš algoritmus vylepšit tak, že dostane na vstupu pouze T a V a vypíše počet políček, která stroji stačila ke zpracování vstupu (počet políček může být i nekonečný). O funkčnosti vašich řešení (popřípadě neexistenci řešení) se nás pokuste přesvědčit co nejlepším důkazem.

Řešení