h1(#drum8). 'Soluţia':algoritmiada-2022/runda-2/solutii/drum8 problemei 'Drum8':problema/drum8

h1(#drum8). 'Soluţia':algoritmiada-2022/runda-2/solutii/drum8 problemei 'Drum8':problema/drum8
 
Fie $i$ indicele poziţiei la care am ajuns în vectorul $A$ şi $j$ indicele poziţiei la care am ajuns în vectorul $B$. O deplasare în jos este echivalentă cu a incrementa valoarea lui $i$, iar o deplasare la dreapta este echivalentă cu a incrementa valoarea lui $j$.
 
h4. Cazul $1$: $0 ≤ A[i], B[i] ≤ 1$
 
Incrementăm valorile lui $i$ şi $j$ până când $A[i] > 0$ şi $B[j] > 0$. Acum incrementăm $i$ până ajungem la ultima valoare egală cu $1$ din vectorul $A$. Apoi incrementăm $j$ până ajungem la ultima valoare egală cu $1$ din vectorul $B$. După nu mai este relevantă ordinea în care incrementăm pointerii deoarece $A[i] * B[j] = 0$, deci nu contribuie cu nimic la sumă.
 
h4. Cazul $2$: $0 ≤ A[i], B[i] ≤ 2$
 
Incrementăm valorile lui $i$ şi $j$ până când $A[i] > 0$ şi $B[j] > 0$. Fie $x$ numărul de valori de $1$ până la primul $2$ din vectorul A şi $y$ numărul de valori de $2$ din vectorul $B$. Dacă $x < y$, incrementăm $i$ până ajungem la primul $2$, apoi incrementăm $j$ până la ultimul $2$ din vectorul $B$, iar apoi incrementăm iar $i$ până la ultimul $2$ din vectorul $A$. Pentru $x > y$, incrementăm în ordine inversă. Acum $i$ şi $j$ pointează spre ultimele valori egale cu $2$ din $A$, respectiv $B$. Dacă numărul de valori egale cu $1$ care au ramas în vectorul $A$ este mai mare decât numărul de valori din vectorul $B$, incrementăm $j$ până la ultima valoare egala cu $1$, iar apoi $i$ până la ultima valoare egală cu $1$. Analog pentru celălalt caz. Apoi este irelevantă ordinea în care incrementăm pointerii, deci afişăm traseul minim lexicografic.

private

protected