# Problem

In a place in Southwestern Europe, the name of which I do not wish to recall, not long ago there were $n$ cities connected by unidirectional roads, with possibly more than one road connecting a city to another one, or even to itself. As a homework assignment for your geography class, you need to calculate the number of paths of length exactly two that were between each pair of cities. However, you’ve been too busy celebrating the Spanish victory in the World Cup, so now you are copying the answers from your friend. You would like to make sure his answers are correct before handing in your homework.

# Input

The input consists of several test cases, separated by single blank lines. Each test case begins with a line containing the integer $n$ $(1 \leqslant n \leqslant 1000)$. The following $n$ lines contain $n$ elements each, with element $j$ of line $i$ being the number of roads from city $i$ to city $j$ (a number between $0$ and $10$, inclusive). After that, there will be $n$ lines. Each will contain $n$ elements, with element $j$ of line $i$ being the answer from your friend for the number of length-$2$ paths from city $i$ to city $j$; it will be an integer between $0$ and $100000$ inclusive.

The test cases will finish with a line containing only the number zero (also preceded by a blank line).

Note: Large input file; use fast I/O routines.

# Output

For each case, your program should output a line. The content of this line should be «YES» if your classmate’s solution to the assignment is right, and «NO» otherwise.

# Tests

 № Input Output 1 3 2 0 1 1 0 3 1 1 0 5 1 2 5 3 1 3 0 43 2 0 1 1 0 3 1 1 0 5 1 2 5 3 2 3 0 40 YES NO 2 5 1 2 7 8 9 4 5 8 7 3 1 0 2 5 6 1 0 0 5 4 1 7 2 5 9 33 75 55 142 170 42 54 90 157 154 14 44 23 73 95 10 30 15 53 65 45 100 85 137 1435 1 2 7 8 9 4 5 8 7 3 1 0 2 5 6 1 0 0 5 4 1 7 2 5 9 33 75 55 142 170 42 4 90 157 154 14 44 23 73 95 10 30 15 53 65 45 100 85 137 1430 YES NO 3 1 2 21 2 40 NO YES 4 9 1 5 7 9 10 6 3 3 6 10 2 0 5 10 4 3 3 5 7 10 4 1 4 0 4 4 2 5 4 0 1 7 0 5 3 2 7 0 6 1 7 5 2 2 2 7 4 0 1 1 8 6 6 3 0 4 9 2 1 8 0 3 7 8 7 7 3 5 0 10 8 2 1 0 5 8 8 8 3 3 1 287 178 173 129 293 196 195 180 134 182 123 203 174 287 214 150 143 144 202 143 163 158 261 150 126 128 148 125 78 153 108 182 137 82 89 109 156 141 157 108 183 149 120 120 105 166 145 166 147 192 199 157 161 147 207 159 98 105 176 141 159 149 81 243 232 270 182 300 197 184 192 201 213 152 128 61 176 142 160 147 1000 YES

# Solution

The problem statement says that element $j$ of line $i$ of the matrix corresponds to the number of unidirectional roads from city $i$ to city $j$. Thus, we have an adjacency matrix of a directed unweighted graph. We need to find the number of paths of fixed length $k = 2$ for each pair of cities and compare them to our friend’s answer from the output. Adjacency matrix $g_{n \times n}$ of a directed unweighted graph contains the number of routes of length $k = 1$  between each pair of vertices. The solution is iterative: adjacency matrix $g$ corresponds to paths of length $k = 1$. Let $g = d_k$. For $k + 1$ we have: $d_{k+1}[i][j] = \sum\limits_{p=1}^n d_k[i][p] \cdot g[p][j]$, i.e. the product of matrices $d_k$ and $g$. Conclusion: to count the routes of fixed length we have to raise the adjacence matrix to the correspondent power.

Testcases are processed one at a time and after each the answer is given. Firstly, two 2D arrays of size $n \times n$ are initialized and entered: one for storing the matrix with the amounts of paths and the other with our friend’s answers. There is a warning about a big input file in the problem statement. Thus we use C style for I/O operations. Secondly, the first matrix is squared and the results are compared to the friend’s answers one by one. Once an error is detected the loop ends and the answer «NO» is displayed. Otherwise the loop reaches its end and «YES» is displayed. It is necessary that both arrays are deleted before processing the next testcase to prevent memory leaks.

# e-olymp 4749. Выручка театра

## Задача

В театре $n$ рядов по $m$ мест в каждом. Даны две матрицы — в первой записаны стоимости билетов. Вторая сообщает, какие билеты проданы, а какие — нет ($1$ — соответствующий билет продан, $0$ — не продан).
Определите общую выручку от спектакля.

#### Входные данные

Сначала записано число $n$, затем число $m$ $(n, m \le 500)$. После задана матрица стоимостей билетов ($n$ строк по $m$ чисел, каждое из чисел от $0$ до $10000$). Далее задана матрица проданных билетов — снова $n$ строк по $m$ чисел.

#### Выходные данные

Выведите общую выручку от продажи билетов.

#### Тесты

 Входные данные Выходные данные 3 3 1 2 3 4 5 6 7 8 9 1 0 1 0 1 0 1 0 1 25 1 1 1 0 0 1 1 1 1 1

#### Решение

Считаем выручку, суммируя цену каждого билета, умноженную на $1$ либо $0$ в зависимости от того продан он или нет соответственно.

# Задача

Задана матрица чисел $a_{ij}$ где $1 \leqslant i \leqslant n$, $1 \leqslant j \leqslant m$. Для всех $i, j$ найдите $$S_{i,j}=\sum_{k=1, t=1}^{k\leqslant i, t \leqslant j}a_{kt}.$$

## Входные данные

В первой строке записаны размеры матрицы — $n, m$ $(1 \leqslant n, m \leqslant 1000)$. В последующих $n$ строках записано по $m$ чисел $a_{ij}$ $(1 \leqslant a_{ij} \leqslant 1000)$.

## Выходные данные

Выведите $n$ строк по $m$ чисел $S_{i,j}$.

## Тесты

 Входные данные Выходные данные 3 5 1 2 3 4 5 5 4 3 2 1 2 3 1 5 4 1 3 6 10 15 6 12 18 24 30 8 17 24 35 45 4 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 2 4 6 8 3 6 9 12 4 8 12 16 6 7 15 78 69 36 567 654 5 54 54 52 81 237 5 98 987 2 65 5 32 89 67 541 89 4 32 4 1 40 68 7 345 6 21 23 56 9 5 7 2 5 4 1000 15 93 162 198 765 1419 1424 69 201 322 439 1243 1902 2005 1056 1190 1376 1498 2334 3082 3252 1597 1820 2010 2164 3004 3753 3963 1665 1895 2430 2590 3451 4223 4489 1674 1909 2451 2613 3479 4255 5521

## Решение

Создаем  матрицу x[1001][1001]  вне int main() . Сдвигаем индексацию массива на единицу и заполняем его. Таким образом первая строка и первый столбец у нас оказываются заполнены нулями. Чтобы не вычислять каждую новую $S_{i,j}$ от $(i+1)\cdot (j+1)$ предыдущих значений, воспользуемся основным свойством частичных сумм: если $$S_{i,j}=\sum_{k=1, t=1}^{k\leqslant i, t \leqslant j}a_{kt},$$ то тогда $S_{i,j} — a_{ij}=S_{i-1,j}+S_{i,j-1}-S_{i-1,j}\cap S_{i,j-1}$, где $S_{i-1,j}\cap S_{i,j-1} = S_{i-1,j-1}$. Тогда при $1 \leqslant i \leqslant n$, $1 \leqslant j \leqslant m$ вычисляем частичные суммы по формуле: $$S_{i,j} = S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}+a_{ij}.$$

## Ссылки

Условие задачи на E-olymp

Код программы на IdeOne

# Задача

## Условие

Задана матрица $n \cdot n$ — назовем ее $[1..n] \cdot [1..n]$ массивом. Для заданных $r$ и $c$ следует вывести $[1..r] \cdot [1..c]$ массив ($r$ строк и $c$ столбцов исходного массива).

## Входные данные

Первая строка содержит число $n (1 \leq n \leq 100)$. Следующие строки содержат матрицу $n \cdot n$. Последняя строка содержит два числа $r$ и $c$ $(1 \leq r, c \leq n)$. Все числа в матрице не превышают по модулю $100$.

## Выходные данные

Выведите матрицу $r \cdot c$.

# Тесты

 № Входные данные Выходные данные 1 4 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 3 2 1 2 5 6 9 1 2 5 18 25 34 44 -43 54 65 75 85 -32 95 15 25 35 -3 -4 15 -6 37 0 44 43 23 3 -12 4 3 18 25 34 54 65 75 95 15 25 -4 15 -6 3 2 0 -1 23 69 1 1 0 4 3 1 2 3 -4 -5 -6 7 8 9 3 1 1 -4 7

# Решение

Для решения данной задачи необходимо ввести в массив все имеющиеся данные и вывести необходимые, соответственно заданным параметрам. Можно использовать как одномерные массивы, так и двухмерные.
В реализации с одномерными вводим все данные в массив $n \cdot n$, а затем выводим, используя вложенные циклы. Цикл проходит от $0$ до $r$ и от $(j \cdot n)$ — первого элемент необходимой строки до $(c + j \cdot n)$ — последнего элемента. В реализации с двумерными массивами заводим все данные в один массив и после выводим необходимые.

# Задача

По заданной матрице A размера n×n и положительному целому значению $k$ вычислить сумму $S = A + A^2+ A^3 + … + A^k.$

## Входные данные

Первая строка содержит три положительных целых числа $n (n ≤ 30)$, $k (k ≤ 10^9)$ и $m (m < 10^4)$. Каждая из следующих $n$ строк содержит $n$ неотрицательных целых чисел меньших $32768$, задающих элементы матрицы $A$ в порядке возрастания строк.

## Выходные данные

Вывести элементы матрицы $S$ по модулю $m$ в таком же виде как и входная матрица $A$.

## Тесты

 № Ввод Вывод 1 2 2 4 0 1 1 1 1 2 2 3 2 4 7 2 3 5 12 10 8 9 2 16 7 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 3 5 10 78 7 6 0 1 6 12 9 1 1 8 1 1 3 1 9 8 5 34 1 7 5 5 5 5 5 2 67 36 32 48 2 6 10 49 65 67 14 58 4 29 64 54 33 45 46 41 4 50 8 55 4 3 2 4 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 5 5 100 1000 1846 4675 8090 4539 1234 4567 7453 9564 6548 1111 5674 9876 5432 1010 1515 0 478 3 11 0 68303 7777 32767 14 8008 614 7 945 925 381 22 332 981 689 527 351 627 130 686 420 340 628 819 758 629 913 426 396 871 91

Код

## Решение

Для решения данной задачи опишем матрицу как структуру и функциями зададим простейшие операции над матрицами — сложение и умножение. Результат обеих функций будем будем брать по модулю $m$, чтоб уменьшить числа, с которыми работаем.

Далее создадим функцию быстрого возведения в степень. $A^k$ представим как $\left(A^2\right)^\frac{k}{2}$ при четном  $k$ и $A × \left(A^2\right)^{\frac{k — 1}{2}}$ в противном случае. Такой алгоритм позволяет значительно уменьшить количество умножений.

И, наконец, последняя функция. Тут все зависит от показателя степени. Если он равен единице, ответом будет исходная матрица. Если же нет, функция становится рекурсивной и с помощью всех остальных описанных ранее функций нам удается получить искомую сумму.

Все, что еще необходимо сделать — вывести результат по модулю $m$.

### Замечание

Тесты на e-olymp требуют отсутствия пробела после последнего столбца.

## Ссылки

Условие задачи на e-olymp

Код задачи на Ideone

# Задача

Задана матрица размера $n \times n.$ Найдите количество и сумму ее четных отрицательных чисел.

## Входные данные

Первая строка содержит число $n (1 \leq n \leq 100).$ Следующие строки содержат матрицу $n \times n.$ Элементы матрицы по модулю не больше $100.$

