Problemă

[•TheNechiz]

Fie n și k două numere naturale. Definim m(k) = numărul minim de înmulțiri
pentru a obține nk. Spre exemplu, pentru k =15, avem m(15) = 5, întrucât:
n * n = n^2
n^2 * n = n^3
n^3 * n^3 = n^6
n^6 * n^6 = n^12
n^12 * n^3 = n^15
Scrieți un program în C care calculează m(1) + m(2) + .... + m(200).

Am nevoie doar de o idee de rezolvare ? De un hint, de orice m-ar putea ajuta să-mi dau seama cum aș putea rezolva problema...

[•klamathix]

Din câte știu eu nu există soluție polinomială la problema asta. https://en.wikipedia.org/wiki/Addition-chain_exponentiation.

Unde ai găsit enunțul?

[•PlayLikeNeverB4]

S-a dat o problema asemanatoare la nationala ACM din 2013: http://acm.tju.edu.cn/toj/vcontest/showp9268_C.html

Poate te ajuta acea solutie http://www.infoarena.ro/blog/acm-2013-etapa-nationala-partea-ii

[•klamathix]

Cel puțin în cazul în care ai doar adunări, soluția aia e corectă doar fiindcă n e mic.. http://stackoverflow.com/a/15856054

Să tot vedem în concurs probleme deschise care ies banal (by pure chance) pe cazuri mici. Quality stuff.

[•TheNechiz]

Din câte știu eu nu există soluție polinomială la problema asta. https://en.wikipedia.org/wiki/Addition-chain_exponentiation.

Unde ai găsit enunțul?

E temă de laborator... și am încercat s-o rezolv cu programare dinamică, am căutat o formulă, apoi nu am mai avut idei.