Čtvrtá série devátého ročníku KSP

Řešení úloh

• 9-4-1: Cor Sair strikes back
• 9-4-2: Green Bit Problem
• 9-4-3: Hellish Clocks
• 9-4-4: Whatsit?
• 9-4-5: Something rotten?
• 9-4-6: Top secret

---

9-4-1 Cor Sair strikes back (Zadání)

---

Začneme úvahami o nutném počtu vážení: Určitě potřebujeme aspoň 3 vážení (protože ve 2 váženích může nastat pouze 9 různých výsledků a koulí je 12). 3 vážení nám ovšem stačí (dokážeme příkladem).

Nejprve si označíme balíky písmenky. (Můžeme použít 12 státních agentů, každý si bude pamatovat jeden balík a písmeno k němu přiřazené, nebo je nahradíme propisovací tužkou a napíšeme číslo přímo na balík – ale pozor na Agentskou odborovou organizaci.) [Michal Šída]

Tučnými písmeny budeme označovat balíky, o kterých víme, že mohou být normální nebo těžší (zbyla-li jediná taková, je jistě těžší), kurzívou pak normální či lehčí, monospacem zaručeně normální balíky a latinkou pak balíky dosud zahalené tajemstvím.

Při prvním vážení použijeme abcd – efgh [ijkl] (levá miska – pravá miska [zbytek]). V případě, že je levá miska těžší, víme, že situace vypadá takto: abcdefghijkl, pro pravou těžší analogicky abcdefghijkl, pro obě stejné abcdefghijkl.

Nyní pro první (analogicky i pro druhý) případ: vážíme aef – bgh [cdijkl]. Levá miska těžší ⇒ dostaneme abcdefghijkl, pravá těžší ⇒ abcdefghijkl, obě stejné ⇒ abcdefghijkl.

A pro případ třetí: vážíme ij – ak [bcdefghl]. Levá těžší ⇒ abcdefghijkl, pravá ⇒ abcdefghijkl, obě stejné ⇒ abcdefghijkl.

Všechny zbývající situace jsou vždy typu abc, abc či ab, případně a, které je všechny možno triviálně rozhodnout jediným vážením (v posledním případě doplníme na druhou misku zaručeně normální kouli). Tudíž třetím vážením se vždy dozvíme, který balík je jiný a dokonce i jak je jiný.

Pokud jste dodrželi postup a nevyskytly se určité nevhodné okolnosti (např. váhy všechny zásilky proměnily v dýně, nebo vysoká hustota tajných agentů květinářské společnosti Brambořík Ibišek Slunečnice), tak jste provedli zakázku za použití 3 vážení, takže si toho všimlo minimální množství lidí (jen cca 99.99%) a vy jste se stal nejslavnějším a nejbohatším važičem všech dob a žil jste šťastně až do smrti. (Což bylo ostatně asi 2 dny, protože tajná služba nerada nechává informace o své samozřejmě legální činnosti.) [opět Michal Šída]

Martin Mareš & Pavel Machek

---

9-4-2 Green Bit Problem (Zadání)

---

Ve světle vzorového řešení předchozí ufounské úlohy (9-2-3 – Překla-datel) jest ten pravý trik na "rozlousknutí" tohoto problému téměř zřejmý: opět budeme něco řešit pro postupně se zvětšující skupiny velikosti 2ⁱ.

Konkrétně se budeme snažit pro všechny části velikosti 2ⁱ vždy spočíst, kolik je ve které části jedničkových bitů, známe-li to již pro obě její poloviny a budeme podle zneužívat toho, že počet jedniček v k-bitovém čísle se vždy do k-bitového čísla vejde (jelikož k < 2^k pro každé k>1, kteroužto úvahu mnozí z vás opomněli učiniti).

Pro dvojbitové skupiny to lze provést triviálně a dokonce pro všechny najednou: stačí si označit a původní číslo, v němž jsou na lichých místech samé nuly a na sudých místech původní číslice, b číslo, v němž jsou na lichých místech opět nuly a na sudých místech číslice z oněch lichých míst a pak tato dvě čísla sečíst. Jelikož 2 < 2², k přenosu mezi jednotlivými 2-bitovými skupinami nedojde a dostaneme přesně to, co jsme chtěli.