## Выходные данные

Выведите в одной строке количество и сумму четных отрицательных чисел в матрице.

# Тесты

 Входные данные Выходные данные 1 3 4 -2 5 1 -4 -12 0 1 -3 3 -18 2 2 4 -7 2 9 0 0 3 5 3 4 -5 7 2 1 2 3 4 -2 -2 -4 -6 -8 4 2 -4 0 -1 6 -26 4 4 1 2 3 4 -1 -2 -4 -3 4 -5 -8 -12 -4 -5 -7 0 5 -30

# Решение

## С помощью массива

Создаем массив.  С помощью цикла for проверяем: если число отрицательное и чётное, то прибавляем его к sum. Выводим количество таких чисел и их сумму.

## Без массива

С помощью цикла for проверяем: если число отрицательное и четное, то прибавляем его к  sum.  Выводим количество таких чисел и их сумму.

# Задача

Задана матрица $n \times n$ — назовем ее $[1 \ldots n] \times [1 \ldots n]$ массивом. Для заданных $r$ и $c$ следует вывести $[1 \ldots r] \times [1 \ldots c]$ массив ($r$ строк и $c$ столбцов исходного массива).

## Входные данные

Первая строка содержит число $n \space (1 \leq n \leq 100)$. Следующие строки содержат матрицу $n \times n$. Последняя строка содержит два числа $r$ и $c \space (1 \leq r, c \leq n)$. Все числа в матрице не превышают по модулю $100$.

## Выходные данные

Выведите матрицу $r \times c$.

## Тесты

 Входные данные Выходные данные 4 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 3 2 1 2 5 6 9 1 5 18 25 34 44 -43 54 65 75 85 -32 95 15 25 35 -3 -4 15 -6 37 0 44 43 23 3 -12 4 3 18 25 34 54 65 75 95 15 25 -4 15 -6 6 30 -10 30 -69 -84 75 -3 -39 60 15 75 -74 36 68 35 23 25 -44 16 42 83 15 59 -18 71 43 35 -81 -38 51 37 -49 55 26 6 33 4 5 30 -10 30 -69 -84 -3 -39 60 15 75 36 68 35 23 25 16 42 83 15 59

# Решение

Для того, чтобы вывести матрицу на экран, нам нужно запустить $2$ цикла, один из которых будет вложен в предыдущий:

• первый цикл ($14$ строка кода) будет отвечать за количество выводимых строк матрицы — по условию, нужно вывести первые $r$ строк;
• второй цикл ($15$ строка кода) будет отвечать за количество выводимых столбцов матрицы — по условию, нужно вывести первые $c$ столбцов.

# Задача

Матрицу будем называть серебрянной, если она удовлетворяет следующим условиям:

Размеры матрицы $n\times n$.
Все элементы матрицы лежат во множестве $S =${$1, 2, 3, \ldots, 2n-1$}.
Для каждого целого числа $i \left(1 ≤ i ≤ n\right),$ все элементы $i$-ой строки и $i$-го столбца образуют множество {$1, 2, 3, \ldots, 2n-1$}.
Например, следующая матрица размера $4×4$ является серебряной:

 1 2 5 6 3 1 7 5 4 6 1 2 7 4 3 1

Доказано, что серебряная матрица размером $2^K\times 2^K$ всегда существует. Вам следует построить серебряную матрицу $2^K\times 2^K$.

# Входные данные

Единственное число $K \left(1 ≤ K ≤ 9\right).$

# Выходные данные

Вывести серебряную матрицу размером $2^K×2^K$. Для вывода матрицы $2^K\times 2^K$, следует вывести $2^K$ строки, каждая из которых содержит $2^K$ целых чисел.

# Тесты

 # Входные данные Выходные данные 1 2 3 1 7 5 4 6 1 2 7 4 3 1 2 1 1 2 3 1 3 3 1 2 5 6 9 10 13 14 3 1 7 5 11 9 15 13 4 6 1 2 12 14 9 10 7 4 3 1 15 12 11 9 8 10 13 14 1 2 5 6 11 8 15 13 3 1 7 5 12 14 8 10 4 6 1 2 15 12 11 8 7 4 3 1

