Explotando la asociatividad
Las matrices son estructuras bidimensionales de números que se utilizan intensivamente en matemáticas y otras ramas de la ciencia. La suma y multiplicación de matrices está definida, por lo que forman un anillo.
Una matriz se caracteriza por el número de filas y de columnas que tiene. Para sumar dos matrices ambas tienen que tener las mismas dimensiones. Por su parte, la multiplicación de dos matrices exige que el número de columnas de la primera matriz (en el lado izquierdo) sea el mismo que el número de filas de la segunda (en el lado derecho). Esto supone que la multiplicación de matrices no es conmutativa. De hecho si la multiplicación A×B está definida puede que no lo esté la de B×A.
La multiplicación de matrices tiene otras características curiosas. La matriz resultante tiene tantas filas como la primera matriz y tantas columnas como la segunda. Además, la cantidad de multiplicaciones de números (escalares) necesaria para calcular A×B es el número de elementos de A por el número de columnas de B.
Aunque la multiplicación de matrices no cumple la propiedad conmutativa, sí cumple la propiedad asociativa. Si tenemos una cadena de multiplicaciones de matrices podemos hacerlas en cualquier orden y el resultado será el mismo. Como la multiplicación de dos matrices tiene un coste en cantidad de cálculos que depende de qué matrices sean, y las dimensiones del resultado también, el orden en el que se calculen las multiplicaciones puede afectar enormemente al número de operaciones necesarias.
Entrada
El programa deberá procesar varios casos de prueba, cada uno ocupando dos líneas.
La primera contiene un número 2 ≤ n ≤ 100 con el número de matrices que hay que multiplicar. La segunda contiene n+1 números entre 1 y 100, a1, a2,…an+1. Cada pareja consecutiva de números contiene el número de filas y de columnas de una matriz. En concreto la matriz i del caso de prueba tiene ai filas y ai+1 columnas. Esto hace que dos matrices adyacentes puedan ser siempre multiplicadas.
Salida
Por cada caso de prueba se escribirá el mínimo y máximo número de multiplicaciones de números necesarias para calcular la multiplicación de todas las matrices si se utiliza el método estándar de multiplicación de dos matrices.
Entrada de ejemplo
2 2 3 2 4 2 3 4 5 3
Salida de ejemplo
12 12 94 123