Matematická olympiáda – kategorie P

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

P-III-4 Tunely

První část úlohy vyřešíme pomocí Dijkstrova algoritmu. Postupně budeme procházet městy dostupnými z výchozího města X, pořadí procházení bude řízeno průběžně počítanými hodnotami H, které jsou přiřazovány jednotlivým městům. U každého města evidujeme maximální výšku vozidla, jaké se do města může dostat. Pro každé město navíc rozlišujeme, zda je jemu přiřazená hodnota H dočasná (možná se ještě změní, tj. vylepší), nebo zda je již trvalá (určuje výslednou maximální výšku vozidla, jaké může dojet do tohoto města).

Před zahájením průchodu bude mít výchozí město X přiřazenu dočasnou hodnotu "nekonečno" (dostane se do něj vozidlo libovolné výšky) a všechna ostatní města mají dočasnou hodnotu 0 (zatím do nich neznáme žádné cesty). Celý výpočet pak bude probíhat po krocích tak dlouho, dokud nebude cílovému městu Y stanovena trvalá hodnota, popř. dokud nebude přiřazena trvalá hodnota všem dostupným vrcholům a Y mezi nimi nebude (pak není město Y z města X vůbec dostupné). V každém kroku výpočtu se provedou tyto akce:

  1. Určíme město s maximální dočasnou hodnotou H.
  2. Dočasnou hodnotu tohoto města prohlásíme za trvalou.
  3. Všem jeho bezprostředním sousedům, kteří mají ještě dočasnou hodnotu, přepočítáme jejich hodnoty H (viz program). Zvýšíme tím všechny ty dočasné hodnoty měst, které je možné zvýšit díky cestě vedoucí přes právě vybrané město.
Výsledkem Dijkstrova algoritmu bude určení maximální výšky vozidla V, jaké může projet z města X do města Y, příp. zjištění, že tato města nejsou vůbec spojena silnicemi.

K vyřešení druhé části úlohy, tj. nalezení takové cesty vozidlem výšky V z X do Y, aby vedla přes minimální počet měst, použijeme průchod do šířky. Při procházení přitom budeme uvažovat pouze ty silnice, na nichž není žádné omezení na výšku vozidla nebo na kterých omezení dovoluje projet vozidlu výšky V. Z technických důvodů je výhodnější provádět průchod do šířky "pozpátku" od cílového města Y k výchozímu městu X. Při závěrečném zpětném chodu pak totiž budem moci přímo vypisovat trasu vozidla z X do Y, jinak bychom ji ještě museli převracet.

Průchod do šířky je řízen pomocnou frontou, v níž jsou v každém okamžiku uložena čísla těch měst, do kterých jsme již došli, ale z nichž jsme ještě nepokračovali v cestě dál. V druhém poli si musíme evidovat již navštívená města (abychom do nich nechodili opakovaně) a ve třetím poli si ke každému městu zaznamenáme, odkud jsem do něj poprvé přišli (jeho předchůdce při průchodu). Procházení do šířky provádíme tak dlouho, dokud nedojdeme do města X.

Výslednou trasu získáme na závěr procházení do šířky zpětným chodem. U výchozího města X je zaznamenán jeho předchůdce při provedeném průchodu do šířky, což je vlastně jeho následník na hledané trase vozidla z X do Y, u něj je zaznamenán zase jeho předchůdce, atd., až se po zaznamenaných předchůdcích dostaneme do cílového města Y.

Uvedený postup je jistě konečný. V Dijkstrově algoritmu je v každém kroku jednomu vrcholu přiřazena trvalá hodnota. Výpočet tedy skončí nejvýše po N krocích, kde N je počet měst. V každém kroku se musí vyhledat město s maximální dočasnou hodnotou, což je výběr z N měst. Provede se při tom tudíž přibližně N operací. Dále se přepočítávají dočasné hodnoty všech sousedů vybraného vrcholu, kterých je méně než N. Celkem se tedy vykoná nejvýše počet operací úměrný N2. Při průchodu do šířky navštívíme a zařadíme do fronty každé z N měst nejvýše jednou a při jeho vyzvednutí z fronty musíme zpracovat jeho sousedy, kterých je méně než N. Celý průchod do šířky proto vyžaduje provést řádově nejvýše N2 operací. Vyhledání výsledné cesty zpětným chodem po předchůdcích je pak již triviální záležitostí a vykoná se v lineárním čase. Celkově má naše řešení úlohy kvadratickou časovou složitost.

