Diferențe pentru problema/pdm între reviziile #1 si #14

Diferențe între titluri:

pdm
Pdm

Diferențe între conținut:

== include(page="template/taskheader" task_id="pdm") ==
Poveste și cerință...
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.
 
h2. 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.
h2. Date de intrare
Fișierul de intrare $pdm.in$ ...
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.
h2. Date de ieșire
În fișierul de ieșire $pdm.out$ ...
Î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
 
h2. 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.
h2. Exemplu
table(example).
|_. pdm.in |_. pdm.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
  13 5 89 3 34
| 2856
  ((1*(2*3))*4)
|
h3. Explicație
 
...
 
== include(page="template/taskfooter" task_id="pdm") ==

Nu există diferențe între securitate.