h1. 'Soluţia':incalzire2020/solutii/teste problemei 'Teste':problema/teste

h1(#teste). 'Soluţia':incalzire2020/solutii/teste problemei 'Teste':problema/teste

h3. 20 de puncte $(O(n^k)+O(sqrt(S)))$

Pentru a reuşi să obţinem un algoritm a cărui complexitate nu depinde de $S$, trebuie să exprimăm $S$ într-un mod mai simplu. Pentru a găsi o soluţie începem prin a fixa o valoare pe o poziţie şi a vedea în câte şiruri apare, la $S$ adăugandu-se produsul între valoare şi număr de apariţii. Dacă fixăm numărul de pe poziţia $poz$ ca fiind $val$, şirul
va arăta astfel:
Pozitie $|1 2.. poz ... n|$

Valoare $|? ?.. val ... $n|$
Observam ca numarul de siruri in care $val$ apare pe pozitia poz este numarul de moduri de a inlocui $n-1$ caractere $?$ cu numere de la $1$ pana la $k$. Acest numar este egal cu $k^(n-1)$. Daca fixam doar pozitia $poz$ si facem suma pentru toate numerele $val$ de la $1$ la $k$, vom obitne $k^(n-1)*k*(k+1)/2$. Deoarece expresia este aceeasi indiferent oricare din cele $n$ pozitii va fi $poz$, $S$ va fi n*(k^(n-1)*k*(k+1)/2).

Valoare $|? ?.. val ... ?|$
Observam ca numarul de siruri in care $val$ apare pe pozitia poz este numarul de moduri de a inlocui $n-1$ caractere $?$ cu numere de la $1$ pana la $k$. Acest numar este egal cu $k^(n-1)$. Daca fixam doar pozitia $poz$ si facem suma pentru toate numerele $val$ de la $1$ la $k$, vom obitne $k^(n-1)*k*(k+1)/2$. Deoarece expresia este aceeasi indiferent oricare din cele $n$ pozitii va fi $poz$, $S$ va fi $n*(k^(n-1)*k*(k+1)/2)$.

Observăm ca în formula anterioara apar doar puteri ale lui $n$, $k$ şi $k+1$ (şi $2$, pe care trebuie să îl reducem de unde este posibil), deci putem precalcula factorii primi ai acestora, şi observând la ce puteri apar cele 3 numere în formula pentru $S$, putem obţine factorizarea lui $S$ "combinând" cele 3 factorizări. Răspunsul va fi produsul puterilor (la care se adauga $1$) la care apar factorii primi ai lui $S$ în factorizarea lui.

private

protected