Nyní již máme 128-bitové číslo z rozdělené na 2^7-k skupin velikosti 2^k, každá z nich již obsahuje počet bitů na počátku v této skupině se nacházejících. Opět zavedeme a obsahující jen skupiny na sudých místech a b původní skupiny z lichých míst přesunuté na sudá místa. A a+b je rozděleno na 2^6-k skupin velikosti 2^k+1. Takto pokračujeme tak dlouho, až získáme jednu skupinu velikosti 2⁷=128, což je hledaný výsledek.

Program bude vypadat takto (i^j značí zopakovat j-kráte posloupnost číslic i):

Získáváme tak řešení v 27 krocích…

Martin Mareš

---

9-4-3 Hellish Clocks (Zadání)

---

Označme si p_i původní nastavení i-tých hodin, r_i jejich požadované nové nastavení, a_ij posunutí i-tých hodin při zmáčknutí j-tého tlačítka a x_j počet zmáčknutí j-tého tlačítka.

Posunutí stejných hodin po zmáčknutí různých tlačítek se sčítají a protože je sčítání komutativní, nezáleží na pořadí stisků jednotlivých tlačítek, ale pouze na jejich počtu. Bude platit následující soustava rovnic (je to pouhé rozepsání pohybu hodin):

aneb pokud operace `+', `-' a `*' budeme provádět modulo 37, můžeme soustavu napsat v maticovém tvaru:

Mnozí z vás vědí, že podobnou soustavu lze v reálných (resp. racionálních) číslech řešit Gaussovou eliminační metodou. Málokdo si však uvědomil, že tato metoda nepožaduje práci přímo s reálnými (resp. racionálními) čísly. Pro zdárný průběh tohoto algoritmu je nutno, aby daný číselný obor byl tělesem, tj. aby splňoval některá základní pravidla (komutativita, asociativita, distributivita, jednotkový a nulový prvek) a aby ke každému nenulovému číslu existovalo číslo inversní.

Lze snadno ukázat, že množina Z_p zbytkových tříd po dělení prvočíslem p je tělesem. Základní vlastnosti, jako je např. komutativita, lze dokázat snadno, takže jediným problémem je existence inversního prvku. Jak již bylo v některé z předchozích sérií KSP ukázáno, plyne z Malé Fermatovy věty, že jsou-li čísla a a p nesoudělná, pak a^p-1≡ 1 mod p, tedy a·a^p-2≡ 1 mod 37. Poněvadž a může být pouze z množiny {0,1,2,…,p-1}, je nenulové a vždy s p nesoudělné. Pro každé nenulové a tedy můžeme nadefinovat a^-1=a^p-2 mod p.

Závěr je ten, že můžeme Gaussovu eliminační metodu použít stejným způsobem, jako kdybychom pracovali např. s racionálními čísly. Pouze musíme zaměnit původní aritmetické operace za nové.

Gaussova eliminační metoda se snaží upravit matici na trojúhelníkový tvar, tj. tvar, ve kterém jsou všechny koeficienty pod hlavní diagonálou nulové. Toho dosáhne řádkovými úpravami matice (násobení rovnic nenulovým číslem, výměna rovnic, sečtení rovnic). Snadno ověříme, že tyto úpravy nemění prostor všech řešení této soustavy.

Popišme po krocích tento důležitý algoritmus:

