Compress

Solutie O(N)

Se parcurge sirul pas cu pas. Cat timp caracterul curent este identic cu cel anterior incrementam un contor k. Daca este diferit de cel anterior, il afisam pe cel anterior, apoi pe k si reinitializam pe k cu 1.

Fragment de cod:

citire(S);

int k =0;
int len = strlen(S);
	
for(int i=0;i<len;i=j)
{
	k = 1;
	
	while(S[i] == S[i+k]) k++;
	afisare(S[i],k);
}

Filme

Solutie O(NlogN)

Pentru fiecare film se retine valoarea v[ i ] = d[ i ] + t[ i ]. Se sorteaza vectorul v crescator . Se aleg primele k filme , unde k este cel mai mare numar pentru care v[ 1 ] + v[ 2 ] + ... + v[ k ] <= m.

Fragment de cod:

citire();

sort(v.begin(),v.end());

int k;

for(k=1;m-v[k] >= 0 && k<=N;k++)
	m = m - v[k];

--k;

Intervale2

Solutie O(N*log2N)

Vom considera o structura de date B de tip vector in care vom avea:

B[x].i - indicele din vectorul A si P al elementului de pe pozitia x din vectorul B.
B[x].pi=P[ B[x].i ]
B[x].a=A[ B[x].i ]

Vom sorta vectorul B descrescator dupa B[x].a si vom parcurge vectorul sortat. Vom retine in vectorul ANS raspunsul pentru fiecare pozitie. Folosind un arbore indexat binar vom afla cate numere mai mari decat B[x].a sunt intre B[x].i si B[x].pi, raspuns pe care il vom memora in vectorul ANS[ B[x].i ] . Apoi vom actualiza in arborele indexat binar pozitia B[x].i ca fiind ocupata.

In cele din urma vom afisa vectorul ANS.

Radacina

Se poate utiliza un algoritm de cautare binara, deoarece polinomul este o functie continua. Astfel daca intr-un moment cautam solutia in intervalul [a,b], si consideram m=(a+b)/2 . Daca ( 0≤P(a) si P(m)≤0 ) sau ( P(a)≤0 si 0≤P(m) ) inseamna ca solutia se afla in intervalul [a,m]. In caz contrar solutia se afla in intervalul [m,b]. Vom initializa pe a=-20 si b=20. Mai multe detalii puteti gasi pe wikipedia .