program Tunely; {Dijkstrův algoritmus + průchod do šířky} const MaxN = 100; {maximální počet měst} var Vyska: array[1..MaxN, 1..MaxN] of integer; {uložení silnic mezi městy s max. výškami vozidel - "matice vzdáleností"} H: array[1..MaxN] of integer; {hodnoty měst} Docas: array[1..MaxN] of boolean; {dočasná hodnota pro Dijkstru} F: array[1..MaxN] of 1..MaxN; {fronta pro průchod do šířky} P: array[1..MaxN] of 1..MaxN; {předchůdci měst} N: 1..MaxN; {počet měst} X, Y: 1..MaxN; {výchozí a cílové město} Pruchod: boolean; {pokračovat v průchodu} V: integer; {možná výška vozidla} Z, K: 1..MaxN; {začátek a konec fronty v poli F} T: text; {vstupní data, výsledky} i,j: integer; begin {Načtení vstupních dat a inicializace polí:} assign(T, 'TUNELY.IN'); reset(T); readln(T, N, X, Y); {počet měst, výchozí a cílové město} for i:=1 to N do begin H[i] := 0; Docas[i] := true; for j:=1 to N do Vyska[i,j] := -1 {silnice i -> j neexistuje} end; readln(T, i, j, V); {silnice z města i do města j} while i <> 0 do {čtení vstupních dat = silnic} begin if (V = 0) or ((V > Vyska[i,j]) and (Vyska[i,j] <> 0)) then begin {zaznamenává se jen "lepší" silnice} Vyska[i,j]:=V; Vyska[j,i]:=V; {silnice je obousměrná} end; readln(T, i, j, V) {další silnice} end; close(T); {Dijkstrův algoritmus pro určení maximální výšky vozidla:} H[X] := maxint; {výchozí město bez omezení výšky} Pruchod := true; while Docas[Y] and Pruchod do begin j := Y; {hledáme město s maximální dočasnou hodnotou} for i:=1 to N do if Docas[i] and (H[i] > H[j]) then j := i; {vybran vrchol j} if H[j] = 0 then Pruchod:=false {město Y je nedostupné} else begin Docas[j] := false; {město j bude mít trvalou hodnotu} for i:=1 to N do if Docas[i] and (Vyska[j,i] >= 0) then {město i ma dočasnou hodnotu a existuje silnice z j do i} begin V := H[j]; {možná výška vozidla jedoucího trasou j -> i} if (Vyska[j,i] > 0) and (Vyska[j,i] < V) then V := Vyska[j,i]; {nutno snížit kvůli omezení silnice} if V > H[i] then H[i] := V; {zlepšení - projede sem vyšší vozidlo} end end end; V := H[Y]; {výsledná maximální výška vozidla} {Ošetření případu, že je cílové město nedostupné:} if not Pruchod then begin assign(T, 'TUNELY.OUT'); rewrite(T); writeln(T, -1); {cílové město není dostupné} close(T); exit end; {Průchod do šířky - určení nejkratší trasy vozidla výšky V mezi městy X a Y. Uvažují se pouze silnice bez omezení výšky vozidla nebo s omezením >= V. Průchod do šířky provádíme od Y k X, abychom pak při zpětném chodu získali přímo trasu z X do Y.} for i:= 1 to N do H[i] := 0; H[Y] := 1; {evidence, kde jsme již byli} Z := 1; K := 1; F[1] := Y; {ve frontě je jen Y} while H[X] = 0 do {dokud jsme nedošli do X} begin i := F[Z]; Z := Z+1; {vyzvednout z fronty} for j:= 1 to N do if H[j] = 0 then if (Vyska[i,j] = 0) or (Vyska[i,j] >= V) then begin H[j] := 1; P[j] := i; K := K+1; F[K] := j {vložit do fronty} end end; {Vypsání výsledku - zpětný chod po "předchůdcích":} assign(T,'TUNELY.OUT'); rewrite(T); if V = maxint then V := 0; {bez omezení výšky} writeln(T, V); {maximální výška vozidla} i := X; while i <> Y do begin write(T, i, ' '); i:=P[i] end; writeln(T, Y); close(T) end.

P-III-5 Zloděj

