eolymp
bolt
Try our new interface for solving problems
Məsələlər

Оптимальное умножение матриц - 2

Оптимальное умножение матриц - 2

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Имея две матрицы A и B, мы можем вычислить C = AB используя стандартные правила умножения матриц:

prb1521

Число колонок в матрице A должно совпадать с числом строк матрицы B. Обозначим через rows(A) и columns(A) соответственно количество строк и колонок в матрице A. Количество умножений, необходимых для вычисления матрицы C (ее количество строк совпадает с A, а количество столбцов с B) равно rows(A) * columns(B) * columns(A). Например, если A имеет размер 10 × 20, B имеет размер 20 × 15, то необходимо совершить 10 × 20 × 15 = 3000 умножений для вычисления матрицы C.

prb1521_3.gif

Перемножать несколько матриц можно несколькими способами. Например, если у нас имеются матрицы X, Y и Z, то вычислить XYZ можно либо как (XY)Z, либо как X(YZ). Пусть X имеет размер 5 × 10, Y имеет размер 10 × 20, Z имеет размер 20 × 35.

prb1521.gif

Подсчитаем количество умножений, необходимых для перемножения трех матриц в каждом из этих двух случаях:

(XY)Z

  • 5 × 20 × 10 = 1000 умножений для определения матрицы (XY), имеющей размер 5 × 20.

  • Потом 5 × 35 × 20 = 3500 умножений для нахождения конечного результата.

  • Общее количество умножений: 4500.

X(YZ)

  • 10 × 35 × 20 = 7000 умножений для определения матрицы (YZ), имеющей размер 10 × 35.

  • Потом 5 × 35 × 10 умножений для нахождения конечного результата.

  • Общее количество умножений: 8750.

Очевидно, что при вычислении (XY)Z требуется меньшее количество умножений.

prb1521_2.gif

По заданной последовательности перемножаемых матриц следует найти оптимальный порядок их умножения. Оптимальным называется такой порядок умножения матриц, при котором количество элементарных умножений минимально.

Giriş verilənləri

Для каждой последовательности перемножаемых матриц Вам будут даны лишь размеры матриц. Каждый тест состоит из количества n (n10) перемножаемых матриц, за которым следуют n пар целых чисел, описывающих размеры матриц (количество строк и столбцов); размеры матриц задаются в порядке их перемножения. Последний тест содержит n = 0 и не обрабатывается.

Çıxış verilənləri

Пусть матрицы пронумерованы A1, A2,..., An. Для каждого теста в отдельной строке следует вывести его номер и скобочное выражение, содержащее оптимальный порядок умножения матриц. Тесты нумеруются начиная с 1. Вывод должен строго соответствовать формату, приведнному в примере. Если существует несколько оптимальных порядков перемножения матриц, выведите любой из них.

Nümunə

Giriş verilənləri #1
3
1 5
5 20
20 1
3
5 10
10 20
20 35
6
30 35
35 15
15 5
5 10
10 20
20 25
0
Çıxış verilənləri #1
Case 1: (A1 x (A2 x A3))
Case 2: ((A1 x A2) x A3)
Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))