# Решение задачи

Доказано, что матрица гарантировано существует. Напишем частный случай когда матрица имеет степень 1. Затем рекурсивно будем заполнять матрицу такими числами которых гарантировано нет ни в строке, ни в столбце. Например, для случая $k = 1$ подбираем вручную матрицу удовлетворяющую всем условиям. В противном же случае спускаемся к случаю $k = 1$ и затем наращиваем недостающие ряды подходящими для нас числами. То есть находим промежуток from и с помощью него заполняем одинаковыми значениями диагонали матрицы. Затем идем по незаполненным полям и заполняем новыми числами, которые еще не встречались.

# Ссылки

Ссылка на e-olymp
Ссылка на ideone

# e-olymp 2371. Черный квадрат

## Условие

Вдохновленный шедевром Казимира Малевича «Черный квадрат», Петр Палевич решил создать собственную версию картины. Он приготовил полотно в виде прямоугольной сетки с $m \times n$ белыми квадратами — $m$ строк по $n$ ячеек каждая.

Петр покрасил некоторые клетки в черный цвет так, что черные ячейки сформировали квадрат размером $s \times s$ ячеек. Но на следующий день Петр разочаровался в своем творении и уничтожил его, разрезав полотно горизонтальными полосами размера $1 \times n$, после чего сжег их в камине.

На следующее утро Петр передумал и решил восстановить картину. Он попытался найти ее останки в камине, и, к счастью, одну из полос, а именно $k$-ую сверху, огонь не тронул.

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

## Входные данные

Первая строка содержит четыре целых числа: $m$, $n$, $s$ и $k$ $\left( 1 \leqslant m, n \leqslant 5000, 1 \leqslant s \leqslant \min \left( m, n \right), 1 \leqslant k \leqslant m \right)$.

Вторая строка содержит $n$ символов и описывает $k$-ую строку картины, ‘.’ означает белую клетку, ‘*’ означает черную клетку.

## Выходные данные

Если изображение может быть однозначно восстановлено, то следует вывести «Unique». Если существует несколько вариантов восстановления картины, то вывести «Ambiguous». Если ни одной соответствующей картины не существует, вывести «Impossible».

## Тесты

 Ввод Вывод $3$ $4$ $2$ $3$ ..** Unique $4$ $4$ $2$ $3$ *.*. Impossible $3$ $5$ $2$ $2$ .**. Ambiguous $2$ $8$ $1$ $2$ ……*. Unique

## Решение

Основная сложность задачи заключается в аккуратном рассмотрении всех возможных вариантов. После прочтения строки символов, которую представляет собой вытащенная из огня полоска, исследуем ее на количество подряд идущих символов ‘*’. Если последовательностей из звездочек в одной строке несколько, то никакие добавленные полоски не смогут сделать из нее квадрат, и тогда решений нет. Иначе дальнейшее решение делится на два случая:

1. Спасенная из огня полоска не содержит звездочек. Тогда мы проверяем, может ли поместиться квадрат из звездочек хотя бы в одну из двух частей, на которые эта полоска делит картину. Если да, проверяем, однозначно ли определяем этот квадрат, или же имеется несколько вариантов его возможного расположения в них.
2. Спасенная из огня полоска содержит звездочки. Тогда, если количество звездочек не совпадает с длиной стороны квадрата, то построить его невозможно, а иначе проверяем, однозначно ли определяем этот квадрат. Здесь необходимо аккуратно рассмотреть все «особенные» случаи, такие как квадрат, состоящий из одной звездочки, а также первая и последняя полоски картины. Очевидно, что в этих случаях расположение квадрата определяется единственным образом.

Если сравнивать, что выгоднее использовать в данной задаче для задания спасённой из огня полоски — строку или массив символов, — то использование строки способствует немного более быстрому решению задачи, чем массив символов; объём используемой памяти при этом не изменяется.

# Задача

