Productes de matrius P97589


Statement
 

pdf   zip

thehtml

Feu un programa que, donada una seqüència de matrius quadrades m1, …, mn, escrigui en quin ordre s’han de multiplicar exactament un cop de manera que el resultat sigui com més gran millor. Considerarem que les matrius s’han de comparar en ordre lexicogràfic, de dalt a baix i d’esquerra a dreta.

Entrada

L’entrada consisteix en un natural n > 0, seguit de m1, …, mn. Totes les matrius tenen mida 2 × 2, i els seus quatre elements (naturals entre 0 i 9) apareixen en una o més línies.

Sortida

Escriviu l’ordre en què s’han de multiplicar totes les matrius exactament un cop de manera que el resultat sigui màxim, seguint el format dels exemples. Si hi ha més d’una manera d’obtenir el mateix resultat, quedeu-vos amb la més petita lexicogràficament, comparant les matrius d’esquerra a dreta.

Public test cases

  • Input

    2

1 2
3 4

5 6
7 8

    Output

    5 6 * 1 2 = 23 34
7 8   3 4   31 46

  • Input

    1

3 4
6 7

    Output

    3 4 = 3 4
6 7   6 7

  • Input

    3

9 0 3 3

2 2 0 2

1 1 5 0

    Output

    2 2 * 1 1 * 9 0 = 114 6
0 2   5 0   3 3   90 0

  • Input

    2

3 0 0 3

1 3 0 4

    Output

    1 3 * 3 0 = 3 9
0 4   0 3   0 12
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions