h3. Solutie de complexitate $O(N^3^)$

Pe fiecare muchie a grafului $(i,j)$ se pune o distanta egala cu valoarea $A[i][j]$ ({$A$} fiind matricea data). Se aplica apoi algoritmul 'Roy-Floyd':http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm pe acest graf, iar matricea distantelor obtinuta trebuie sa fie identica cu matricea distantelor data (in caz contrar neexistand solutie).

Pe fiecare muchie a grafului $(i,j)$ se pune o distanta egala cu valoarea $A[i][j]$ ($A$ fiind matricea data). Se aplica apoi algoritmul 'Roy-Floyd':http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm pe acest graf, iar matricea distantelor obtinuta trebuie sa fie identica cu matricea distantelor data (in caz contrar neexistand solutie).

h3. Probleme asemanatoare

Problema cere determinarea radicalului de ordin $P$ dintr-un numar mare. Exista mai multe metode de realiza acest lucru, dintre care voi mentiona doua:

* Determinarea radicalului de ordin $P$ cifra cu cifra: Se determina intai numarul de cifre ale numarului (se incadreaza radicalul intre un {$10^x^$ si $10^x+1^$}), apoi se determina, pe rand, fiecare cifra a rezultatului; pentru fiecare pozitie, se incearca, pe rand, toate cifrele de la $0$ la $9$ si ne oprim la ultima cifra pentru care numarul ridicat la puterea $P$ (considerand ca cifrele de dupa cifra curenta sunt egale cu $0$), nu depaseste $N$-ul dat. Eventual, cifra curenta se poate cauta binar (poate fi util daca rezultatul este tinut intr-o baza mai mare decat $10$).

* Determinarea radicalului de ordin $P$ cifra cu cifra: Se determina intai numarul de cifre ale numarului (se incadreaza radicalul intre un $10^x^$ si $10^x+1^), apoi se determina, pe rand, fiecare cifra a rezultatului; pentru fiecare pozitie, se incearca, pe rand, toate cifrele de la $0$ la $9$ si ne oprim la ultima cifra pentru care numarul ridicat la puterea $P$ (considerand ca cifrele de dupa cifra curenta sunt egale cu {$0$}), nu depaseste $N$-ul dat. Eventual, cifra curenta se poate cauta binar (poate fi util daca rezultatul este tinut intr-o baza mai mare decat {$10$}).

* Cautarea binara a rezultatului, intre o limita inferioara si o limita superioara. Numarul fixat in cadrul cautarii binare se ridica la puterea $P$ si daca depaseste $N$-ul dat, se pastreaza jumatatea inferioara a intervalului de cautare; in caz contrar, se pastreaza jumatatea superioara a intervalului.
Pe langa alegerea uneia dintre cele $2$ metode, sunt necesare cateva optimizari suplimentare, precum:

* $nrbiti = 3$
* $for i = N -> 1$

** $daca num[i-1, nrbiti] >= M atunci$
*** $bitul i este 0$
** $altfel$
*** $bitul i este 1$
*** $M = M - num[i-1, nrbiti]$
*** $nrbiti = nrbiti - 1$

** daca num[i-1, nrbiti] >= M atunci$
*** $bitul i este 0$$
** altfel
*** bitul i este 1
*** M = M - num[i-1, nrbiti]
*** nrbiti = nrbiti - 1

h3. Probleme asemanatoare