Напишите программу, которая выводит элемент из строки $x$ и столбца $y$ матрицы размера $n × m$, которая заполнена змейкой:

# Входные данные

Даны натуральные числа $n$, $m$, $x$, $y$ $(1 ≤ x ≤ n ≤ 50, 1 ≤ y ≤ m ≤ 50)$. Здесь $n$ — количество строк матрицы, $m$ — количество столбцов матрицы, $x$ и $y$ — номера строки и столбца искомого элемента.

# Выходные данные

Вывести элемент из строки $x$ и столбца $y$.

# Тесты

 Входные данные Выходные данные $5 \; 2 \; 3 \; 1$ $4$ $6 \; 3 \; 4 \; 3$ $9$ $10 \; 5 \; 10 \; 2$ $48$

# Решение задачи

Читаем входные данные и объявляем массив $n$ на $m$, $num = 0$ — число элемента в этом массиве, далее будем заполнять его в цикле. Делаем перебор строк, для каждой строки есть число $j$ — номер элемента (в текущей строке), с которого мы записываем числа и число $dir$ — направление, в которое мы эти числа записываем (оно у нас 1 или -1). Если строка четная, то начинаем движение слева направо, если нечетная, то справа налево. Далее перебираем каждый элемент строки и записываем ему свой номер. В ответе выводим выбранный элемент.

# Ссылки

Условие задачи на e-olymp
Код решения на ideone

# Задача

Найти объём тетраэдра три стороны которого образованы векторами $\vec {a} = \left( x_a, y_a, z_a \right)$, $\vec {b} = \left( x_b, y_b, z_x \right)$, $\vec {c} = \left( x_c, y_c, z_c \right)$.

# Пояснительный рисунок

## Входные данные

Координаты векторов $\vec {a}$, $\vec {b}$, $\vec {c}$.

Объём тетраэдра.

# Тесты

Входные данные Выходные данные
$x_a$ $y_a$ $z_a$ $x_b$ $y_b$ $z_b$ $x_c$ $y_c$ $z_c$ $V$
0 0 1 0 1 0 1 0 0 0.166667
3 6 3 1 3 -2 2 2 2 3
0 0 0 1 3 -2 2 2 2 0

# Решение задачи

Так как тетраэдр построен на векторах $\vec {a} = \left( x_a, y_a, z_a \right)$, $\vec {b} = \left( x_b, y_b, z_x \right)$, $\vec {c} = \left( x_c, y_c, z_c \right)$, для данной задачи оптимальным решением будет использовать следующие формулы:

1. $V = \frac {|\Delta|} {6}$, где $V$ — объём тетраэдра, а $\Delta$ — определитель матрицы.
2. $\Delta = \begin{vmatrix} x_a & y_a & z_a \\ x_b & y_b & z_b \\ x_c & y_c & z_c \end{vmatrix} = x_a \left(y_b z_c-z_b y_c \right)-x_b \left( y_a z_c-z_a y_c \right)+x_c \left( y_a z_b-z_a y_b \right)$.

Итоги:

• если значение определителя матрицы равно нулю, то либо некоторые из заданных векторов коллинеарны, либо нулевые, либо все они лежат в одной плоскости. Во всех этих случаях тетраэдр не может существовать, и программа выведет $0$;
• если значение определителя не равно нулю, то программа вычислит объём тетраэдра. В случае, если определитель примет отрицательное значение, программа домножит значение объёма на $-1$, в результате чего оно станет положительным.

# А712

Задача

Дана квадратная матрица $A$ порядка $n$. Получить матрицы $\frac{1}{2}(A+A^{*}) (1)$ и $\frac{1}{2}(A-A^{*}) (2)$.

Тесты:

 Ввод Вывод (1) Вывод (2) 3 1 2 3 2 4 6 1 4 8 1 2 2 2 4 5 2 5 8 0 0 1 0 0 1 -1 -1 0

Код:

Сначала, вводим размер матрицы и саму матрицу, сразу же транспонируем ее. Теперь каждый элемент обычной матрицы прибавляем к транспонированному и отнимаем от транспонированного в последствии умножая на $\frac{1}{2}$. Записываем это в две различные матрицы с результатом и выводим их на экран.