1. Provedeme druhý krok postupně pro všechny sloupce i=1,2,…,n.
2. Nyní jsou sloupce 1,2,…,i-1 v požadovaném tvaru, cheme upravit také i-tý sloupec.
   1. Je-li a_ii≠ 0, pak můžeme tuto rovnici podělit a_ii. Dále pro všechna j=i+1,i+2,…,n odečteme a_ji násobek této rovnice od j. rovnice. Tím vynulujeme všechna čísla v sloupci pod a_ii.
   2. Pokud je a_ii=0, zkusíme nalézt takové j∈{i+1,i+2,…,n}, že a_ji≠ 0. Pokud takové j existuje, můžeme prohodit i. a j. rovnici, bude splněna podmínka nenulovosti a můžeme postupovat podle bodu (a).
   3. Pokud žádné takové j nenalezneme, je celý sloupec včetne a_ii nulový. Pak žádné úpravy dělat nebudeme a skočíme rovnou na další sloupec. Při zpětném dosazování mohou nastanou dvě možnosti:
      • vyjde nám rovnice typu 0x=0, pak je řešením jakékoliv x, např. x=0 (ať nemusejí čerti zbytečně mačkat tlačítka),
      • nebo nám vyjde 0x=1, pak nemá soustava rovnic řešení.
3. Soustava je v diagonálním tvaru, tedy v poslední rovnici se vyskytne maximálně jedna neznámá, v předposlední dvě… Rovnice budeme odzadu řešit. Pokud bude existovat více řešení, zvolíme např. nulu, pokud nebude existovat žádné, ohlásíme, že řešení neexistuje.

Program je přímou implementací uvedeného algoritmu. Jsou k němu připojeny komentáře, takže jeho pochopení by nemělo činit potíže. Nezbývá než ještě poznamenat, že tabulka inversních čísel je předpočítaná, aby se urychlil výpočet.

Program

Robert Špalek

---

9-4-4 Whatsit? (Zadání)

---

Cílem této úlohy bylo, abyste zjistili nejenom co onen záhadný program dělá, ale také proč to vlastně dělá. Řešení bez důkazu tedy nebyla odměněna příliš štědře. Rovněž pak důkaz typu "zkoušel jsem to pro 10000 hodnot a fungovalo to" nemá žádnou váhu (to, že program funguje pro N různých vstupů, ještě nevypovídá příliš o tom, co dělá pro ty ostatní, leda že by již žádné ostatní neexistovaly [ale v tomto příkladu bylo ≈ 10⁹ možností, takže probrání všech v rozumném čase nehrozilo]).

A co že vlastně program dělal? Inu, byl to interpreter jednoduchého programovacího jazyka. Text interpretovaného programu byl uložen v řetězci s, jazyk pracoval se sedmiprvkovým polem, jehož prvky si označíme k₀ až k₆. Prvek k₀ ukazoval do pole s na právě prováděný příkaz (pokud "vyjel" pryč, program se zastavil), k₁ fungoval jako "data pointer" (označíme si jej δ) – tedy obsahoval číslo prvku k_i, se kterým se prováděly některé operace a k₂ sloužil k uchování cílové adresy skoku. Jazyk se skládal z následujících příkazů:

Vstupy programu byly uloženy v k₃ a k₄, program začínal na pozici k₀=1, δ=k₁ bylo inicializováno na 1 a k₂ na 2. Výsledek byl předán v k₆. Zbylý "registr" k₅ sloužil jako pomocná proměnná.

Interpretovaný program vypadal takto (po přepsání neznámých znaků na hvězdičky a očíslování pozic):

A provádí toto:

1–4	δ=2, k2=6
5–6	δ=6
7–8	k6 ←2·k6, opakuj dokud k6 ≠ 0 (vše je typu word, pročež
	všechny operace fungují modulo 65536, a tak k nule dojít musíme)
9–10	δ=5, k2=10
11–12	Prakticky stejným způsobem nulujeme k5.
13–18	δ=2, k2=26
19–21	δ=3 a pokud k3 ≠ 0, skáčeme na pozici 27.
22–26	δ=2, k2=208, zastavujeme se (skok mimo).
27	k3 ←k3 - 1
28–30	δ=4, k2=30
31	k4 ←k4 - 1
32–33	δ=6, k6 ←k6 + 1
34–35	δ=5, k5 ←k5 + 1
36–37	δ=4, pokud k4 ≠ 0, skáčeme na 31. Tímto jednoduchým cyklem přesouváme
	původní hodnotu k4 do k5 a současně ji přičítáme ke k6, načež zbyde k4=0.
