Matematická olympiáda – kategorie P

Řešení úloh ústředního kola (2. soutěžní den) 48. ročníku

P-III-4 Nákup

Zadání nejdříve omezíme na vybrané druhy výrobků (přičemž zrušíme nabídky neobsahující námi vybrané druhy zboží, z každé nabídky ostatní předměty vyškrtáme, pokud nějaká nabídka obsahovala počet předmětů větší než ten, jenž chceme nakoupit, omezíme jej na nakupovaný počet a vyjde-li po tomto seškrtání více nabídek se stejnými počty vybraných předmětů, ponecháme z nich pouze tu nejlevnější). Z podmínek uvedených v zadání triviálně plyne, že takto upravená úloha má stejné řešení jako úloha původní. Budeme ji řešit dynamickým programováním.

Máme tedy předměty očíslované 1 až k <= 5 s cenami ci a od každého z těchto předmětů chceme nakoupit mi <= 6 kusů s využitím nabídek zlevňujících sadu tvořenou pij kusy j-tého druhu zboží na cenu wi.

Nejprve si nadefinujeme konfigurace a operace s nimi:

Naším cílem je tedy nalézt konfiguraci e, která je rozšířením zadané konfigurace m a její we je nejmenší možné. Jelikož nákup se vždy skládá ze zlevněných nabídek doplněných jednotlivými předměty, je každou konfiguraci e možno rozložit na prostou konfiguraci p a triviální konfigurace ki (vybrané z množiny všech Ti, ale některé se mohou vyskytnout vícekrát) takové, že e = p + SUMAi ki a we = wp + SUMAi wk(i). Pokud tedy dokážeme spočítat ceny wp pro všechny prosté konfigurace, máme vyhráno, protože stačí prozkoumat všechny takové a každou doplnit triviálními tak, aby obsahovala všechny požadované předměty z m a je jisté, že mezi takto získanými konfiguracemi bude i hledaná e.

Ceny prostých konfigurací spočteme indukcí podle vp. Pro prázdnou konfiguraci (víme o ní, že vp=0) je cena nulová. Známe-li již ceny všech prostých konfigurací qi takových, že vq(i) < vp, spočteme cenu prosté konfigurace p: Jelikož optimální zaplacení každé neprázdné prosté konfigurace zahrnuje přikoupení nějaké zlevněné nabídky k některé menší prosté konfiguraci, stačí položit:
wp=min{ wq(i) + wp(j) ; qi + pj = p }
To můžeme snadno učinit, jelikož všechna qi, která potřebujeme, jsou v daném okamžiku již spočtena (qi < p, tudíž také vq(i) < vp).

Zadání od nás ovšem požaduje nejen spočtení we, ale také zjištění, které nabídky jsme pro tento výpočet využili. K tomu stačí při výpočtu minima v indukčním kroku připojit informaci o tom, pro jaké i,j se minima nabývá a podle toho pak prostou konfiguraci p, jejímž rozšířením získáme optimální zaplacení e, rozložit na nabídky (odebráním poslední přidané nabídky získáme menší prostou konfiguraci, kterou rozložíme týmž způsobem).

Časová složitost: Připravná fáze (filtrování zadání) trvá O(nm), oceňování prostých konfigurací O(smk) (kde s=(1+maxi mi)k je počet všech konfigurací), ocenění zadané konfigurace O(s\cdot k) a zpětné vyhledání optimálního zaplacení O(s). Celkem tedy O((1+maxi mi)kmk + nm).

Paměťová složitost: O((1+maxi mi)k + mk + n).

