Lista de probleme 2

Johnie a început să se joace cu un vector de numere. El dispune iniţial de un vector V cu N numere întregi (numerotate de la 0 la N - 1) şi poate efectua următoarele operaţii:

• schimbarea elementului de pe poziţia p cu un alt număr întreg;
• aflarea subsecvenţei de sumă maximă din V inclusă între indicii a şi b;

Considerăm trei numere naturale nenule: n, k şi x. Denumim o kx-descompunere a numărului n o posibilitate de a scrie numărul n ca sumă de k numere naturale nenule astfel încât diferenţa între oricare doi termeni ai sumei este cel puţin egală cu x. Fiind date trei numere naturale n, k şi x, să se determine câte kx-descompuneri distincte există. Două kx-descompuneri sunt distincte dacă diferă prin cel puţin un termen.