38–40	δ=5, k2=40
41	k5 ←k5 - 1
42–43	δ=4, k4 ←k4 + 1
44–46	δ=5 a pokud k5 ≠ 0, skáčeme na pozici 41. I hle, prohodili jsme k4 a k5!
47–49	k2=δ=2
50–52	k2 = 10
53–57	δ=5, k5=1, skáčeme (nepodmíněně) na pozici 11 (všimněte si,
	že proměnné δ i k2 jsou nastaveny stejně jako když jsme se tam
	dostaly minule – vše tedy bude probíhat stejně).
58–60	Sem se nikdy nedostaneme…

Povšimněte si nyní, že program se skládá ze dvou částí: inicializace (příkazy 1–10, vlastně jen k₆←0) a velký cyklus (11–57) prováděný k₃-krát a v každém průchodu přičítající k₄ ke k₆. Na konci vracíme k₆ jako výstup programu… Vypadá to jako násobení dvou přirozených čísel, tváří se to jako násobení dvou přirozených čísel a nenechte se mýlit – je to násobení dvou přirozených čísel! Záhada jest rozřešena (zejména uvědomíme-li si, že pokud k₄=0, provádíme vnitřní cyklus 65536-krát, takže tak jako tak nula po dlouhém počítání díky přetečení vyjde) a program můžeme triviálně zjednodušit na:

function thatsit(a,b:word):word;
begin
   thatsit := a*b;
end;

Jak prosté, milý Watsone!

Martin Mareš

---

9-4-5 Something rotten? (Zadání)

---

Jak už to tak v našem semináři poslední dobou bohužel bývá (slibujeme, že se polepšíme!!), zadání této úlohy nebylo jednoznačné. Respektive ono možná jednoznačné bylo, ale odporovalo uvedenému příkladu. A po právu. Formulace zadání odpovídalo úloze, že si silničáři v království vyberou, které cesty nechají rozpadnout a tyto cesty se posléze rozpadnou. My máme silničářům sdělit, kolik cest mohou vybrat.

Vyřešit takovou úložku je veskrze triviální, neboť k tomu, aby města zůstala navzájem dosažitelná, postačuje kostra grafu silnic, která má vždy N-1 silnic. Pokud tedy má zůstat království souvislé, stačí nám udržovat N-1 vybraných cest a zbytek cest se může rozpadnout. Každý vidí, že spočítat počet cest a odečíst od toho N-1 si nezaslouží v zadání nabízených 12 bodů.

Tedy dvě okolnosti nasvědčovaly tomu, že zadání chce říci něco jiného, než říká. Zadání totiž chtělo říci, že silničáři nemají ve své kompetenci určit, které cesty se rozpadnou. Tamější silničáři totiž fungují tak, že implicitně nedělají nic. Když jim však ze všech koutů království přicházejí zprávy, že se dohromady rozpadá již x silnic, potřebují vědět, jestli je to stále ještě O.K., nebo jestli už náhodou nehrozí to, že se království rozpadne na dvě a více částí a měli by začít něco dělat. Jelikož poddaní neznají (případně když už znají, tak cesou alespoň zkomolí) názvy měst, hlásí silničářům pouze počty rozpadlých silnic.

Vaším úkolem tedy bylo na základě mapy silnic zjistit, kdy musejí silničáři začít pracovat, tedy maximální počet cest, které se mohou rozpadnout, aniž by to ohrozilo celistvost království. Této úložce se v terminologii teorie grafů říká hledání minimálního řezu v grafu, resp. v našem případě postačuje nalezení jeho velikosti. Co je to minimální řez? Řez v grafu je množina hran, které když se vypustí, tak se graf rozpadne. Minimální řez je pak samozřejmě řez, který je nejmenší ze všech možných řezů grafu. Silničáři tedy musí pracovat tehdy, pokud se počet rozpadlých silnic značně přiblížil velikosti minimálního řezu v jejich systému silnic.

Úloha hledání řezů v grafu souvisí s jinou zajímavou grafovou úložkou, s takzvanými toky v sítích. Síť není opět nic jiného než graf, avšak jelikož úloha má svůj předobraz v inženýrských sítích – potrubních a elektrických rozvodech – zkoumanému grafu se přezdívá síť. Tok v síti je pak prostě nějaké konkrétní rozložení proudu, ať již elektrického, nebo vody, na jednotlivé spojnice (hrany) sítě. Předpokládá se, že v jednom místě v síti je takzvaný zdroj, ze kterého to teče, a dále je tam jeden spotřebič, do kterého vše teče a jinde v síti již žádný proud nevzniká ani nezaniká, tj. to co do ostatních uzlů vstoupí, to z nich i vystoupí. [MJ: Zlí jazykové tvrdí, že to není připad vodovodních ani elektrovodných sítí, protože tam se vše ztrácí všude…]

Evidentně spotřebič odebírá právě to, co zdroj vypouští. Když na rozložení proudu dáme omezení, že po každé spojnici může protékat buď jednotkový objem libovolným směrem, nebo nic, pak maximální objem proudu vypouštěný zdrojem nám říká, kolik je maximální počet hranově nezávislých cest mezi zdrojem a spotřebičem. To odpovídá velikosti minimálního řezu oddělujícího spotřebič od zdroje. Toto tvrzení zde ponecháme bez důkazu a odkážeme laskavého čtenáře na knihu L. Kučery "Kombinatorické algoritmy". Když takto pro všechny možné spotřebiče a zdroje prozkoumáme minimální řezy, které je oddělují, nalezneme hledaný minimální řez.

Všimněte si, že můžeme zafixovat jeden konkrétní zdroj a prozkoumat jen všechny možné spotřebiče. To vyplývá z toho, že pokud se nějakým řezem graf rozpadne, speciálně tedy minimálním, pak námi vybraný zdroj zůstane v jedné z částí grafu a libovolný spotřebič z druhé části grafu nemůže odebírat více než je velikost použitého minimálního řezu. Zároveň vůči jednomu ze spotřebičů bude pro přepravu použita maximální zátěž minimálního řezu, tj. všechny jeho hrany. (Rozmyslete si správnost těchto tvrzení.)

Jak tedy zjistit velikost maximálního toku mezi daným zdrojem a spotřebičem? Tuto úložku vyřešíme tak, že budeme tok postupně zlepšovat. Na začátku řekněme, že nikde nic neteče. Poté se pokusíme nalézt takovou cestu od zdroje ke spotřebiči, že po jednotlivých hranách této cesty buď nic neteče, nebo po nich něco teče, avšak v opačném směru, tj. ve směru od spotřebiče ke zdroji. Pomocí této cesty můžeme zlepšit tok tak, že po jejích hranách, po kterých nic neteklo, necháme téci jednotkový objem směrem ke spotřebiči a po hranách, po kterých teklo něco směrem od spotřebiče, nebude téci nic. Snadno nahlédneme, že takto zlepšený tok bude korektní, tedy v dotčených uzlech bude i nadále platit to, že co do nich vstupuje, to z nich i vystupuje, a opačně. Pozorný čtenář již jistě vytušil, že takovéto zlepšení provedeme maximálně N-1-krát.

Zbývá doplnit, jak nalézt zlepšující cestu. Zlepšující cestu budeme hledat průchodem grafu do šířky a to tak, že budeme používat pouze zlepšující cesty, tj. budeme chodit pouze po hranách, kde nic neteče, nebo kde jdeme proti proudu. Takto budeme nalézat vrcholy, do kterých vede zlepšující cesta. Pokud již víme, že do daného vrcholu zlepšující cesta vede, tak ho již znovu procházet nebudeme, neboť nám postačuje nalezení nějaké zlepšující cesty. Hledání skončí tehdy, když nalezneme zlepšující cestu až ke spotřebiči, nebo tehdy, když už z žádného dosaženého vrcholu nelze jít po nevyužité hraně, či proti proudu. Jelikož při tomto průchodu musíme v nejhorším případě probrat téměř všechny hrany, je časová složitost této fáze O(M), kde M je počet hran. (Předpokládáme, že M>N).

