| Автор: | Команда перемножения матриц (Василенко М. Поповиченко Р. Охрименко М.) | Ограничение времени: | 10 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 1024 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 1 |
В качестве шифрования для передачи данных между штабами было принято использовать метод умножения матриц Штрассера. Берётся некоторая матрица B, известная всем штабам. Секретные данные записываются числами в некоторую матрицу A. Данные матрицы умножаются по методу Штрассера и записываются все M1, M2, ..., M7, используемые в методе Штрассера. Данные M передаются в другой штаб, где их уже расшифровывают. Однако в ходе операции врага часть данных может не дойти до базы.
Ваша задача — написать дешифратор, который по матрице B и неполным M должен найти матрицу A. Причём элемент матрицы A равен числу только в том случае, если он однозначно определяется M. В противном случае на его место выводится символ "_". Для создания M используется следующий код:
def split(A):
n = A.shape[0]
k = n // 2
return A[:k, :k], A[:k, k:], A[k:, :k], A[k:, k:]
def strassen(A, B):
if A.shape[0] == 1:
return A * B
A11, A12, A21, A22 = split(A)
B11, B12, B21, B22 = split(B)
M1 = strassen(A11 + A22, B11 + B22)
M2 = strassen(A21 + A22, B11)
M3 = strassen(A11, B12 - B22)
M4 = strassen(A22, B21 - B11)
M5 = strassen(A11 + A12, B22)
M6 = strassen(A21 - A11, B11 + B12)
M7 = strassen(A12 - A22, B21 + B22)
Первая строка содержит целое число t, где 2t — размер квадратных матриц A и B. Далее идут 2t строк, содержащие матрицу B. Затем идут 7t-1 строк, содержащие все значения M1, …, M7, где каждый элемент либо целое число, либо "_".
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|