Код на Java

# А701б

### Условие

Даны квадратная матрица $A$ порядка $n$ и  вектор $b$ c $n$ элементами. Получить вектор ${ A }^{ 2 }b$

### Тесты

 n A b Результат 3 1 1 11 1 1 1 1 1 5 5 5 45  45 45 5 1 0 0 0 00 2 0 0 0 0 0 3 0 0 0 0 0 4 0 0 0 0 0 5 8  1 8 1 8 8  4  72  16 200 2 1 00 1 2 2 2 2

### Алгоритм

Считываем матрицу. Возводим ее в квадрат ( перемножение матрицы осуществляется при помощи циклов). Считываем вектор. Умножаем матрицу на вектор. Выводим ответ.

Фактически, умножение матриц пишется по определению. Сумма произведений элементов строки на элементы столбцов.

Ссылка на ideone.com

# А709

Условие:

Дана квадратная матрица $A$, порядка $m$, натуральное число $n$, действительные числа  $p_{n},p_{n-1},\ldots,p_{0}$. Получить матрицу $p_{n}A^{n}+p_{n-1}A^{n-1}+\ldots p_{1}A+p_{0}E$, где $E$- единичная матрица порядка $m$.

Тесты:

 Ввод количества p Ввод размерности матрицы А и одновременно Е 6 3

 Ввод коэффициентов 5 4 3 2 1 0

Матрица А:

 1 2 3 3 2 1 2 1 3

Результат:

 544308 445319 692718 544281 445354 692710 544277 445315 692753

Код:

Программа базируется на классе Matrix. Этот класс необходим для представления алгоритма вычисления полинома в естественной математической форме. Класс реализует следующие операции:

1. Создание матрицы заданного размера заполненной заданным числом
2. Умножение матрицы на число
3. Сложение матриц
4. Произведение матриц
5. Возведение матрицы в степень
6. Вывод содержимого матрицы на консоль

Класс Matrix содержит 3 члена – число строк, колонок и двумерный массив, который создается на куче. Главный модуль содержит две вспомогательный функции для ввода данных.

Основная часть программы состоит из следующих этапов:

1. Ввод данных: число итераций, размерности матрицы , списка коэфф. P и самой матрицы А
2. Создание единичной матрицы Е и далее – начального значения суммы E*P_0
3. Вывод исходных данных: E, A и P
4. Цикл суммирования, где вычисляется i-й элемент суммы
5. Вывод результата

Ссылка на ideone.com: http://ideone.com/ZWCf15

# А710

Дана матрица A размера $m*n$. Получить транспонированную матрицу A*(ее размер $n*m$).

n m А А*
5 4
5 6
4  3

Код программы:

Считываем матрицу $n*m$, а затем создаем транспонированную матрицу, в которой строки исходной матрицы являются столбцами и наоборот. Выводим A*.

Код программы.

# A699

A699. Даны квадратные матрицы $A$ и $B$ порядка $n$.Получить матрицу $AB-BA$.
 Размер матрицы Матрица А Матрица В Результат 3 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 -60 -90 -120 30     0   -30 120   90  60 2 3  13 21 8 7 9 2 4 -163 -84 73   163
Создаем матрицы $A, B, C, D, E,$ где $A$-первая матрица, $B$- вторая матрица, $C$-матрица $AB$, $B$- матрица $BA$, а $E$- матрица $AB-BA$. Вводим с клавиатуры матрица $A$ и $B$, а остальные заполняем нулями. Находим матрицу $C$ и $D$, после чего находим матрицу $E$.

Код программы можно посмотреть тут

# А409

Дана действительная квадратная матрица порядка 9. Вычислить сумму тех из её элементов, расположенных на главной диагонали и выше неё, которые превосходят по величине все элементы, расположенные ниже главной диагонали. Если на главной диагонали и выше неё нету элементов с указанным свойством, то ответом должно служить сообщение об этом.

 1 3 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Ответ 14
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 Ответ Нету элементов с такими свойствами

