Diferente pentru happy-coding-2007/solutii intre reviziile #50 si #54

Nu exista diferente intre titluri.

Diferente intre continut:

h3. Solutia 2
Vom incerca sa calculam valorile $pmin[i]$ treptat. Vom parcurge pozitiile de la $1$ la $N$ si vom incerca sa incepem un palindrom avand centrul in pozitia $i$ (pentru cazul unui palindrom de lungime impara), respectiv avand centrul la pozitiile $i$ si $i+1$ (pentru cazul unui palindrom de lungime para). Ideea importanta este ca, atunci cand ajungem la pozitia $i$, toate valorile $pmin[j]$, cu $j < i$ au fost calculate, iar valorile $pmin[k]$, $k > i$, au niste valori partiale (adica valorile calculate nu sunt inca finale, ele mai putand sa scada ulterior). Vom extinde treptat cat putem de mult un palindrom in jurul pozitiei $i$ (respectiv pozitiilor $i$ si {$i+1$}); la fiecare pas de extindere, vom incerca sa incrementam palindromul de la lungimea curenta $L$, la lungimea $L+2$ (pentru aceasta verificam caracterele din capatele palindromului); inainte de a realiza extinderea, vom incerca sa folosim palindromul curent in cadrul unei solutii - mai exact, vom avea posibilitatea ca valoarea $pmin[i-(L+1)/2]+1$ sa fie folosita pentru a micsora valoarea lui $pmin[i+(L+1)/2-1]$ (pentru cazul lungimii impare), respectiv valoarea $pmin[i-L/2]+1$ poate fi folosita pentru a micsora valoarea lui $pmin[i+L/2]$ (pentru cazul lungimii pare).
Vom incerca sa calculam valorile $pmin[i]$ treptat. Vom parcurge pozitiile de la $1$ la $N$ si vom incerca sa incepem un palindrom avand centrul in pozitia $i$ (pentru cazul unui palindrom de lungime impara), respectiv avand centrul la pozitiile $i$ si $i+1$ (pentru cazul unui palindrom de lungime para). Ideea importanta este ca, atunci cand ajungem la pozitia $i$, toate valorile $pmin[j]$, cu $j < i$ au fost calculate, iar valorile $pmin[k]$, $k > i$, au niste valori partiale (adica valorile calculate nu sunt inca finale, ele mai putand sa scada ulterior). Vom extinde treptat cat putem de mult un palindrom in jurul pozitiei $i$ (respectiv pozitiilor $i$ si {$i+1$}); la fiecare pas de extindere, vom incrementa palindromul de la lungimea curenta $L$, la lungimea $L+2$ (pentru aceasta verificam caracterele din capatele palindromului); inainte de a realiza extinderea, vom incerca sa folosim palindromul curent in cadrul unei solutii - mai exact, vom avea posibilitatea ca valoarea $pmin[i-(L+1)/2]+1$ sa fie folosita pentru a micsora valoarea lui $pmin[i+(L+1)/2-1]$ (pentru cazul lungimii impare), respectiv valoarea $pmin[i-L/2]+1$ poate fi folosita pentru a micsora valoarea lui $pmin[i+L/2]$ (pentru cazul lungimii pare).
Complexitatea ambelor solutii este $O(N^2^)$, insa a doua solutie merge mai repede, in practica, deoarece ia in considerare numai palindroamele valide (care pot fi cel mult {$O(N^2^)$}).
==code(c) |
cmin[ 0 ] = 0
pentru i de la 1 la N
cmin[i]=infinit
pentru j de la 1 la i
  cost_total = cmin[j-1] + F[j] + C[j] * D[j]
  cost_stocare=S[j]
  pentru k de la j+1 la i
    cost_total = cost_total + (C[j]+cost_stocare) * D[k]
    cost_stocare = cost_stocare + S[k]
  daca cost_total < cmin[i] atunci
    cmin[i]=cost_total
  cmin[i]=infinit
  pentru j de la 1 la i
    cost_total = cmin[j-1] + F[j] + C[j] * D[j]
    cost_stocare=S[j]
    pentru k de la j+1 la i
      cost_total = cost_total + (C[j]+cost_stocare) * D[k]
      cost_stocare = cost_stocare + S[k]
    daca cost_total < cmin[i] atunci
      cmin[i]=cost_total
==
	Se variaza valoarea lui $i$ de la $1$ la $N$ si pentru fiecare valoare incercam sa calculam $cmin[i]$. Pentru aceasta, incercam toate valorile $j &le; i$ care pot reprezenta luna in care sunt produse kilogramele de cascaval necesare in luna $i$. Apoi calculam costul total pentru cazul in care luna $j$ produce cantitatea de cascaval necesara pentru a satisface cererile din lunile $j, j+1, .., i$. In cele din urma vom avea in $cmin[i]$ minimul dintre costurile corespunzatoare fiecarei variante de alegere a lunii $j$. Costul total minim pentru toate cele $N$ luni il avem in $cmin[N]$. Bineinteles, aceasta solutie nu se incadreaza in limita de timp.
  pentru j de la i la 1
    cost_stocare = cost_stocare + S[j] * dtotal
    dtotal = dtotal + D[j]
    cost_productie = F[j] + C[j]    dtotal
    cost_productie = F[j] + C[j] * dtotal
    cost_total = cmin[j-1] + cost_productie + cost_stocare
    daca cost_total < cmin[i] atunci
      cmin[i]=cost_total
h2(#biti3). 'Biti3':problema/biti3
Vom considera bitii fiecarui sir numerotati de la $N$ la $1$ (de la stanga la dreapta) si vom calcula $num[i, j]$ = numarul de siruri de $i$ biti, continand exact $j$ biti de $1$. $num[i, 0] = 1$. Pentru $j &gt; i$, avem $num[i, j] = 0$ ; altfel, $num[i, j] = num[i-1, j] + num[i, j-1]$ (cele $2$ variante corespund deciziei de a plasa un bit de $0$ pe pozitia $i$, caz in care pe pozitiile $1,..,i-1$ se afla $j$ biti de $1$, respectiv un bit de $1$ pe pozitia $i$, caz in care pe pozitiile $1,..,i-1$ se mai afla doar $j-1$ biti de $1$). Alt mod de a calcula aceste valori este urmatorul: $num[i,j] = Combinari de i luate cate j$.
Vom considera bitii fiecarui sir numerotati de la $N$ la $1$ (de la stanga la dreapta) si vom calcula $num[i, j]$ = numarul de siruri de $i$ biti, continand exact $j$ biti de $1$. $num[i, 0] = 1$. Pentru $j &gt; i$, avem $num[i, j] = 0$ ; altfel, $num[i, j] = num[i-1, j] + num[i-1, j-1]$ (cele $2$ variante corespund deciziei de a plasa un bit de $0$ pe pozitia $i$, caz in care pe pozitiile $1,..,i-1$ se afla $j$ biti de $1$, respectiv un bit de $1$ pe pozitia $i$, caz in care pe pozitiile $1,..,i-1$ se mai afla doar $j-1$ biti de $1$). Alt mod de a calcula aceste valori este urmatorul: $num[i,j] = Combinari de i luate cate j$.
Folosind aceste valori, vom determina bitii celui de-al $M$-lea sir, unul cate unul, pornind de la al $N$-lea bit. La fiecare pas, va trebui sa determinam cate siruri incep cu bitul $0$ si cate siruri incep cu bitul $1$. La inceput, vor exista $num[N-1,3]$ siruri care incep cu bitul $0$ si $num[N-1,2]$ siruri care incep cu bitul $1$. Este evident ca, la un anumit pas, toate sirurile care incep cu $0$ se vor afla inaintea tuturor sirurilor care incep cu $1$. De aceea, daca $M$ &lt; numarul sirurilor care incep cu $0$, bitul respectiv va fi $0$; in caz contrar, bitul va fi $1$. Daca bitul este $1$, inainte de a trece la pasul urmator, va trebui sa actualizam valoarea lui $M$, in asa fel incat sa sarim peste toate sirurile care incep cu $0$ ({$M = M - numarul de siruri care incep cu 0$}), precum si sa tinem cont de faptul ca am mai consumat inca un bit de $1$. Algoritmul in pseudocod este urmatorul:

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.