Ř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:
- Určíme město s maximální dočasnou hodnotou H.
- Dočasnou hodnotu tohoto města prohlásíme za trvalou.
- 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ě v
1, v
2, ...,
v
N a
jejich ceny c
1,
c
2,..., c
N.
Nejprve se zaměříme pouze na stanovení výsledné
optimální ceny vybraných předmětů. Označme S
i,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 S
N,M. Hodnoty
S
i,j budeme počítat postupně pro i rostoucí od 1 do N. Pro každé
takové i vždy stanovíme S
i,j pro všechna j od 1 do M.
Čísla S
1,j
spočítáme snadno, první předmět můžeme vzít právě tehdy, když
jeho hmotnost nepřekročí j. Bude tedy:
S
1,j = 0 pokud v
1 > j
S
1,j = c
1 pokud v
1 <= j
Pro i > 1 dokážeme určit hodnoty S
i,j na základě dříve spočtených
hodnot S
i-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 S
i-1,j = S
i,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 S
i,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-v
i. Pokud se rozhodneme
i-tý předmět nepoužít, bude jistě S
i-1,j = S
i,j.
Z obou
uvažovaných hodnot vybereme maximum:
S
i,j = S
i-1,j pokud v
i > j
S
i,j = max(c
i + S
i-1,k,
S
i-1,j),
kde k=j-v
i, pokud v
i <= 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.