Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2015-02-22 10:14:18.
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 cele N numere
dp[i]1 = numarul de submultimi cu suma numerelor impara cu cele N numere
Cazul de baza:
dp0[0] = 1 (submultimea vida)
dp0[1] = 0
Relatia de recurenta:
Daca numarul v[i] este par:
dp[i]0 = 2 * dp[i-1]0
dp[i]1 = 2 * dp[i-1]1
Daca numarul v[i] este impar:
dp[i]0 = dp[i]0 + dp[i]1
dp[i]1 = dp[i]0 + dp[i]1
Complexitate: 
