e-olymp 8525. Четные отрицательные в матрице

Задача

Задана матрица размера $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.  Выводим количество таких чисел и их сумму.

Ссылки

e-olymp 8530. Печать матрицы

Задача

Задана матрица $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$ столбцов.

Ссылки

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

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 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

Код

String

C-string

Решение

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

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

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

Ссылки

Условие на e-olymp.com
Код с использованием string на ideone.com
Код с использованием c-string на ideone.com

e-olymp 2667. Змейка

Задача

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

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

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

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

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

Тесты

Входные данные Выходные данные
[latex]5 \; 2 \; 3 \; 1[/latex] [latex]4[/latex]
[latex]6 \; 3 \; 4 \; 3[/latex] [latex]9[/latex]
[latex]10 \; 5 \; 10 \; 2[/latex] [latex]48[/latex]

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

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

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

Ссылки

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

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

Задача

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

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

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

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

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

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

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

Тесты

Входные данные Выходные данные
[latex]x_a[/latex] [latex]y_a[/latex] [latex]z_a[/latex] [latex]x_b[/latex] [latex]y_b[/latex] [latex]z_b[/latex] [latex]x_c[/latex] [latex]y_c[/latex] [latex]z_c[/latex] [latex]V[/latex]
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

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

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

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

  1. [latex]V = \frac {|\Delta|} {6}[/latex], где [latex]V[/latex] — объём тетраэдра, а [latex]\Delta[/latex] — определитель матрицы.
  2. [latex]
    \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)
    [/latex].

Итоги:

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

Ссылки

А712

Задача

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

Тесты:

Ввод Вывод (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

Код:

Ссылка на ideone.

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

Код на Java

 

А701б

Условие

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

Тесты

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

Условие:

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

Тесты:

Ввод количества 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 размера [latex]m*n[/latex]. Получить транспонированную матрицу A*(ее размер [latex]n*m[/latex]).

n m А А*
5 4
 5 6
4  3

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

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

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

A699

A699. Даны квадратные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex].Получить матрицу [latex]AB-BA[/latex].
Размер матрицы Матрица А Матрица В Результат
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

Создаем матрицы [latex]A, B, C, D, E,[/latex] где [latex]A[/latex]-первая матрица, [latex]B[/latex]- вторая матрица, [latex]C[/latex]-матрица [latex]AB[/latex], [latex]B[/latex]- матрица [latex]BA[/latex], а [latex]E[/latex]- матрица [latex]AB-BA[/latex]. Вводим с клавиатуры матрица [latex]A[/latex] и [latex]B[/latex], а остальные заполняем нулями. Находим матрицу [latex]C[/latex] и [latex]D[/latex], после чего находим матрицу [latex]E[/latex].

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

А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
Ответ Нету элементов с такими свойствами

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

link

Java

 

А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.

Ю4.9

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

Тесты:

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

Ссылка на код:ссылка

Ход решения:

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

Ю4.10

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

[latex]l[/latex] [latex]m[/latex] [latex]Q\left(l,m \right)[/latex] [latex]\acute{Q}\left(l,m \right)[/latex]
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:

У переменных [latex]l[/latex], [latex]m[/latex] (количество строк и столбцов соответственно) — тип int, т.к. это целые числа.
Массив для данной матрицы [latex]q\left[l \right]\left[m \right][/latex] и массивы элементов суммы [latex]sum\left[l \right][/latex] и среднего арифметического [latex]sr\left[l \right][/latex] каждой строки  имеют тип double, так как могут содержать вещественные числа.

В первом цикле инициализируем элементы массива [latex]sum\left[l \right][/latex] нулями, чтобы там не лежал мусор.

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

В третьем цикле вычитаем из каждого элемента среднее арифметическое строки, в которой он находится, и выводим новое значение элемента на экран.

Задача на Ideone:
C++
Java