Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2015-02-22 10:42:55.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
Soluţii ONIS 2015, Runda 1
- Lista de probleme
- Por Costel şi Azerah
- Por Costel şi Algoritmul
- Por Costel şi Bujor
- Por Costel şi Comisia de Cenzură
- Por Costel şi Cifrul
- Por Costel şi Invazia Extraterestră
- Por Costel şi Livada
- Por Costel şi Meciul
- Por Costel şi Perechile
- Por Costel şi Pinball
- Por Costel şi Semipalindroamele
Por Costel şi Azerah
Solutia cea mai la indemana la problema aceasta se bazeaza pe metoda programarii dinamice:
Calculam:
dp[i][0] = numarul de submultimi cu suma numerelor para cu primele i numere din sirdp[i][1] = numarul de submultimi cu suma numerelor impara cu primele i numere din sir
Cazul de baza:
dp[0][0] = 1 (submultimea vida)dp[0][1] = 0
Relatia de recurenta:
Daca numarul v[i] este par:dp[i][0] = 2 * dp[i-1][1]dp[i][1] = 2 * dp[i-1][1]
Daca numarul v[i] este impar:dp[i][0] = dp[i-1][0] + dp[i-1][1]dp[i][1] = dp[i-1][0] + dp[i-1][1]
Complexitate: 
Insa, la o inspectie mai amanuntita a dinamicii sau dupa un rationament combinatoric descoperim ca:
* Daca exista cel putin un numar impar in sir raspunsul este 2n-1
* Altfel este 2n
Acum, daca ignoram citirea sirului, complexitatea este 