Úlohu budeme řešit metodou dynamického programování. Označme si hmotnosti předmětů po řadě v1, v2, ..., vN a jejich ceny c1, c2,..., cN. Nejprve se zaměříme pouze na stanovení výsledné optimální ceny vybraných předmětů. Označme Si,j pro i od 1 do N, j od 1 do M maximální cenu předmětů, které lze vybrat z prvních i předmětů tak, aby souhrnná hmotnost vybraných předmětů nepřevýšila j. Řešením úlohy pak bude zřejmě údaj SN,M. Hodnoty Si,j budeme počítat postupně pro i rostoucí od 1 do N. Pro každé takové i vždy stanovíme Si,j pro všechna j od 1 do M. Čísla S1,j spočítáme snadno, první předmět můžeme vzít právě tehdy, když jeho hmotnost nepřekročí j. Bude tedy:
S1,j = 0 pokud v1 > j
S1,j = c1 pokud v1 <= j
Pro i > 1 dokážeme určit hodnoty Si,j na základě dříve spočtených hodnot Si-1,j. Jestliže hmotnost i-tého předmětu převyšuje mez j, nemůžeme ho použít ve výběru a tedy Si-1,j = Si,j. V opačném případě sice i-tý předmět lze vybrat, ale musíme ještě uvážit, zda se nám to vyplatí. Musíme tedy porovnat výslednou cenu výběru při použití a bez použití i-tého předmětu a z obou možností zvolit tu lepší. Použijeme-li i-tý předmět, pak Si,j bude rovno součtu ceny i-tého předmětu a nejvyšší možné ceny, které lze dosáhnout pomocí prvních i-1 předmětů vybraných tak, aby jejich celková hmotnost nepřesáhla hodnotu k=j-vi. Pokud se rozhodneme i-tý předmět nepoužít, bude jistě Si-1,j = Si,j. Z obou uvažovaných hodnot vybereme maximum:
Si,j = Si-1,j pokud vi > j
Si,j = max(ci + Si-1,k, Si-1,j), kde k=j-vi, pokud vi <= j

V programové realizaci popsaného postupu bychom mohli použít dvourozměrné pole S velikosti N x M a vyplňovat ho postupně po řádcích. Vzhledem k povolenému rozsahu hodnot N, M je však použití tak velkého pole nereálné a navíc ho stejně ani nepotřebujeme. Z odvozených vzorců je zřejmé, že k určení hodnot na i-tém řádku nám stačí znát hodnoty na předchozím i-1 řádku, nikdy se nepotřebujeme vracet ke starším údajům. Vystačíme proto s jedním jednorozměrným polem S o M prvcích, které bude postupně představovat jednotlivé řádky výše uvažované matice. Hodnoty uložené v poli S budou tedy představovat optimální ceny výběru předmětů pro jednotlivé váhové limity. Přitom v i-tém kroku smíme vybírat z prvních i předmětů. Je důležité přepočítávat hodnoty v poli S ve správném pořadí "zprava doleva", tzn. od vyšších váhových limitů k nižším, abychom při určování ceny Si,j měli ještě k dispozici nezměněné údaje Si-1,x pro x < j.

Po N průchodech polem velikosti M získáme výslednou optimální cenu výběru ze všech předmětů. Bude uložena v posledním, tzn. M-tém prvku pole S. Časová složitost výpočtu je tedy O(NM).

Popsané řešení musíme nyní rozšířit o určení, jak nejvýhodnější výběr předmětů vypadá, tzn. které předměty do něj patří, navíc s ohledem na požadovanou minimální hmotnost z více možných výběrů téže maximální ceny. Pro každý váhový limit od 1 do M si budeme muset udržovat nejen jako dosud údaj o prozatím nejvyšší ceně dosažitelné pomocí prvních i předmětů, ale také informaci o hmotnosti uvažovaného výběru (nejnižší možné v případě více možností) a seznam předmětů tvořících tento výběr. Při každé změně některé dílčí ceny patřičně upravíme i odpovídající seznam vybraných předmětů. K uložení hmotností jednotlivých výběrů použijeme jednorozměrné pole H o M prvcích. Pokud bychom si složení výběrů ukládali jednoduše ve formě seznamů čísel předmětů, potřebovali bychom mít uloženo v paměti M seznamů po nejvýše N číslech, tzn. prostor pro N.M čísel předmětů. Vzhledem ke stanovaným maximálním hodnotám N <= 250, M <= 10000 to je dva a půl miliónu čísel, což je nereálný paměťový požadavek. Paměťově úspornějšího uložení potřebných informací dosáhneme pomocí bitových polí. I tak budeme potřebovat uchovávat v paměti počítače M údajů, každý o velikosti N bitů, tzn. celkem NM bitů. Pro stanovené mezní hodnoty N a M to znamená asi 340 kB paměti, což již lze bez problémů realizovat (např. v Turbo Pascalu ovšem jen v dynamicky alokované paměti, jak ukazuje následující program).

