e-olymp 1484. Серебрянная матрица

Задача

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

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

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

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

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

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

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

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

Тесты

# Входные данные Выходные данные
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. Затем рекурсивно будем заполнять матрицу такими числами которых гарантировано нет ни в строке, ни в столбце. Например, для случая [latex]k = 1[/latex] подбираем вручную матрицу удовлетворяющую всем условиям. В противном же случае спускаемся к случаю [latex]k = 1[/latex] и затем наращиваем недостающие ряды подходящими для нас числами. То есть находим промежуток from и с помощью него заполняем одинаковыми значениями диагонали матрицы. Затем идем по незаполненным полям и заполняем новыми числами, которые еще не встречались.

Ссылки

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

e-olymp 5282. Седловые точки

Задача

Задана матрица [latex]K[/latex], содержащая [latex]n[/latex] строк и [latex]m[/latex] столбцов. Седловой точкой этой матрицы назовём элемент, который одновременно является минимумом в своей строке и максимумом в своём столбце.
Найдите количество седловых точек заданной матрицы.
Saddle point

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

Первая строка содержит целые числа [latex]n[/latex] и [latex]m[/latex]. [latex](1 ≤ n, m ≤ 750)[/latex]. Далее следуют [latex]n[/latex] строк по [latex]m[/latex] чисел в каждой. [latex]j[/latex]-ое число [latex]i[/latex]-ой строки равно [latex]k_{ij}[/latex]. Все [latex]k_{ij}[/latex] по модулю не превосходят [latex]1000[/latex].

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

Выведите количество седловых точек.

Тесты

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

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

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

Для каждой строки, будем осуществлять два прохода. В первом найдем минимальное число, а во втором, если значение очередного элемента будет являться в ней минимумом, то проверим будет ли оно максимумом в своем столбце таким образом, что если элемент заранее созданного массива [latex]([/latex] в котором изначально лежат все [latex]Unknown ([/latex] заранее созданная константа равная [latex]1001[/latex][latex] ([/latex] так как по условию, числа которые мы вводим не больше чем [latex]1000 ) ) )[/latex] не равен [latex]Unknown[/latex], то просто сравним элемент массива с минимумом, иначе найдем максимум для данного столбца и положим его в массив, о котором шла речь ранее и сравним уже это число с минимумом строки. Если они совпадают, то это и есть седловая точка!

Ссылки

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

Код решения на ideone.com.

А705

Задача:
Даны квадратные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex]. Получить матрицу [latex]A(B-E)+C[/latex], где [latex]E[/latex] — единичная матрица порядка [latex]n[/latex], а элементы матрицы [latex]C[/latex] вычисляются по формуле:[latex]C_{ij}=\frac{1}{i+j}\;\;\;\;(i,j=1,2,\ldots,n)[/latex].

Тесты
К сожалению я не разместила здесь тесты к задаче.

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

Код C++

Код C++ на Ideone: A705

Код Java

Код Java на Ideone: A705

Тесты:

№ теста Размерность матрицы n Матрица A Матрица В Ответ
1 2 3 4
2 1
2 1
9 0
  39.50  -0.67

11.33  1.25

2 4 5 5 5 5
0 0 8 7
2 3 4 7
8 6 1 2
5 7 3 4
9 8 3 4
2 3 4 5
6 6 6 6
  105.50  115.33  75.25  90.20

58.33  66.25  66.20  75.17

85.25  89.20  69.17  75.14

100.20  113.17  57.14  71.12

3 3 0 0 0

0 0 0

0 0 0

1 0 0

0 1 0

0 0 1

 0.5 0.33 0.25

0.33 0.25 0.20

0.25 0.20 0.17

 

А396

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

Тесты:

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

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

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

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

Решение на Java:

Код на Java.