Problema se rezolva prin programare dinamica. Fie {$D{~i, x3, x5~}$} valoarea maxim posibila pentru exponentul lui $2$ care se poate obtine din primele $i$ fractii, astfel incat exponentul lui $3$ sa fie $x3$ si exponentul lui $5$ sa fie {$x5$}. Tabloul {$D$} poate contine si indici negativi! Relatia de recurenta este urmatoarea:
{$D{~i, x3, x5~}$} = maxim({$D{~i-1, x3, x5~}, x2' + D{~i-1, x3-x3', x5-x5'~}$}), unde {$(x2' x3' x5')$} este tripletul asociat celei de a {$i$}-a fractii.
Din considerente de memorie nu vom retine tot tabloul {$D$}. Deoarece elementele de pe pozitii de forma ({$i, a, b$}) depind doar de elemente de pe pozitii de forma ({$i, a', b'$}) vom retine o singura matrice in locul unui tablou tridimensional si vom actualiza elementele din aceasta matrice printr-o parcurgere convenabila a indicilor.
Dupa ce avem tabloul $D$ construit, aflam maxim({$2^D{~N, x3, x5~}^ * 3^x3^ * 5^x5^$}), cu $x3 ≥ 0$ si {$x5 ≥ 0$}. Pentru a compara doua numere $2^x1^ * 3^y1^ * 5^z1^$ si $2^x2^ * 3^y2^ * 5^z2^$ vom logaritma si vom compara {$x1*ln2 + y1*ln3 + z1*ln5$} cu {$x2*ln2 + y2*ln3 + z2*ln5$}. Atunci cand am aflat o solutie optima, este necesara implementarea operatiilor pe numere mari, deoarece rezultatul nu se incadreaza in nici un tip de date conventional.
Din considerente de memorie nu vom retine tot tabloul {$D$}. Deoarece elementele de pe pozitii de forma ({$i, a, b$}) depind doar de elemente de pe pozitii de forma ({$i-1, a', b'$}) vom retine o singura matrice in locul unui tablou tridimensional si vom actualiza elementele din aceasta matrice printr-o parcurgere convenabila a indicilor.
Dupa ce avem tabloul $D$ construit, aflam maxim({$2^D{~N,x3,x5~}^ * 3^x3^ * 5^x5^$}), cu $x3 ≥ 0$ si {$x5 ≥ 0$}. Pentru a compara doua numere $2^x1^ * 3^y1^ * 5^z1^$ si $2^x2^ * 3^y2^ * 5^z2^$ vom logaritma si vom compara {$x1*ln2 + y1*ln3 + z1*ln5$} cu {$x2*ln2 + y2*ln3 + z2*ln5$}. Atunci cand am aflat o solutie optima, este necesara implementarea operatiilor pe numere mari, deoarece rezultatul nu se incadreaza in nici un tip de date conventional.
Complexitatea problemei este {$O(N^3^)$} de constanta {$4*(log{~3~}MAX)*(log{~5~}MAX)$}, unde {$MAX = 400.000.000$}. Aceasta solutie obtine 100 de puncte.
h2(#tunel). 'Tunelul groazei':problema/tunel