program P_III_4; { P-III-4 -- Nakup -- Martin Mares, brezen 1999 } const MaxN = 100; { Maximalni pocet predmetu } MaxO = 100; { Maximalni pocet nabidek } MaxS = 5; { Maximalni pocet vybranych predmetu } MaxX = 6; { Maximalni pocet vybranych kusu od kazdeho predmetu } NStates = 16807; { Velikost stavoveho prostoru: (MaxX+1)^MaxS } type CVector=array [1..MaxS] of byte; { Konfiguracni vektor } SVector=array [0..NStates-1] of word; { Stavovy vektor } var NItems:integer; { Pocet predmetu } Price:array [1..MaxN] of word; { Ceny predmetu } SPrice:array [0..NStates-1] of word; { Pro kazdy stav min. cena, } SLast:array [0..NStates-1] of byte; { posledni pridana nabidka } SBack:^SVector; { a predchozi stav } Index:array [1..MaxN] of byte; { Prevod cisel predmetu } Xedni:array [1..MaxS] of byte; { Prevod zpet } Count:array [1..MaxS] of byte; { Kolik chceme kusu } NSel:integer; { Pocet vybranych predmetu } Offer:array [1..MaxO] of CVector; { Nabidky pro vybrane predmety } OPrice:array [1..MaxO] of word; { Ceny nabidek } NOff:integer; { Pocet nabidek } OCount:array [1..MaxO] of byte; { Pocet pouziti nabidek } OXedni:array [1..MaxO] of word; { Precislovani nabidek } function Encode(var x:CVector):word; var i,j:word; { Vytvoreni cisla stavu z konfigurace } begin i := 0; for j:=NSel downto 1 do i := i*(MaxX+1) + x[j]; Encode := i; end; procedure Decode(var x:CVector; state:word); var j:word; begin { Vytvoreni konfigurace z cisla stavu } for j:=1 to NSel do begin x[j] := state mod (MaxX+1); state := state div (MaxX+1); end; end; procedure ReadInput; { Nacteni vsech vstupnich dat a jejich filtrace } var i,j,k,l,c,z:integer; begin read(NItems); { Predmety a jejich cena } for i:=1 to NItems do read(Price[i]); read(NSel); { Vybrane predmety } FillChar(Index, sizeof(Index), 0); for i:=1 to NSel do begin read(j); read(Count[i]); Index[j] := i; { Predmety si precislujeme } Xedni[i] := j; end; read(c); { Nabidky } NOff := 1; { V tabulce stavu si budeme prechodne pamatovat ceny nabidek } for i:=0 to NStates-1 do SPrice[i] := maxint; for i:=1 to c do begin for j:=1 to NSel do Offer[NOff,j] := 0; k := 0; repeat read(j); { predmet } if j<>0 then begin read(l); { pocet } z := Index[j]; if (z > 0) and (l > 0) and (Count[z] > 0) then begin if l > Count[z] then l := Count[z]; { orezani } inc(k); Offer[NOff,z] := l; end; end; until j=0; read(j); { cena nabidky } l := Encode(Offer[NOff]); { cislo odpovidajiciho stavu } if (k>0) then { byl tam alespon jeden z vybranych predmetu } if SPrice[l] = maxint then begin SLast[l] := NOff; { zatim nejlepsi nabidka pro danou kombinaci } OPrice[NOff] := j; OXedni[NOff] := i; inc(NOff); SPrice[l] := j; end else if SPrice[l] > j then begin { zlepseni nejake predchozi } move(Offer[NOff], Offer[SLast[l]], sizeof(CVector)); SPrice[l] := j; OPrice[SLast[l]] := j; OXedni[SLast[l]] := i; end; end; dec(NOff); end; procedure FillStates; { Spocteme cenu pro vsechny `rozumne' kombinace nabidek } var c,d:CVector; i,j,k,l:word; begin new(SBack); SPrice[0] := 0; for i:=1 to NStates-1 do SPrice[i] := maxint; for i:=0 to NStates-1 do { Prochazime vsechny stavy } if SPrice[i] <> maxint then begin { Ty nedostupne preskakujeme } Decode(c, i); { Spocteme konfiguraci } for j:=1 to NOff do begin { Zkousime pridavat nabidky } for k:=1 to NSel do begin d[k] := c[k] + Offer[j,k]; if d[k] > Count[k] then { Prilis mnoho predmetu } d[k] := Count[k]; end; k := Encode(d); { Spocteme cislo stavu } l := SPrice[i] + OPrice[j]; { a cenu konfigurace } if l < SPrice[k] then begin { Je to zlepseni? } SPrice[k] := l; SLast[k] := j; { Ulozim, odkud jsem prisel } SBack^[k] := i; end; end; end; end; procedure FindMin; { Prochazime konfigurace a rozsirujeme je na reseni } var c:CVector; i,j,p,min,mini:word; begin min := maxint; for i:=0 to NStates-1 do { Probereme vsechny stavy, } if SPrice[i] < maxint then begin { ktere jsou dostupne } p := SPrice[i]; Decode(c, i); { Spocteme konfiguraci } for j:=1 to NSel do { Doplnime predmety, abychom dostali } if c[j] < Count[j] then { pripustne reseni } inc(p, (Count[j]-c[j])*Price[Xedni[j]]); if p<min then begin { A udrzujeme si minimum } min := p; mini := i; end; end; writeln(min); { Vypis vysledku: minimum } for j:=1 to NOff do OCount[j]:=0; { a pouzite nabidky } while mini>0 do begin inc(OCount[SLast[mini]]); mini := SBack^[mini]; end; for j:=1 to NOff do if OCount[j] > 0 then writeln(OXedni[j], ' ', OCount[j]); end; begin assign(input, 'nakup.in'); reset(input); assign(output, 'nakup.out'); rewrite(output); ReadInput; FillStates; FindMin; end.

P-III-5 Vigenerova šifra

Úlohu je možné řešit více různými způsoby. Ukážeme si proto několik technik, které je možné při řešení použít. Zdrojový text vzorového programu neuvádíme, řešitelé ho dostanou na disketě zároveň se vstupními soubory. Obvykle se Vigenerova šifra dešifruje pomocí frekvencí výskytů jednotlivých písmen v daném přirozeném jazyce. Jelikož náš slovník není příliš velký a v zašifrovaném textu jsou zachovány mezery, je možné s úspěchem použít i vhodně upravené prohledávání všech možností (z množiny všech klíčů vybereme dostatečně malou podmnožinu možných klíčů a ty vyzkoušíme). Uvedeme hlavní myšlenky obou zmíněných postupů.

Řešení pomocí frekvencí výskytů je sice rychlé, ne vždy ale najde správné řešení. Proto je poměrně vhodné spojit tuto techniku ještě s prohledáváním všech možností. Můžeme například zkusit uhádnout řešení pomocí frekvencí a pokud tímto způsobem nenajdeme správné řešení, spustíme ještě prohledávání všech možností. Případně můžeme pomocí frekvencí výskytů uhádnout délku klíče a zkoušet pak už jenom klíče této délky.

Řešení pomocí frekvencí výskytů

Toto řešení je založeno na skutečnosti, že v textu zapsaném v přirozeném jazyce se některá písmena (například samohlásky) vyskytují častěji než jiná písmena. Frekvencí písmena v textu budeme nazývat počet výskytů tohoto písmena v textu vydělený celkovým počtem písmen v textu. Jestliže si pro několik dlouhých textů zapsaných v témže jazyce spočítáme frekvence jednotlivých písmen, uvidíme, že jsou dosti podobné. Při dešifrování textu se tedy snažíme najít takový klíč, aby se vzniklé frekvence co nejvíce podobaly frekvencím použitého přirozeného jazyka.

Malá písmena anglické abecedy označme čísly 0 (a) až 25 (z). Vynechejme nyní ze zašifrovaného textu mezery a písmena zašifrovaného textu označme po řadě c0,c1,... ,cn-1, kde n je počet písmen v zašifrovaném textu. Klíč budeme označovat K = k0k1...kd-1. Nalezení klíče se skládá ze dvou podúloh: v první fázi musíme zjistit délku klíče d a ve druhé samotný klíč K.

Předpokládejme nyní, že známe délku klíče d. Písmena si rozdělíme do d skupin podle toho, kterým písmenem klíče byla zašifrována. První skupinu budou tedy tvořit písmena c0,cd,c2d,..., která byla zašifrována znakem klíče k0. Obecně skupinu zašifrovanou znakem klíče ki tvoří znaky ci,cd+i,c2d+i,....

Pokusíme se nyní určit písmeno ki. Pokud jím odšifrujeme jeho skupinu písmen, měly by se jejich frekvence podobat rozdělení frekvencí jednotlivých znaků v běžném textu. Musíme si ovšem stanovit kritérium, které určí, nakolik se dvě rozdělení frekvencí sobě podobají. Při statistických výpočtech se obvykle používá následující vztah (pj je frekvence výskytu písmena j v běžném textu, fj,ki je frekvence výskytu písmena j v naší skupině po odšifrování pomocí ki):
ok(i) = sqrt( (f0,k(i) - p0)2+ ... + (f25,k(i) - p25)2),
přičemž frekvence se sobě podobají tím více, čím je nižší hodnota ok(i). Vyzkoušíme tedy, pro které ki bude tato suma minimální (všimněme si, že platí fa,b = fa+i, b+i pro i=0,1,...,25, + je sčítání modulo 26; z čísel fa,b nám tedy stačí počítat jen f0,0,f1,0,... f25,0).

Popsaným způsobem jsme schopni najít klíč pro danou délku efektivně a s velkou pravděpodobností. Popsaná metoda funguje pro dostatečně dlouhé šifrované texty, pro její spolehlivý chod stačí kolem 50 znaků šifrovaného textu na jeden znak klíče.

Zůstává problém s určením délky klíče. Nejjednodušší metodou je vyzkoušet všechny délky od 1 do určeného maxima, najít pro danou délku kandidáta na klíč, dešifrovat s ním zašifrovaný text a ověřit, zda jsme dostali text skládající se ze slov obsažených ve slovníku. Jinou možností je pokusit se určit i délku klíče statisticky - vybereme takovou délku klíče, aby statistická odchylka frekvencí výskytu písmen v textu dešifrovaném pomocí nalezeného klíče (dané délky) od hodnot pi byla minimální. Je-li řetězec K klíčem, budou klíči také KK, KKK, ... atd. Proto minimální odchylku dostaneme pro více délek, z nichž samozřejmě vybereme minimální.

Prohledávání všech možností

Při prohledávání všech možností zkoušíme všechny možné délky klíče od 1 až do 50 a snažíme se nalézt první, pro kterou existuje vyhovující klíč. Pro každou délku dále zkoušíme jednotlivé klíče.

Všech klíčů délky k existuje 26k, což je už pro poměrně nízké k velmi velké číslo. Proto nemůžeme bezhlavě zkoušet všechny možnosti. Dobré řešení dostaneme třeba takto. Náš klíč budeme vytvářet postupně. Začneme s klíčem, v němž budou místo písmen znaky *, které znamenají, že dané písmeno klíče ještě není určeno (tj. může tam být libovolné písmeno). Potom postupně po jedné budeme hvězdičky nahrazovat písmeny, přičemž pro každou hvězdičku rekurzívně zkoušíme všechny možnosti nahrazení ostatních hvězdiček v klíčí. Důležité je, že vždy, když některou hvězdičku nahradíme písmenem, zkontrolujeme konzistenci dosud vytvořeného klíče se zašifrovaným textem (a slovníkem). To znamená, že v každém slově zašifrovaného textu odšifrujeme pomocí našeho klíče písmena, která jsme již v klíči určili, a na pozice odpovídající hvězdičkám dáme hvězdičky. Potom zjišťujeme, zda se dají hvězdičky v rozšifrovaném slově nahradit tak, abychom dostali nějaké slovo ze slovníku (tj. hledáme ve slovníku slovo, které se s naším nezašifrovaným slovem shoduje na všech nehvězdičkových pozicích). Jakmile zjistíme, že některé slovo po takovémto částečném rozšifrování nelze doplnit na slovo ze slovníku, víme, že v našem dosud vytvořeném klíči je některé písmeno špatně a nemá tedy smysl zkoušet v něm nahrazovat další hvězdičky písmeny.

Zkušenosti ukazují, že pokud zkoušíme například nesprávnou délku klíče, většinou hned po dosazení prvního písmena do klíče zjistíme, že tato možnost není správná, stačí tedy vyzkoušet 26 možností. Podobně velmi rychle se tímto způsobem objeví i případ, když umístíme na některé místo chybné písmeno. Na první pohled se může zdát, že prohledávat po doplnění každého písmena do klíče každé slovo zašifrovaného textu a pro každé takové slovo ještě prohledávat velkou část slovníku se nevyplatí, ve skutečnosti nám však tímto prohledáváním ubude velmi mnoho možností.

Při tomto způsobu řešení je vhodné slovník reprezentovat tak, že slova máme rozdělena do seznamů podle délky, abychom při vyhledávání nemuseli zbytečně prohlížet i slova jiných délek. V těchto seznamech už nemusíme slova nijak speciálně uspořádávat, vyhledáváme v nich lineárně.

Popíšeme si ještě jedno možné vylepšení. Je založeno na jednoduché myšlence: slov některých délek (velmi krátkých a velmi dlouhých slov) je poměrně málo. Kdybychom text dešifrovali ručně, zkoušeli bychom na tato místa dosazovat jednotlivá slova, což by nám určilo část klíče. Takto získanou část klíče bychom se pak snažili rozšířit.

Nyní ukážeme, jak lze tuto myšlenku využít v programu. Předpokládejme například, že v zašifrovaném textu je na některém místě slovo délky 2 začínající na a a že žádné slovo délky 2 obsažené ve slovníku nezačíná písmenem z. Z toho vyplývá, že v klíči na pozici, která se při šifrování umístí pod dané místo textu, určitě nebylo písmeno b, neboť pomocí písmena b jsme písmeno a mohli dostat jedině z písmena z (a písmeno z na dané pozici být nemůže).

Podobných omezení můžeme na základě slovníku najít více a pro každou pozici klíče vytvoříme seznam hodnot, které se na tomto místě v klíči mohou vyskytnout. V příznivém případě se stane, že na některé pozici nám nezůstane žádná možnost - znamená to, že jsme zvolili nesprávnou délku klíče a je třeba zkoušet jinou.

Jestliže však máme pro každou pozici klíče aspoň jednu možnost, můžeme použít získané informace při prohledávání. Prohledáváme v podstatě stejně jako předtím - vždy dosadíme jedno písmeno do klíče a ověříme správnost klíče. Zkoušíme však už jen ty možnosti, které jsme dosud nevyloučili. Navíc je výhodné začít těmi pozicemi klíče, které mají nejméně možností.

Pro přirozené texty se při tomto způsobu řešení často stává, že pro nesprávnou délku klíče získáme pro některou pozici nula možností, takže k samotnému prohledávání ani nedojde. Naopak, když zkoušíme správnou délku klíče, pro mnohé (někdy dokonce pro všechny) pozice zůstane jen jedna možnost, kterou můžeme přímo do klíče dosadit.