N - Násobenie matíc

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Študent informatiky Filip si zapísal predmet Úvod do počítačovej grafiky, kde sa dozvedel, že pri výpočtoch na grafickej karte sa násobia matice (otočenia, posunutia, ...). Za úlohu dostali implementovať takéto násobenie viacerých matíc. Ako riešiteľa rýchlostného programovania, zaujala ho aj efektivita riešenia násobenia matíc.
Dve matice sa môžu vynásobiť, ak počet stĺpcov prvej matice sa zhoduje s počtom riadkov druhej matice. Nech majú teda rozmenry n x m a m x o. Výsledkom je matica s rozmermi n x o. Na výpočet výsledku je potrebných n.m.o násobení prvkov.
Pri násobení viacerých matíc sa postupne vynásobia susedné dve matice, až pokiaľ neostane už len jedna, výsledná matica. Výsledok bude pri ľubovoľnom výbere susedných matíc rovnaký (násobenie matíc je asociatívne), ale efektivita, teda celkový počet násobení prvkov sa môže líšit. Filip sa rozhodol, že vypočíta minimálny počet násobení prvkov pri násobení matíc.

Úloha

Pre zadané rozmery matíc vypočítajte minimálny počet násobení potrebný na výpočet výslednej matice.

Vstup

Vstup obsahuje dva riadky. Na prvom riadku je jedno celé číslo N (1 ≤ N ≤ 100), počet matíc. Druhý riadok obsahuje N+1 kladných celých čísel (z rozsahu 1 až 1000), rozmery matíc.

Výstup

Výstup obsahuje jedno celé kladné číslo, minimálny počet násobení. Keďže tento počet môže byť veľké číslo, vypíšte ho modulo 99991.

Príklad

Vstup:

3 
2 1000 2 1000

Výstup:

Vstup popisuje 3 matice A, B, C s rozmermi 2x1000, 1000x2 a 2x1000. Pri násobení matíc (A.B).C bude potrebných 8 000 násobení prvkov, ale pri násobení A.(B.C) až 4 000 000.

17 Finále 2