Celková časová složitost pak dosáhne O(N²M), neboť pro N spotřebičů budeme vyhledávat maximální tok, což znamená maximálně N-krát nalézt zlepšující cestu v čase O(M). Jelikož počet hran M<N², lze též použít hrubší odhah O(N⁴). Paměťová složitost je O(M), neboť si musíme pamatovat aktuální tok a popis grafu.

Zbývá snad jen dodat, že pro hledání minimálního řezu existuje i algoritmus pracující v čase O(N³) a taktéž pravděpodobnostní algoritmus, jenž řešení nalezne v průměrném čase O(N² log² N). Pravděpodobnostní algoritmus je algoritmus, který si v průběhu výpočtu může házet kostkou. Některá tvrzení jsme zde ponechali bez důkazu (např. správnost algoritmu hledání maximálního toku), neboť rozsahem přesahují možnosti tohoto řešení. Zvídavé čtenáře tedy odkazujeme již zmíněnou knihu od Dr. Kučery, kde ke všem zde uvedeným tvrzením a algoritmům nalezne důkaz jejich správnosti. Vzorový program je pro jednoduchost napsán s časovou složitostí O(N⁴), neboť z hlediska počtu hran nemá optimálně napsané vyhledávání minimálního toku.

Program

Michal Koucký

---

9-4-6 Top secret (Zadání)

---

Opravdu náhodná čísla není možné generovat "čistým" algoritmem. Každý takový algoritmus má podle definice předem předvídatelné chování, a tedy jím vygenerovaná čísla není možné považovat za opravdu náhodná, protože jsou efektivně vyčíslitelná. (Je možné sestrojit algoritmus, který bude generovat posloupnost "náhodných" čísel, která se nikdy nezačne opakovat, např. číslice čísla π. Ani takovou posloupnost ale není možné považovat za posloupnost opravdu náhodných čísel.) [Pozn. MJ: Nikdo ovšem dosud nedokázal, že něco jako náhodná čísla vůbec může existovat – pokud je vesmír deterministický, náhodná čísla neexistují, ale nepředvídatelná čísla stále ještě ano – zkuste se nad tím zamyslet.]

Musíme se tedy vzít na pomoc něco z reálného světa. Budeme se zde zabývat pouze metodami, které jsou vhodné pro spojení s počítačem. (Vynecháme obligátní házení kostkou, losování předmětů, atp.)

Všechny následující metody jsou založeny na tom, že měří náhodnou složku nějakého jevu.

Jednoduše realizovatelné je měřit s velkou přesností, co člověk považuje za chvíli, a za náhodné číslo prohlásit zbytek po dělení této hodnoty malým číslem:

uses Crt;

function Random256: Byte;
{ Generuje náhodné číslo v rozsahu 0..255 }
 label start;
 var x: longint;
 begin
start:
 writeln('Za chvíli stiskni klávesu.');
 x := 0; while not keypressed do inc(x);
 while keypressed do readkey;
 if x < 100000 then begin
  writeln('Tohle není žádný rychlokurs!');
  goto start;
  end;
 Random256 := Byte(x); {rychlejší `x mod 256'}
end;

Modifikace tohoto postupu je použita ve velmi rozšířeném programu Pretty Good Privacy (PGP). Pro masové použití např. v bankách je ovšem tento postup nevhodný.

Brownův pohyb, rozpad radioaktivního materiálu a další (prozatím) náhodné fyzikální jevy, jsou v praxi těžko použitelné, jelikož k jejich automatickému měření je třeba drahé zařízení.

Nejsnáze realizovatelné je měření šumu nějaké elektrické veličiny:

• šum éteru – měří se s velkou přesností proud, který teče z antény.
• šum sítě – měří se s velkou přesností napětí v zásuvce.
• šum polovodičového přechodu (Snem většiny konstruktérů diod je vyrobit takovou, která vůbec nešumí. Existuje ale také malá, nicméně dobře placená, skupina konstruktérů diod, jejíž snem je vyrobit diodu, která šumí co nejlépe.)

Je možné, že za pár let bude pro podporu šifrování standardní součástí PC obvod pro generování náhodných čísel. Zatím se vyrábějí pouze specializované desky.

Jan Kotas

Menu