program Zlodej; {dynamické programování} const MaxN = 250; {maximální počet předmětů} MaxM = 10000; {max. hmotnostní limit výběru} var N: word; {počet předmětů} M: word; {hmotnostní limit výběru} V: array[1..MaxN] of word; {hmotnosti předmětů} C: array[1..MaxN] of word; {ceny předmětů} S: array[0..MaxM] of longint; {nejvyšší možné ceny výběru pro různé hmotnostní limity} H: array[0..MaxM] of word; {nejnižší možné hmotnosti výběru při maximální ceně S[i] pro různé hmotnostní limity} const VelPoleMnozin = 2000; {maximální velikost pole množin} MaxPoliMnozin = (MaxM-1) div VelPoleMnozin +1; {max. potřebný počet polí množin} type PoleMnozin = array[1..VelPoleMnozin] of set of 1..MaxN; var P: array[1..MaxPoliMnozin] of ^PoleMnozin; {uložení výběru předmětů} W: byte; {skutečný počet polí množin} var T: text; {vstupní data, výsledky} Z: longint; {možnost zlepšení ceny} I, J, J1, J2, K, K1, K2: word; begin {Načtení vstupních dat:} assign(T,'ZLODEJ.IN'); reset(T); readln(T,N,M); for I:=1 to N do readln(T, V[I], C[I]); close(T); {Inicializace datových struktur:} for J:=0 to M do begin S[J]:=0; H[J]:=0 end; {výběry jsou zatím prázdné} W:=(M-1) div VelPoleMnozin +1; {potřebný počet polí množin} for J1:=1 to W do begin new(P[J1]); for J2:=1 to VelPoleMnozin do P[J1]^[J2]:=[]; end; {Vlastní výpočet:} for I:=1 to N do {bereme postupně předměty} for J:=M downto 1 do {výběry od největšího!} if V[I] <= J then {I-tý předmět se vejde} begin K:=J-V[I]; {zbytek "kapacity" po I-tém} Z:=C[I] + S[K]; {Z teď udává nejlepší možnou cenu J-tého výběru, pokud I-tý předmět opravdu vezmeme} if Z > S[J] then {vyplatí se I-tý předmět vzít} begin S[J]:=Z; {zvýšit cenu J-tého výběru} H[J]:=V[I] + H[K]; {nová hmotnost J-tého výběru} {pro aktualizaci složení J-tého výběru potřebujeme rozložit indexy J, K do složek na adresování v P:} J1:=(J-1) div VelPoleMnozin +1; J2:=(J-1) mod VelPoleMnozin +1; if K > 0 then begin K1:=(K-1) div VelPoleMnozin +1; K2:=(K-1) mod VelPoleMnozin +1; P[J1]^[J2]:=[I] + P[K1]^[K2] end else P[J1]^[J2]:=[I] {nové složení J-tého výběru} end else if Z = S[J] then {rozhodujeme jen podle hmotnosti} if V[I] + H[K] < H[J] then begin {vezmeme I-tý předmět, cena výběru se tím nezmění, ale celková hmotnost vybraných předmětů se sníží} H[J]:=V[I] + H[K]; {nová hmotnost J-tého výběru} J1:=(J-1) div VelPoleMnozin +1; J2:=(J-1) mod VelPoleMnozin +1; if K > 0 then begin K1:=(K-1) div VelPoleMnozin +1; K2:=(K-1) mod VelPoleMnozin +1; P[J1]^[J2]:=[I] + P[K1]^[K2] end else P[J1]^[J2]:=[I] {nové složení J-tého výběru} end end; {Výpis výsledků:} assign(T,'ZLODEJ.OUT'); rewrite(T); writeln(T, H[M], ' ', S[M]); for I:=1 to N do if I in P[W]^[(M-1) mod VelPoleMnozin +1] then write(T,I,' '); close(T); end.