Находим наибольший из нижних элементов (элементы, расположенные ниже главной диагонали). Потом сравниваем каждый элемент верхнего множества (элементы, расположенные выше главной диагонали и на самой диагонали) с наибольшим элементов ($bigger$) всех нижних элементов и если это число больше, то прибавляем это число к переменной $summa$.

Java

# А396

Задача. Дана действительная квадратная матрица порядка n. Построить последовательность действительных чисел $a_{1}\cdots a_{n}$ по правилу: если в i-й строке матрицы элемент, принадлежащий главной диагонали, отрицателен, то $a_{i}$ равно сумме элементов i-й строки, предшествующих первому отрицательному элементу, в противном случае $a_{i}$ равно сумме последних элементов i-й строки, начиная с первого по порядку неотрицательного элемента.

Тесты:

 Данная матрица Последовательность Комментарий $\begin{Vmatrix}1 & 2 & -3 & 4\\ 3 & 5 & 6 & 7\\ 1 & 3 & 0 & 6\\ -5 & 7 & 2 & -9\end{Vmatrix}$ 4 21 10 0 Пройден $\begin{Vmatrix}1 & -2 & 3\\ -7 & -3 & 0\\ 5 & 5 & 2 \end{Vmatrix}$ 2 0 12 Пройден $\begin{Vmatrix}7 & 7 & 9 & 3\\ 0 & 5 & 0 & 7\\ 4 & 7 & -7 & 2\\ 1 & -4 & 8 & -3\end{Vmatrix}$ 26 12 11 1 Пройден

Код программы:

Для начала мы должны обнулить матрицу $b_{1}\cdots b_{n}$, элементы которой являются суммами элементов i-х строк входной матрицы, которую мы также задаем. А далее, с помощью циклов  for , можно оценить диагональные элементы заданной матрицы. И следуя условию, если они отрицательные, то в $b_{i}$ мы просуммируем все элементы данной строки, если они положительные, до первого отрицательного в строчке, а если они положительные, то $b_{i}$ будет равно сумме последних элементов строки (т.е. после диагонального) начиная с первого по порядку неотрицательного элемента. И в конце выводим конечную последовательность $b_{1}\cdots b_{n}$.

Код можно проверить здесь.

Решение на Java:

Код на Java.

# Ю4.9

Задача: В матрице $A\left(m,n \right)$ все ненулевые элементы заменить обратными по величине  и противоположными по знаку.

Тесты:

 n m Введенная матрица Полученная матрица 3 4 2 0 3 6 1 0 1 2 9 0 7 8 -0.5 0 -0.333333 -0.166667 -1 0 -1 -0.5 -0.111111 0 -0.142857 -0.125 3 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 5 -2 0 -4 5 -6 9 -8 7 -6 5 -7 3 -6 0 -9 0.5 0 0.25 -0.2 0.166667 -0.111111 0.125 -0.142857 0.166667 -0.2 0.142857 -0.333333 0.166667 0 0.111111 3 4 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
Ссылка на код: http://ideone.com/JX6G1b
Ссылка на код:ссылка

Ход решения:

Вводим матрицу $A$ размером $\left(m,n \right)$. Делаем цикл, в котором проверяем каждый элемент матрицы. Если он равен $0$ — мы оставляем его без изменений, если не равен $0$, то  умножаем его на обратный по величине и противоположный по знаку $\left(-\frac{1}{A\left[i \right]\left[j \right]} \right)$. Полученную матрицу выводим на печать.

# Ю4.10

Задача: Найти среднее арифметическое элементов каждой строки матрицы $Q\left(l,m \right)$ и вычесть его из элементов этой строки.

$l$ $m$ $Q\left(l,m \right)$ $\acute{Q}\left(l,m \right)$
2 3
 4 6 2 5 9 10
 0 2 -2 -3 1 2
4 3
 -5 -2 -3 6 5 0 -8 9 -64 468 -3 1
 -1.66667 1.33333 0.333333 2.33333 1.33333 -3.66667 13 30 -43 312.667 -158.333 -154.333
1 1 8 0

C++:

Java: