

			INMULTIRI
		       ------------

	Pentru un n dat sa se determine numarul minim de inmultiri cu care se poate calcula a^n.
	Fisierul de intrare IN.TXT contine, pe cate o linie, valori ale lui n.

SOLUTIE:
--------
1)
	Problema revine la generarea lungimii minime a lanturilor aditive pt. n care reprezinta
un sir de intregi 1=a0,a1,...,ar=n cu propietatea ca exista j, k<=j<i, a(i)=a(j)+a(k), oricare
i=1,2,..,r. Un lant aditiv se numeste "lant stea" daca a(i)=a(i-1)+a(k), k<=i-1, oricare i=1,..,r.
Daca se noteaza cu l(n) lungimea minima a lanturilor aditive pt. n, si cu l*(n) lungimea lanturilor
aditive de tip stea pt. n, are loc proprietatea l(n)<=l*(n). Cercetarile in acest domeniu arata
ca prima valoare a lui n pt. care l(n)<l*(n) este n=12509. Pt. valori mai mici se poate inlocui
problema determinarii lui l(n) cu aceea mai simpla de stabilire a lui l*(n).
	O metoda eleganta si rapida de determinare a acestei valori este construirea asa-numitului
arbore de puteri care are in radacina valoarea 1, pe nivelul urmator valoarea 2=1+1 si apoi
toate valorile a(i) care se pot calcula de pe fiecare ramura:
1=a0,a1,a2,..,ar=n. Pt. a nu pierde solutii, o aceeasi valoare se va pastra in toate pozitiile
unde ea poate fi calculata pe un anumit nivel din arbore. Nu se vor mai pastra insa valorile si-
tuate pe nivele mai mari decat cele corespunzatoare primelor aparitii. Valoarea lui l*(n) va fi
numarul nivelului pe care apare prima data n.

2) (propusa de mine)
A[k] = nr. de inmultiri pt. a obtine a^k.
A[0]=0;
A[1]=0;

A[k]=1+min(A[p]+a[k-p]), p=1,..,k-1.