Fişierul intrare/ieşire: | pdm.in, pdm.out | Sursă | ad-hoc |
Autor | Din Folclor | Adăugată de | |
Timp execuţie pe test | 1.5 sec | Limită de memorie | 16384 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Pdm
Se dă un produs matricial M = M1M2...Mn. În înmulţirea matricelor, se înmulţeşte fiecare linie din prima matrice cu fiecare coloană din a 2 - a matrice. Pentru ca această operaţie să fie posibilă, matricele trebuie să aibă o latură comună. Spre exemplu, prima matrice are a linii şi b coloane, iar ce-a de a 2 - a are b linii şi c coloane, iar matricea rezultată va avea a linii şi c coloane. Numărul de înmulţiri elementare a celor 2 matrici de mai sus este a *b *c. Cum înmulţirea matricelor este asociativă, toate parantezările conduc la acelaşi rezultat. Însă, numărul total de înmulţiri scalare al produsului matricial poate să difere substanţial în funcţie de ordinea efectuării calculelor, ordine dată de paranteze. Dimensiunile celor n matrici se dau sub forma unui şir d astfel încât perechea (di-1, di) reprezintă dimensiunile matricii Mi.
Cerinta
Se cere să se minimizeze numărul total de înmulţiri scalare al produsului matricial M, precum şi o parantezare care dă acest număr de produse scalare.
Date de intrare
Fişierul de intrare pdm.in conţine pe prima linie un număr natural n, reprezentând numărul matricelor. Pe următoarea linie se găsesc n + 1 numere naturale, reprezentând valorile şirului d.
Date de ieşire
În fişierul de ieşire pdm.out se va găsi un singur număr natural egal cu valoarea minimă a numărului total de înmulţiri scalare a produsului matricial M şi parantezarea optimă corespunzătoare acestuia.
Formatul afişării unei parantezări este următorul:
-dacă parantezarea conţine un factor, se va afişa doar acesta
-dacă parantezarea conţine doi factori, va fi pusă între paranteze, iar factorii ei afişaţi pe rând
Restricţii
- 1 ≤ N ≤ 500
- 0 ≤ d ≤ 1000
- În cazul în care există mai multe soluţii, de exemplu A şi B, se va afişa parantezarea care ar realiza primele k înmulţiri între aceleaşi matrice , îar a k+1-a înmulţire în ordine inversă, la o matrice de ordin mai mic. În alte cuvinte, dacă avem 3 matrice, iar variantele ((A*B)*C), (A*(B*C)) oferă aceeaşi soluţie, se va alege prima variantă.
- Pentru afişarea corectă doar a numărului de înmulţiri scalare, se acordă 40% din punctaj.
Exemplu
pdm.in | pdm.out |
---|---|
4 13 5 89 3 34 | 2856 ((1*(2*3))*4) |