e-olymp 8651. Браслети (Bangles)

14/06/2019 by Руслан Масальский

Задача взята з сайту e-olymp

Шпигунам-конкурентам вдалося потрапити на склад запасних частин фірми «Magic & Stupidity», яка виготовляла магічні браслети. Стало зрозуміло, що всі браслети складалися з чотирьох різних деталей, кожна з яких мала на кінцях замки різних типів (розрізнялися за номерами). Вони з’єднувалися по колу, причому у сусідніх частин замки повинні мати однаковий номер. Знайшлося $N$ різних типів замків (позначимо їх номерами від $1$ до $N$) і $М$ типів деталей, які визначаються парою номерів замків (порядок несуттєвий). Напишіть програму, яка б підраховувала скільки існує різних наборів з чотирьох деталей для виготовлення браслетів фірмою «Magic & Stupidity».

Вхідні дані

Програма читає з першого рядка числа $N$ (кількість типів замків) та $M$ (кількість типів деталей). ($4 \leq N \leq 300$). У $M$ наступних рядках наведені параметри деталей (пара номерів замків). Всі пари різні.

Вихідні дані

Програма визначає кількість варіантів браслетів.

Код

#include <iostream>

using namespace std;

typedef long long ll;

const ll INF = 3e2+5;

ll arr[INF][INF];

void power(ll n){

ll arr1[n][n];

for(int i = 0 ; i < n ; i++){

for(int j = 0 ; j < n; j++){

arr1[i][j]=0;

for(int k = 0 ; k < n ; k ++){

arr1[i][j]+=arr[i][k]* arr[k][j];

}

for(int i = 0 ; i < n ; i++){

for(int j = 0 ; j < n; j++){

arr[i][j]=arr1[i][j];

}

int main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

int n,m ;

cin>>n>>m;

ll a,b;

for(int i = 0 ; i < m ; i++){

cin>>a>>b;

a--;

b--;

if(a!=b){

arr[a][b]++;

arr[b][a]++;

}

power(n);

ll to_del[n];

for(int i = 0 ; i < n; i++){

to_del[i]=0;

for(int j = 0 ; j < n; j++){

if(i==j){

arr[i][i] = 0;

}else{

to_del[i]+=arr[i][j];

}

power(n);

ll answer =0;

for(int i = 0 ; i < n ; i++){

answer +=arr[i][i]-to_del[i];

}

cout<<answer/8;

return 0;

}

Рішення

Зробимо ізоморфний перехід в графи, а саме можна помітити, що визначивши типи запків як вершини матимемо зв’язки між типами, як існуючий елемент браслета, тобто пара $(1, 2)$ насправді задає зв’язок між першим і другим типом. Маэмо граф, залишилось знайти кількість простих циклів завдовшки у чотири ребра (чотири вершини).
Построївши матрицю суміжності ми на справді побудували матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за один хід.
Нехай за х ходів ми потрапили з вершини $i$ у вершину $k$ рівно $a$ способами, а з вершини $k$ у вершину $j$ рівно $b$ способами. Тоді за $2x$ ходів ми можемо потрапити з вершини $i$ у вершину $j$ через вершину $k$ рівно $ab$ способами, що насправді еквівалентно возведенню матриці суміжності у степінь, яка дорівнює кількості ходів
Тепер за два перемноження отримаємо матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за 4 ходи. Сумма елементів на головній діагоналі майже дає нам потрібний результат. Нам треба відняти ходи такого типу 1-2-1-2-1 та 1-2-3-2-1. Щоб відняти ходи першого типу після першого перемноження поставимо на головній діагоналі нулі, що означатиме що ми не можемо у другому ході повернутися у ту вершину з якої прибули. Для другого типу треба помітити, що ми йдемо по тому шляху, по якому вже йшли тобто якщо мі за два ходи дійшли до певної вершини $a$ способами, то повертаючись назад отримаємо $2a$ способів, але з них рівно $a$ нам не підходять, тому після другого перемноження с діагоналі видаляємо сумму на ряді на моменті коли було зроблено усього $2$ ходи, звісно не враховуючи елементи на головній діагоналі. Ми будували неорієнтований граф тому сумму на діагоналі треба поділити на $2,$ а ще в наших циклах по $4$ вершини, тому треба ще поділити на 4.

Посилання

ideone
e-olymp

Руслан Масальский

Прикладная математика. Одесский национальный университет им. Мечникова

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

27/02/2019 by Иван Киреев

Задача. Четные отрицательные в матрице

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

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

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

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

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

Тесты

№	Ввод	Вывод
1	3 4 -2 5 1 -4 -12 0 1 -3	3 -18
2	5 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100	25 -2500
3	2 0 0 0 0	0 0
4	3 -2 -1 -1 -1 -2 -1 -1 -1 -2	3 -6
5	2 6 8 12 100	0 0
6	4 -25 0 12 5 -29 47 23 15 11 100 -89 20 55 25 42 -12	1 -12
7	2 -12 -12 -12 -12	4 -48

Решение

При обработке двумерного массива я использовал один цикл длиной в $n^2$ витков.
В нём я обращался к элементам с помощью целого и остатка от деления на $n$, то есть изменял второй индекс заново через каждые $n$ элементов, увеличивая, при таком переходе, первый индекс на единицу.
Используя этот приём я избежал вложенных циклов и просматривал элементы в том же порядке, как если бы их использовал.

Код

#include <iostream>

using namespace std;

int main() {

short n, count = 0, summ = 0, mat[100][100];

cin >> n;

for (int i = 0; i < n * n; i++)

cin >> mat[i / n][i % n];

for (int i = 0; i < n * n; i++) {

short elem = mat[i / n][i % n];

if (elem % 2 == 0 && elem < 0) {

count++;

summ += elem;

}

cout << count << ' ' << summ;

return 0;

}

Иван Киреев

e-olymp 8524. Сумма положительных в матрице

24/12/2018 by Богдан Подгорный

Задача взята с сайта e-olymp

Условие

Задана матрица размера [latex]n\times n[/latex]. Найдите сумму ее положительных элементов.

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

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

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

Выведите сумму положительных элементов матрицы.

Тесты

№	Inputs	Outputs
1	3 4 -2 5 1 -4 -12 0 1 -3	11
2	4 -4 -2 -5 -7 -1-14 -4 -12 -12 -1 -3 -53	0
3	3 0 0 0 0 1 0 0 0 0	1
4	0	0
5	5 89 76 54 32 33 46 57 89 40 32 12 45 63 78 65 13 76 54 89 67 13 67 89 90 43	1412

Код

#include <iostream>

using namespace std;

int main() {

int n, a, sum = 0;

cin >> n;

for(int i = 0; i < n*n; i++)

cin >> a;

if(a > 0){

sum += a;

}

cout << sum;

return 0;

}

Решение

В условии сказано, что задана матрица размера [latex]n\times n[/latex], тогда вводов тоже будет, соответственно, [latex]n\cdot n[/latex]. В цикле ввода используется условный оператор для проверки на то, положительно число или нет.

Ссылки

Богдан Подгорный

e-olymp 1482. Умножение матриц

25/06/2018 by Томас Пасенченко

Задача

Пусть даны две прямоугольные матрицы $A$ и $B$ размерности $m \times n$ и $n \times q$ соответственно:
$$A = \begin{bmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{bmatrix} \; , \; B = \begin{bmatrix} b_{11} & b_{12} & \ldots & b_{1q} \\ b_{21} & b_{22} & \ldots & b_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \ldots & b_{nq} \end{bmatrix} .$$
Тогда матрица $C$ размерностью $m \times q$ называется их произведением:
$$C = \begin{bmatrix} c_{11} & c_{12} & \ldots & c_{1q} \\ c_{21} & c_{22} & \ldots & c_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \ldots & c_{mq} \end{bmatrix} ,$$
где: $$c_{i,j} = \sum_{r=1}^{n} a_{i,r}b_{r,j} \; \left(i = 1, 2, \ldots m; j = 1, 2, \ldots q\right).$$
Операция умножения двух матриц выполнима только в том случае, если число столбцов в первом сомножителе равно числу строк во втором; в этом случае говорят, что форма матриц согласована.

Задано две матрицы $A$ и $B$. Найти их произведение.

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

В первой строке задано $2$ натуральных числа $n_a$ и $m_a$ – размерность матрицы $A$. В последующих $n_a$ строках задано по $m_a$ чисел – элементы $a_{ij}$ матрицы $A$. В $\left(n_a + 2\right)$-й строке задано $2$ натуральных числа $n_b$ и $m_b$ – размерность матрицы $B$. В последующих $n_b$ строках задано по $m_b$ чисел – элементы $b_{ij}$ матрицы $B$. Размерность матриц не превышает $100 \times 100$, все элементы матриц целые числа, не превышающие по модулю $100$.

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

В первой строке вывести размерность итоговой матрицы $C$: $n_с$ и $m_c$. В последующих $n_с$ строках вывести через пробел по $m_c$ чисел – соответствующие элементы $c_{ij}$ матрицы $C$. Если умножать матрицы нельзя — в первой и единственной строке вывести число $\; -1$.

Тесты

Входные данные	Выходные данные
2 3 1 3 4 5 -2 3 3 3 1 3 2 2 1 3 0 -1 1	2 3 7 2 15 1 10 7
3 3 1 5 3 2 6 1 7 -1 -3 3 2 3 6 -1 1 3 1	3 2 7 14 3 19 13 38
4 4 4 8 -18 16 3 7 14 -42 2 1 1 7 4 9 5 -2 4 4 1 0 0 0 0 1 0 0 0 0 1 0	4 4 4 8 -18 16 3 7 14 -42 2 1 1 7 4 9 5 -2
3 3 5 7 -1 8 9 3 0 -6 17 2 3 7 -15 1 8 8 2	-1
2 3 57 -49 31 89 11 -37 3 1 19 -19 0	2 1 2014 1482

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

#include <iostream>

using namespace std;

int main() {

int na, ma, nb, mb;

cin >> na >> ma;

int **a = new int *[na];

for (int i = 0; i < na; i++) {

a[i] = new int[ma];

}

for (int i = 0; i < na; i++) {

for (int j = 0; j < ma; j++) {

cin >> a[i][j];

}

cin >> nb >> mb;

// Проверяем возможность вычисления произведения матриц

if (ma != nb) {

cout << -1;

return 0;

}

int **b = new int *[nb];

for (int i = 0; i < nb; i++) {

b[i] = new int[mb];

}

for (int i = 0; i < nb; i++) {

for (int j = 0; j < mb; j++) {

cin >> b[i][j];

}

int **c = new int *[na];

for (int i = 0; i < na; i++) {

c[i] = new int[mb];

}

// Вычисляем произведение

for (int i = 0; i < na; i++) {

for (int j = 0; j < mb; j++) {

for (int r = 0; r < ma; r++) {

c[i][j] += a[i][r] * b[r][j];

}

// Выводим результат

cout << na << " " << mb << "\n";

for (int i = 0; i < na; i++) {

for (int j = 0; j < mb; j++) {

cout << c[i][j];

if (j + 1 != mb) cout << " ";

}

cout << "\n";

}

return 0;

}

Решение

Для начала, считываем данные матрицы $A$ из входного потока и записываем их в двумерный динамический массив. Далее, получив данные о размерности второй матрицы, мы можем определить, выполнима ли операция умножения, и если нет, то прервать выполнение программы. Если операция умножения данных матриц выполнима, то считываем и записываем данные второй матрицы, после чего, по приведённой выше формуле вычисляем произведение матриц $C = A \times B.$ Наконец, выводим полученную матрицу $C.$

Ссылки

Условие задачи на e-olymp
Код задачи на ideone
Умножение матриц на Wikipedia

Томас Пасенченко

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

24/02/2018 by Данила Савчак

Задача

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

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

Первая строка содержит целые числа [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

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

#include <iostream>

#define Unknown 1001

using namespace std;

int main() {

int n, m,uf = 0,maxi;

//input

cin >> n >> m;

int ** x = new int * [n];

for (int i = 0; i < n; i++)

x[i] = new int[m];

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

cin >> x[i][j];

//workspace

int max[m];

for (int i = 0; i < m; i++){

max[i] = Unknown;

}

for (int i = 0; i < n; i++) {

int min = x[i][0];

for (int j = 1; j < m; j++) {

if ( min > x[i][j] ) {

min = x[i][j];

}

for (int j = 0; j < m; j++) {

if (x[i][j] == min) {

if (max[j] != Unknown){

maxi = max[j];

}

else {

maxi = x[i][j];

for (int l = 0; l < n; l++) {

if (maxi < x[l][j]){

maxi = x[l][j];

}

max[j] = maxi;

}

if ( maxi == min) {

uf++;

}

//output

cout << uf;

return 0;

}

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

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

Ссылки

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

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

Данила Савчак

ML30. Объём параллелепипеда

29/10/2016 by Оля Вдовиченко

Задача. Найти объём параллелепипеда три стороны которого образованы векторами [latex] \overrightarrow{a}=(a_x,a_y,a_z),[/latex] [latex]\overrightarrow{b}=(b_x,b_y,b_z)[/latex] и [latex]\overrightarrow{c}=(c_x,c_y,c_z).[/latex]

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

Выходные данные: Объём параллелепипеда.

Тесты

Входные данные	Выходные данные
0 0 1 0 1 0 1 0 0	1
0 0 0 1 0 0 0 0 1	0
1 0 0 0 0 1 0 0 1	0
2 5 3 4 1 0 -2 7 6	18
3 5 1 0 -7 2 6 -4 5	21

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

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double ax, ay, az, bx, by, bz, cx, cy, cz, V, V1;

cin >> ax >> ay >> az >> bx >> by >> bz >> cx >> cy >> cz; //Ввод координат векторов.

V = (ax*((by*cz)+(cy*bz)))-ay*((bx*cz)+(cx*bz))+az*((bx*cy)+(cx*by)); //Вычисление объёма.

cout << abs(V); //Выводим модуль значения определителя.

return 0;

}

Решение

Для решения данной задачи можно составить матрицу и вывести из неё формулу для нахождения определителя:
[latex]\triangle = \begin{vmatrix}a_x & a_y & a_z \\ b_x & b_y & b_z \\ c_x & c_y & c_z\end{vmatrix} =[/latex] [latex] a_x \left(b_y c_z+c_y b_z\right)[/latex] [latex]-a_y \left(b_x c_z+c_x b_z\right)+[/latex] [latex]a_z\left(b_x c_y+c_x b_y\right).[/latex]

Модуль определителя матрицы равен объёму параллелепипеда.

Решение на ideone.

Оля Вдовиченко

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

28/09/2016 by Вадим Гордийчук

Задача

Найти объём тетраэдра три стороны которого образованы векторами [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

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

#include <iostream>

using namespace std;

int main()

{

double Ax, Ay, Az, Bx, By, Bz, Cx, Cy, Cz, V;

cin >> Ax >> Ay >> Az >> Bx >> By >> Bz >> Cx >> Cy >> Cz; //Считывание координат векторов.

V = (Ax * (By * Cz - Bz * Cy) - Bx * (Ay * Cz - Az * Cy) + Cx * (Ay * Bz - Az * By)) / 6.0; //Подсчитывание объёма.

if (V < 0) V *= -1; //Определитель матрицы может быть отрицательным числом, объём - нет. Поэтому если объём отрицательный, умножаем его на -1.

cout << V; //Вывод объёма.

}

import java.util.*;

public class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

double

Ax = in.nextDouble(),

Ay = in.nextDouble(),

Az = in.nextDouble(),

Bx = in.nextDouble(),

By = in.nextDouble(),

Bz = in.nextDouble(),

Cx = in.nextDouble(),

Cy = in.nextDouble(),

Cz = in.nextDouble();

double V = (Ax * (By * Cz - Bz * Cy) - Bx * (Ay * Cz - Az * Cy) + Cx * (Ay * Bz - Az * By)) / 6.0;

if (V < 0) V *= -1;

System.out.print(V);

}

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

Так как тетраэдр построен на векторах [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], для данной задачи оптимальным решением будет использовать следующие формулы:

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

Ссылки

Вадим Гордийчук

А406

18/12/2015 by Сабиров Ильдар

Задача

С помощью [latex]x_{ij}, i=1,2; j=1,\ldots,n.[/latex] — действительной матрицы на плоскости задано n точек так, что [latex]x_{1j}, x_{2j}[/latex] — координаты [latex]j[/latex] — точки. Точки попарно соединены отрезками. Найти длину наибольшего отрезка.

Тест

n	Матрица [latex]x_{ij}, i=1,2.[/latex]	Длина наибольшего отрезка	Комментарий
3	2 8 4 9 1 5	10	Пройдено
4	6 14 2 1 9 3 8 0	13.3417	Пройдено
5	1 8 4 3 7 2 9 5 0 11	11.7047	Пройдено

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

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double max = 0;

int K=2,L,x=0,y=1;

cin >> L;

int D[K][L];

for (int i = 0; i < K; i++)

{

for (int j = 0; j < L; j++)

{

cin>>D[i][j];

}

for (int i = 0; i < L-1; i++)

{

for (int j = 0; j < L; j++)

{

double q=sqrt((D[x][i]-D[x][j])*(D[x][i]-D[x][j])+(D[y][i]-D[y][j])*(D[y][i]-D[y][j]));

if(q>max)

{

max=q;

}

for (int i = 0; i < K; i++)

{

for (int j = 0; j < L; j++)

{

cout<<D[i][j]<<" ";

}

cout<<"\n";

}

cout<<max;

return 0;

}

Ход решения:

Вводим матрицу построчно (не очень удобно).
Находим длину наибольшего отрезка.
С помощью вложенных циклов мы находим длины всех отрезков по формуле
[latex] AB=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}, A(x_{1},y_{1}), B(x_{2},y_{2}). [/latex]
По алгоритму нахождения максимума находим длину наибольшего отрезка.
Выводим матрицу.
Выводим длину наибольшего отрезка.
Ссылка на код

Сабиров Ильдар

Ю4.12

14/09/2015 by Сабиров Ильдар

Задача: Все ненулевые элементы матрицы [latex]D(k,l)[/latex] расположить в начале массива [latex]E(k \times l)[/latex] и подсчитать их количество.

K	L	Матрица D	Ненулевые элементы матрицы E	Количество ненулевых элементов
2	3	2 7 0 1 4 9	2 7 1 4 9	5
3	4	6 7 4 2 9 0 1 3 0 8 0 19	6 7 4 2 9 1 3 8 19	9
4	2	8 9 0 1 5 2 7 26	8 9 1 5 2 7 26	8

#include <iostream>

#include <stdlib.h>

#include <ctime>

using namespace std;

int main() {

int K;

int L;

cin>>K;

cin>>L;

int M=K*L;

int D[K][L];

int E[M];

int count = 0;

for (int i = 0; i < K; ++i) {

for (int j = 0; j < L; ++j) {

cin>>D[i][j];

if (D[i][j] != 0) {

E[count++] = D[i][j];

cout << D[i][j] << " ";

}

cout << " количество ненулевых элементов матрицы E = " << count << endl;

for (int u = 0; u < K; ++u) {

for (int y = 0; y < L; ++y) {

cout<<D[u][y]<<" ";

}

cout<<"\n";

}

return 0 ;

}

Заполняем матрицу с клавиатуры посредством циклов.
Выводим ненулевые элементы.
Выводим их количество.
Выводим матрицу D.

Ссылка на код

Сабиров Ильдар

А705

29/06/2015 by Кібакова Надія Олександрівна

Задача:
Даны квадратные матрицы [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++

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n; //ввод из стандартного потока

int A[n][n];

int B[n][n];

int Z[n][n];

int H[n][n];

int E[n][n];

float C[n][n];

float Ans[n][n];

for (int i = 0; i < n; i++){ //матрица А

for (int j = 0 ; j < n ; j++){

cin >> A[i][j];

}

for (int i = 0; i < n; i++){ //матрица В

for (int j = 0 ; j < n ; j++){

cin >> B[i][j];

}

for (int i = 0; i < n; i++){ //единичная матрица Е

for (int j = 0 ; j < n ; j++){

if (i == j) E[i][j] = 1;

else E[i][j] = 0;

}

for (int i = 0; i < n; i++){ //разность матриц В и Е

for (int j = 0; j < n; j++){

Z[i][j] = 0;

Z[i][j] = B[i][j] - E[i][j];

}

for (int i = 0; i < n; i++){ //умножение матриц А и (В - Е)

for (int j = 0; j < n; j++){

H[i][j] = 0;

for (int t = 0; t < n; t++){

H[i][j] += A[i][t] * Z[t][j];

}

for (int i = 0; i < n; i++){ //матрица С

for (int j = 0; j < n; j++){

C[i][j] = 0;

C[i][j] = 1.0/(i+1 + j+1);

}

for (int i = 0; i < n; i++){ //матрица A(B–E)+C

for(int j = 0; j < n; j++){

Ans[i][j] = H[i][j] + C[i][j];

printf("%1.2f", Ans[i][j]);

cout << " " ;

}

cout << endl;

}

return 0;

}

Код C++ на Ideone: A705

Код Java

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) throws java.lang.Exception {

Scanner read = new Scanner (System.in);

int n = read.nextInt(); //ввод из стандартного потока

double A[][] = new double [n][n];

double B[][] = new double [n][n];

double Z[][] = new double [n][n];

double H[][] = new double [n][n];

double E[][] = new double [n][n];

double C[][] = new double [n][n];

double Ans[][] = new double [n][n];

for (int i = 0; i < n; i++){ //матрица А

for (int j = 0 ; j < n ; j++){

A[i][j] = read.nextDouble();

}

for (int i = 0; i < n; i++){ //матрица В

for (int j = 0 ; j < n ; j++){

B[i][j] = read.nextDouble();

}

for (int i = 0; i < n; i++){ //единичная матрица Е

for (int j = 0 ; j < n ; j++){

if (i == j) E[i][j] = 1;

else E[i][j] = 0;

}

for (int i = 0; i < n; i++){ //разность матриц В и Е

for (int j = 0; j < n; j++){

Z[i][j] = 0;

Z[i][j] = B[i][j] - E[i][j];

}

for (int i = 0; i < n; i++){ //умножение матриц А и (В - Е)

for (int j = 0; j < n; j++){

H[i][j] = 0;

for (int t = 0; t < n; t++){

H[i][j] += A[i][t] * Z[t][j];

}

for (int i = 0; i < n; i++){ //матрица С

for (int j = 0; j < n; j++){

C[i][j] = 0;

C[i][j] = 1.0/((i+1)+(j+1));

}

for (int i = 0; i < n; i++){ //матрица A(B–E)+C

for(int j = 0; j < n; j++){

Ans[i][j] = H[i][j] + C[i][j];

System.out.print(Ans[i][j] + " ");

}

System.out.println();

}

Код 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

Кібакова Надія Олександрівна

А700в

19/06/2015 by Янішевська Альона Русланівна

Задача. Дана квадратная матрица А порядка n. Получить матрицу AB; элементы матрицы B вычисляются по формуле:

[latex]b_{ij}=\left\{\begin{matrix}\frac{1}{i+j-1}&,if\: i<j\\ 0&,if\: i=j\\-\frac{1}{i+j-1}&other\: case\end{matrix}\right.[/latex]

[latex](i,j=1,\cdots, n)[/latex]

Тесты:

Размер матрицы	Входные данные	Результат	Комментарий
n=2	[latex]\begin{pmatrix}1&7\\3&2\end{pmatrix}[/latex]	[latex]\begin{pmatrix}-3,5&0,5\\-1&1,5\end{pmatrix}[/latex]	Пройден
n=3	[latex]\begin{pmatrix}1&2&3\\7&6&5\\4&8&9\end{pmatrix}[/latex]	[latex]\begin{pmatrix}-2&-0,25&0,83333\\-4,66667&2,25&3,83333\\-7&-0,25&3,333\end{pmatrix}[/latex]	Пройден

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

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

double A[n][n];

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

cin >> A[i][j];

}

double B[n][n];

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

B[i][j] = 0;

if (i < j){B[i][j] = 10 * 0.1 / ((i+1) + (j+1) -1);}

else {

if (i == j){B[i][j] = 0;}

else {B[i][j] = -10 * 0.1 / ((i+1) + (j+1) -1);}

}

double C[n][n];

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

C[i][j] = 0;

for(int k = 0; k < n; k++){

C[i][j] += A[i][k] * B[k][j];

}

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

cout << C[i][j] << " ";

}

cout << endl;

}

return 0;

}

После ввода матрицы A, мы должны найти элементы матрицы B. Из условия задачи: [latex]b_{ij}=\left\{\begin{matrix}\frac{1}{i+j-1}&,if\: i<j\\ 0&,if\: i=j\\-\frac{1}{i+j-1}&other\: case\end{matrix}\right.[/latex] , при [latex](i,j=1,\cdots, n)[/latex].

Для нахождения [latex]b_{ij}[/latex] используется условный оператор if в цикле for. Матрица C — результат умножения матрицы A на матрицу B, которое также производим в цикле for.

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

Решение на Java:

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

double A[][];

A = new double [n][];

for(int i=0; i<n; i++){

A[i] = new double [n];

for(int j=0; j<n; j++){

A[i][j] = in.nextDouble();

}

double B[][];

B = new double [n][];

for(int i=0; i<n; i++){

B[i] = new double [n];

for(int j=0; j<n; j++){

B[i][j]=0;

if (i<j){

B[i][j]=10*0.1/((i+1)+(j+1)-1);

}

else{

if (i==j){

B[i][j]=0;

}

else {

B[i][j]=-10*0.1/((i+1)+(j+1)-1);

}

double C[][];

C = new double [n][];

for(int i=0; i<n; i++){

C[i] = new double [n];

for(int j=0; j<n; j++){

C[i][j]=0;

for(int k=0; k<n; k++){

C[i][j]+=A[i][k]*B[k][j];

}

for(int i=0; i<n; i++){

for(int j=0; j<n; j++){

System.out.print(C[i][j]+" ");

}

System.out.println();

}

Ссылка на решение.

Янішевська Альона Русланівна

А719б

17/06/2015 by Іванов Вячеслав Володимирович

Условие

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

Решение

Безусловно, по входным данным можно восстановить матрицы, тривиальным образом их перемножить и вывести результат в заданном виде. Как пример плохого стиля программирования: наивный алгоритм приводит к почти двукратному перерасходу потребляемой памяти и существенно уступает в производительности. Существует другое решение, прийти к которому можно путем последовательного приспособления стандартных матричных операций к формату входных данных.

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

Замечание 1

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

Пример

[latex] \left(\begin{array}{ccc} 1 & 1 & 3 \\ 1 & 4 & 5 \\ 3 & 5 & 0\end{array} \right) \cdot \left( \begin{array}{ccc} 4 & 0 & 0 \\ 0 & 4 & 3 \\ 0 & 3 & 2 \end{array} \right) = \left( \begin{array}{ccc} 4 & 13 & 9 \\ 4 & 31 & 22 \\ 12 & 20 & 15 \end{array} \right)[/latex]

Замечание 2

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

Во всех дальнейших выкладках подразумевается, что матрица представлена линейным массивом из [latex]\frac{n(n+1)}{2}[/latex] элементов.

Для начала, заметим, что элемент [latex]c_{i,j}[/latex] матрицы [latex]C=A^{2}[/latex], равен скалярному произведению (как векторов в стандартном базисе) [latex]i[/latex]-ой строки матрицы [latex]A[/latex] на [latex]j[/latex]-ую её строку (в силу того, что в симметричной матрице [latex]j[/latex]-ая строка совпадает с [latex]j[/latex]-м столбцом). Следовательно, для возведения в степень симметричной матрицы необходимо и достаточно реализовать операцию скалярного перемножения двух её строк.

Тогда следует понять, как по данному представлению матрицы получить её [latex]i[/latex]-ую строку. Для удобства, выпишем имеющиеся элементы в виде полной матрицы. Заметим, что первым элементом [latex]i[/latex]-ой строки будет [latex]i[/latex]-ый элемент первой строки, и обобщим это наблюдение. Обозначим позицию текущего интересующего нас элемента [latex]i[/latex]-ой строки как [latex]j[/latex]. Если [latex]j < i[/latex], то следует выбрать [latex]i[/latex]-ый элемент [latex]j[/latex]-ой строки, иначе следует выбрать все элементы [latex]j[/latex]-ой строки, лежащие правее данного. Графически можно интерпретировать алгоритм таким образом: начиная с [latex]i[/latex]-го элемента первой строки, спускаться вертикально вниз по матрице до тех пор, пока не будет достигнута [latex]i[/latex]-ая строка, далее — двигаться вправо до конца строки. Наглядность алгоритма позволяет легко воплотить его программно.
Следует только пронаблюдать, как изменяются расстояния между элементами, лежащими один под другим, при движении вниз по строкам матрицы, что позволит легко перенести алгоритм на линейное представление верхней треугольной матрицы. Предлагаем читателю самому проделать это несложное, но наглядное упражнение, для лучшего понимания алгоритма.

Теперь можно перейти непосредственно к реализации.

Тесты

[latex]n[/latex]	[latex]A[/latex]	[latex]B[/latex]	[latex]A^{2}-B^{2}[/latex]
2	1 2 5	7 4 8	-60 -48 -51
4	1 7 3 -2 3 1 9 2 8 11	4 5 11 -3 4 -7 22 1 4 0	-108 116 -8 -79 -434 -10 75 -109 290 -239

Реализация

ideone: http://ideone.com/Dyte8l

100

101

102

103

104

105

106

107

108

109

110

#include <bits/stdc++.h>

using namespace std;

//Симметричная квадратная матрица порядка n задана линейным набором из

//n(n+1)/2 элементов. Все методы класса оперируют только с таким представлением.

template <typename T>

class symmetric_matrix{

private:

T* data;

int data_size;

public:

//Конструкторы.

symmetric_matrix(){}

symmetric_matrix(int n){

data = new T[(n*(n+1))/2];

data_size = n;

}

symmetric_matrix(int n, int value){

data = new T[(n*(n+1))/2];

for(int i = 0; i < (n*(n+1))/2; i++)

data[i] = value;

data_size = n;

}

//Методы.

int size(){ return data_size; }

T get(int pos){ return data[pos]; }

void set(int pos, T value){ data[pos] = value; }

//Подпространство симметричных квадратные матриц заданного порядка

//не замкнутно относительно операции матричного умножения.

//Тем не менее, при возведение матрицы в степень замкнутость не

//нарушается, в связи с чем операция умножения реализована для него.

symmetric_matrix<T> operator *(symmetric_matrix<T> B){

int n = data_size;

symmetric_matrix<T> C(n);

int curr = 0;

for(int row = 0; row < n; row++){ //row

for(int col = row; col < n; col++){ //col

int rpos = row, cpos = col; //(row, col)

int rstep = n-1, cstep = n-1; //row, col step

for(int i = 0; i < n; i++){

C.set(curr, C[curr] + data[rpos]*B[cpos]);

rpos += (rstep >= n-row)*(rstep - 1) + 1;

cpos += (cstep >= n-col)*(cstep - 1) + 1;

rstep--, cstep--;

}

curr++;

}

return C;

}

//Операторы.

T operator [](int pos){return data[pos];}

symmetric_matrix<T> operator +(symmetric_matrix<T> B){

int n = B.size();

symmetric_matrix<T> C(n);

for(int i = 0; i < (n*(n+1))/2; i++)

C.set(i, data[i] + B[i]);

return C;

};

symmetric_matrix<T> operator -(symmetric_matrix<T> B){

int n = B.size();

symmetric_matrix<T> C(n);

for(int i = 0; i < (n*(n+1))/2; i++)

C.set(i, data[i] - B[i]);

return C;

};

//Бинарный алгоритм возведения матрицы в степень.

template <typename T>

symmetric_matrix<T> power(symmetric_matrix<T> A, int n){

symmetric_matrix<T> result(A.size());

//Изначально result - нейтральный элемент относительно умножения

//т.е. единичная матрица.

for(int i = 0, diag = 0; i < A.size(); i++){

result.set(diag, 1);

diag += A.size()-i;

}

while(n){

if(n & 1)

result = result * A;

A = A * A;

n >>= 1;

}

return result;

}

int main(){

int n; cin >> n;

symmetric_matrix<int> A(n), B(n), C(n);

//Считывание данных

for(int i = 0; i < (n*(n+1))/2; i++){

int value; cin >> value;

A.set(i, value);

}

for(int i = 0; i < (n*(n+1))/2; i++){

int value; cin >> value;

B.set(i, value);

}

C = power(A, 2) - power(B, 2);

for(int i = 0; i < (n*(n+1))/2; i++){

cout << C.get(i) << " ";

}

return 0;

}

Тесты

Детали реализации

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

Формулировка задачи не оговаривает тип элементов матрицы, так что класс [latex]symmetric\_matrix[/latex] является шаблоном, пригодным для типов данных, поддерживающих операции сложения, вычитания и умножения (соответствующие операторы определены внутри класса).
Алгоритм бинарного возведения матрицы в степень полезен при решении более широкого круга задач, в связи с чем также реализован. При необходимости, программа легко обобщается на большие степени матрицы.
Предусмотрены три типа конструкторов: конструктор по умолчанию и два параметрических конструктора, один из которых позволяет заполнить матрицу некоторым наперед заданным значением.
Для удобства работы с заданным представлением данных, добавлен синтаксический сахар: перегружен оператор [latex][][/latex], осуществляющий доступ к заданному элементу матрицы в линейном её представлении.

Іванов Вячеслав Володимирович

А717б

24/05/2015 by Вустянюк Ігор Дмитрович

Условие

Две правые треугольные матрицы [latex] A [/latex] и [latex] B [/latex] порядка [latex] n [/latex] заданы в виде последовательности [latex] \frac{\left( n + 1 \right) n}{2}[/latex] чисел: сначала идёт [latex] n [/latex] элементов первой строки, затем [latex] n-1 [/latex] элемент второй строки, и т.д. (из последней, [latex] n [/latex] -ой строки берётся только [latex] n [/latex] -ый элемент). Нужно получить в аналогичном виде матрицу

б) [latex] A \left( I + B^{2} \right) [/latex], где [latex] I [/latex] — единичная матрица порядка [latex] n [/latex]

Тест

[latex] \begin{bmatrix} 2 & 2 & 2 \\ 0 & 0 & 3 \\ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{bmatrix} = \begin{bmatrix} 4 & 54 & 236 \\
0 & 0 & 111 \\
0 & 0 & 37 \end{bmatrix} [/latex]

Решение

Создадим класс для работы с треугольными матрицами указанного вида и снабдим его основными методами, необходимыми для решения задачи.

У нас будут конструктор матрицы из стандартного потока ввода, конструктор скалярной матрицы, а также будут перегружены операторы сложения, умножения и присваивания.

Код на С++

#include <iostream>

#include <assert.h>

#include <stdlib.h>

using namespace std;

class TriMat {

private:

int Size;

int** M;

public:

TriMat(int n) {

Size = n;

M = (int**) malloc(Size * sizeof(int));

for (int k = 0; k < Size; k++) {

M[k] = (int*) malloc((Size - k) * sizeof(int));

for (int j = 0; j <= Size - 1 - k; j++)

cin >> M[k][j];

}

// Конструктор скалярной матрицы с заданным элементом на главной диагонали

TriMat(int n, int a) {

Size = n;

M = (int**) malloc(Size * sizeof(int));

for (int k = 0; k < Size; k++) {

M[k] = (int*) malloc((Size - k) * sizeof(int));

M[k][0] = a;

}

void print() {

for (int k = 0; k < Size; k++) {

for (int j = 0; j < k; j++)

cout << "\t";

for (int j = 0; j <= Size - 1 - k; j++)

cout << M[k][j] << "\t";

cout << endl;

}

int* operator[](size_t k) {

assert(0 <= k && k < Size);

return M[k];

}

void assign(int i, int j, int a) {

assert(0 <= i && i < Size && 0 <= j && j < Size);

M[i][j] = a;

}

int el(int i, int j) {

assert(0 <= i && i < Size && 0 <= j && j < Size);

return M[i][j];

}

TriMat operator+ (TriMat B) {

TriMat C(Size);

for (int k = 0; k < Size; k++)

for (int j = 0; j <= Size - 1 - k; j++)

C[k][j] = M[k][j] + B[k][j];

return C;

}

TriMat operator= (TriMat B) {

for (int k = 0; k < Size; k++)

for (int j = 0; j <= Size - 1 - k; j++)

M[k][j] = B[k][j];

return *this;

}

TriMat operator* (TriMat B) {

TriMat C(Size);

for (int k = 0; k < Size; k++)

for (int j = k; j < Size; j++) {

for (int r = k; r <= j; r++)

C[k][j-k] += M[k][r-k] * B[r][j-r];

}

return C;

}

};

int main() {

int n;

cin >> n;

TriMat A(n), B(n), I(n,1), C = A * (I + B*B);

A.print();

B.print();

C.print();

return 0;

}

Ideone (C++)

Код на Java

import java.util.*;

import java.lang.*;

import java.io.*;

class Trimat {

int Size;

int[][] M;

public Trimat(int n, Scanner in) {

Size = n;

M = new int[Size][];

for (int k = 0; k < Size; k++) {

M[k] = new int[Size - k];

for (int j = 0; j < Size - k; j++)

M[k][j] = in.nextInt();

}

public Trimat(int n, int a) {

Size = n;

M = new int[Size][];

for (int k = 0; k < Size; k++) {

M[k] = new int[Size - k];

M[k][0] = a;

}

public void print() {

for (int k = 0; k < Size; k++) {

for (int j = 0; j < k; j++)

System.out.print("\t");

for (int j = 0; j < Size - k; j++)

System.out.format("%d\t", M[k][j]);

System.out.println();

}

public Trimat add(Trimat B) {

Trimat C = new Trimat(Size, 0);

for (int k = 0; k < Size; k++)

for (int j = 0; j < Size - k; j++)

C.M[k][j] = M[k][j] + B.M[k][j];

return C;

}

public Trimat mul(Trimat B) {

Trimat C = new Trimat(Size, 0);

for (int k = 0; k < Size; k++)

for (int j = k; j < Size; j++)

for (int r = k; r <= j; r++)

C.M[k][j-k] += M[k][r-k] * B.M[r][j-r];

return C;

}

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

Trimat A = new Trimat(n, in), B = new Trimat(n, in);

Trimat I = new Trimat(n,1);

Trimat C = A.mul(I.add(B.mul(B)));

A.print();

B.print();

C.print();

}

Ideone (Java)

Вустянюк Ігор Дмитрович

A711a

20/05/2015 by Калачьов Андрій Сергійович

Задача: Дана матрица [latex]A [/latex] размера [latex]m\times m [/latex]. Получить матрицу [latex]AA^{*} [/latex] (ее размер [latex]m\times m [/latex]).

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

1	2	3	4
5	6	7	8
9	0	1	2
3	4	5	6

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

30	70	20	50
70	174	68	122
20	68	86	44
50	122	44	86

Решение:

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

#include <iostream>

using namespace std;

int main() {

int n;

cin>>n;

double x[n][n],y[n][n],z[n][n],mu=0;

for (int i = 0; i < n; i++){

for (int j = 0; j < n; j++){

cin>>x[i][j];

y[j][i]=x[i][j];

}

for (int i = 0; i < n; i++){

for (int j = 0; j < n; j++){

for (int p = 0; p < n; p++){

mu += x[i][p]*y[p][j];

}

z[i][j] = mu;

mu = 0;

}

for (int i = 0; i < n; i++){

for (int j = 0; j < n; j++){

cout<<z[i][j]<<" ";

}

cout<<endl;

}

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

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

double mu=0;

int n=in.nextInt();

double[][] x = new double[n][n];

double[][] y = new double[n][n];

double[][] z = new double[n][n];

for (int i = 0; i < n; i++){

for (int j = 0; j < n; j++){

x[i][j]=in.nextDouble();;

y[j][i]=x[i][j];

}

for (int i = 0; i < n; i++){

for (int j = 0; j < n; j++){

for (int p = 0; p < n; p++){

mu += x[i][p]*y[p][j];

}

z[i][j] = mu;

mu = 0;

}

for (int i = 0; i < n; i++){

for (int j = 0; j < n; j++){

System.out.printf("%.1f ",z[i][j]);

}

System.out.println();

}

Вводим матрицу [latex]A[i][j] [/latex] и матрицу [latex]B[j][i] [/latex] в цикле по [latex] i,j[/latex] от одного до [latex] n[/latex]. Умножаем матрицу [latex] A[/latex] на [latex]A^{*} [/latex].

Калачьов Андрій Сергійович

А714

19/05/2015 by Ковальський Олександр Дмитрович

Задача

Комплексная матрица [latex]Z[/latex] представляется парой [latex]X[/latex], [latex]Y[/latex] действительных матриц так, что [latex]Z=X+iY[/latex]. Даны действительные квадратные матрицы [latex]A[/latex], [latex]B[/latex], [latex]C[/latex] и [latex]D[/latex] порядка [latex]m[/latex]. Найти произведение двух комплексных матриц [latex]A+iB[/latex] и [latex]C+iD[/latex], т. е. найти действительные квадратные матрицы [latex]X[/latex] и [latex]Y[/latex] порядка [latex]m[/latex] такие, что [latex]X+iY=(A+iB)(C+iD)[/latex].

Пример

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

Вывод

9 5 4 8 5 2 6 1 3

1 4 6 5 3 1 9 8 7

4 2 8 3 9 5 1 2 7

5 6 7 4 1 9 3 8 2

16 13 70

9 24 39

-68 -91 -75

99 141 186

96 108 167

110 165 218

Решение

#include <iostream>

using namespace std;

int main()

{

int m;

cin>>m;

int A[m][m], B[m][m], C[m][m], D[m][m];

int X[m][m], Y[m][m];

int el;

for(int i=0;i<m;i++)

for(int j=0;j<m;j++)

cin>>A[i][j];

for(int i=0;i<m;i++)

for(int j=0;j<m;j++)

cin>>B[i][j];

for(int i=0;i<m;i++)

for(int j=0;j<m;j++)

cin>>C[i][j];

for(int i=0;i<m;i++)

for(int j=0;j<m;j++)

cin>>D[i][j];

for(int i=0;i<m;i++)

{

for(int j=0;j<m;j++)

{

el=0;

for(int l=0;l<m;l++)

{

el=el+A[i][l]*C[l][j]-B[i][l]*D[l][j];

}

X[i][j]=el;

}

for(int i=0;i<m;i++)

{

for(int j=0;j<m;j++)

{

el=0;

for(int l=0;l<m;l++)

{

el=el+A[i][l]*D[l][j]+B[i][l]*C[l][j];

}

Y[i][j]=el;

}

cout<<"X:"<<endl;

for(int i=0;i<m;i++)

{

for(int j=0;j<m;j++)

{

cout<<X[i][j]<<" ";

}

cout<<endl;

}

cout<<endl;

cout<<"Y:"<<endl;

for(int i=0;i<m;i++)

{

for(int j=0;j<m;j++)

{

cout<<Y[i][j]<<" ";

}

cout<<endl;

}

return 0;

}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int m = in.nextInt(), el;

int[][] A = new int[m][m], B = new int[m][m], C = new int[m][m], D = new int[m][m],X = new int[m][m], Y = new int[m][m];

for(int i = 0; i < m; i++)

for(int j = 0; j < m; j++)

A[i][j] = in.nextInt();

for(int i = 0; i < m; i++)

for(int j = 0; j < m; j++)

B[i][j] = in.nextInt();

for(int i = 0; i < m; i++)

for(int j = 0; j < m; j++)

C[i][j] = in.nextInt();

for(int i = 0; i < m; i++)

for(int j = 0; j < m;j++)

D[i][j] = in.nextInt();

for(int i = 0; i < m; i++)

{

for(int j = 0; j < m; j++)

{

el = 0;

for(int l = 0;l < m; l++)

{

el += A[i][l] * C[l][j] - B[i][l] * D[l][j];

}

X[i][j] = el;

}

for(int i = 0; i < m; i++)

{

for(int j = 0; j < m; j++)

{

el = 0;

for(int l = 0; l < m; l++)

{

el += A[i][l] * D[l][j] + B[i][l] * C[l][j];

}

Y[i][j] = el;

}

System.out.println("X:");

for(int i = 0; i < m; i++)

{

for(int j = 0; j < m; j++)

{

System.out.printf(X[i][j] + " ");

}

System.out.println();

}

System.out.println();

System.out.println("Y:");

for(int i = 0; i < m; i++)

{

for(int j = 0; j < m; j++)

{

System.out.printf(Y[i][j] + " ");

}

System.out.println();

}

[latex]X+iY=(A+iB)(C+iD)=(AC-BD)+i(AD+BC)[/latex], т. е. [latex]X=AC-BD[/latex], [latex]Y=AD+BC[/latex].

Код на ideone.

Ковальський Олександр Дмитрович

A708

17/05/2015 by Фесенко Катерина Володимирівна

Задача

Даны квадратная матрица [latex]A[/latex] порядка [latex]m[/latex], натуральное число [latex]n[/latex]. Получить матрицу [latex]E+A+A^2+A^3+\dots+A^n,[/latex] где [latex]E[/latex] — единичная матрица порядка [latex]m[/latex].

Тесты

m, n

матрица А

результат

3 3

3 2 1

5 7 3

9 7 3

359 358 158

1028 1047 460

1156 1162 513

2 2

6 7

12 54

127 427

732 3055

Код на языке С++:

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> m >> n;

double a[m][m]; //Исходная матрица

double b[m][m]; //Вспомогательная матрица

double c[m][m]; //Матрица в степени n

double ans[m][m];//Результирующая матрица

for(int i = 0; i < m; i++){

for(int j = 0; j < m; j++){

a[i][j] = b[i][j] = c[i][j] = ans[i][j] = 0; //Очистка памяти

}

for(int i = 0; i < m; i++){

for(int j = 0; j < m; j++){

cin >> a[i][j];

c[i][j] = b[i][j] = ans[i][j] = a[i][j];

}

for(int it = 1; it < n; it++){

//Возводим матрицу в след. степень

for(int i = 0; i < m; i++){

for(int j = 0; j < m; j++){

c[i][j] = 0;

for(int k = 0; k < m; k++){

c[i][j] += a[i][k]*b[k][j];

}

for(int i = 0; i < m; i++){

for(int j = 0; j < m; j++){

ans[i][j] += c[i][j]; //Добавляем к ответу

b[i][j] = c[i][j]; //Заменяем вспомогательную матрицу

}

//Добавляем единичную матрицу

for(int i = 0; i < m; i++){

ans[i][i]++;

}

//Вывод результата

for(int i = 0; i < m; i++){

for(int j = 0; j < m; j++){

cout << ans[i][j] << ' ';

}

cout << endl;

}

return 0;

}

Ссылка на программу:http://ideone.com/3B9ti7

Код на языке Java:

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

Scanner sc = new Scanner (System.in);

int n, m;

m = sc.nextInt();

n = sc.nextInt();

double [][] a = new double [m][m];

double [][] b = new double [m][m];

double [][] c = new double [m][m];

double [][] ans = new double [m][m];

for (int i = 0; i < m; i++) {

for (int j = 0; j < m; j++) {

a[i][j] = sc.nextDouble();

c[i][j] = b[i][j] = ans[i][j] = a[i][j];

}

for (int it = 1; it < n; it++) {

for (int i = 0; i < m; i++) {

for (int j = 0; j < m; j++) {

c[i][j] = 0;

for (int k = 0; k < m; k++) {

c[i][j] += a[i][k] * b[k][j];

}

for (int i = 0; i < m; i++) {

for (int j = 0; j < m; j++) {

ans[i][j] += c[i][j];

b[i][j] = c[i][j];

}

for (int i = 0; i < m; i++) {

ans[i][i]++;

}

for (int i = 0; i < m; i++) {

for (int j = 0; j < m; j++) {

System.out.print(ans[i][j] + " ");

}

System.out.println();

}

Ссылка на программу: http://ideone.com/hOFldD

Решение:

Заводим четыре матрицы: исходную, вспомогательную, матрицу в степени [latex]n[/latex] и результирующую; обнуляем все матрицы, тем самым очищаем память. Дальше возводим матрицу в степень [latex]n[/latex], добавляем к результирующей и заменяем вспомогательную матрицу. В завершении мы прибавим единичную матрицу к ответы и выведем его.

Фесенко Катерина Володимирівна

А706 Алгоритм быстрого возведения в степень

14/05/2015 by Осецимський Анатолій Вадимович

Степень

Входная матрица

Результирующая матрица

0	1
2	3

2	3
6	11

0	1
2	3

6	11
22	39

Пусть даны квадратная матрица [latex]A[/latex] порядка [latex]m[/latex] и натуральное число [latex]n[/latex]; требуется найти [latex]A^{n}[/latex]. Алгоритм, основанный на непосредственной применении формулы [latex]A^{n} = A*A*A…*A [/latex]([latex]n[/latex] сомножителей), слишком разорителен. Например, [latex]A^{4}[/latex] экономичнее вычислять как [latex]A^{2^{2}}[/latex]. Идея одного достаточно экономичного алгоритма вычисления [latex]A^{n}[/latex] заключается в следующем: если [latex]n = 2k[/latex], то [latex]A^{n} = (A^{2})^{k}[/latex]; если же [latex]n = 2k + 1[/latex], то [latex]A^{n} = (A^{2})^{k} * A[/latex]. Степень с показателем [latex]k[/latex] вычисляется с учетом этих же соображений. Итак, надо разделить [latex]n[/latex] на [latex]2[/latex] с остатком:[latex] n = 2k + l [/latex] [latex](0\le l\le 1[/latex]), потом это же проделать с [latex]k[/latex] и т.д. Эти действия приводят, как известно, к построению двоичной записи [latex]n[/latex]. Алгоритм, основанный на этой идее, состоит в том, что последовательно вычисляются [latex]A^{a_{0}}, A^{a_{1}*a_{0}}, …,A^{a_{l}*…*a_{0}}, a_{l}*…*a_{0}[/latex] — двоичная запись числа [latex]n[/latex]. Для этого вычисляется, цифра за цифрой, двоичная запись [latex]n[/latex] и, параллельно, степень за степенью,[latex]A^{(2^{0})}, A^{(2^{1})}, …[/latex] — каждая следующая степень получается из предыдущей возведением в квадрат. Подсчитывается произведение тех из вычисленных степеней, для которых соответствующая цифра двоичного представления равна 1. Например, запись [latex]9[/latex] в двоичной системе есть [latex]1001[/latex][latex](9 = 1*8 + 0*4 + 0*2 + 1)[/latex]; для вычисления [latex]A^{9}[/latex] достаточно найти [latex]A^{2},A^{4},A^{8},[/latex]([latex]3[/latex] умножения), а затем определить [latex]A*A^{8},[/latex] ([latex]1[/latex] умножение).

Преимущество этого алгоритма в сравнении с простейшим состоит в том, что простейший алгоритм требует числа умножений, растущего как линейная функция от [latex]n[/latex], а здесь число умножений грубо говоря, пропорционально количеству цифр числа [latex]n[/latex] или двоичному логарифму [latex]n[/latex]. Это преимущество весьма ощутимо при работе с матрицами (из-за трудоемкости каждого умножения), хотя, разумеется, этот алгоритм может быть использован и для вычисления степени любого числа.

Написать программу, реализующую предположенный алгоритм.

Суть алгоритма была описана в задании. Реализация была через свою структуру данных, такую как матрица. В ней мы определили умножение и присваивание, для удобства. Есть несколько конструкторов, но нужен по сути только самый первый, остальные для разыгравшейся фантазии. Инициализация при создании матрицы обязательна, поскольку может выдавать неправильный ответ в связи с забытым в памяти мусором. Как перемножать матрицы можно узнать здесь. Нам понадобятся три матрицы, исходная, временная и матрица для ответа. Само двоичное представление удобно хранить в строке, поскольку идя по ней и находя [latex]1[/latex] мы можем домножить на временную матрицу матрицу ответ.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

#include <iostream>

#include <string>

#include <vector>

#include <deque>

using namespace std;

class matrix{ //создаем класс матрицы, в основном для красивого перемножения

private:

int n,m;

int long long **arr;

public:

matrix(){

n = 1; m = 1;

}

matrix(int x){

n = x; m = x;

arr = new int long long *[n];

for(int i = 0; i < n; i++){

arr[i] = new int long long [m];

}

for(int j = 0; j < this->n; j++){

for(int k = 0; k < this->m; k++){

arr[j][k] = 0;

}

matrix(int x, int y){

n = x; m = y;

arr = new int long long *[n];

for(int i = 0; i < n; i++){

arr[i] = new int long long [m];

}

for(int j = 0; j < this->n; j++){ // необходимо инициализировать нулями,покольку в памяти может быть забытый мусор

for(int k = 0; k < this->m; k++){

arr[j][k] = 0;

}

} // выше были описанны конструкторы

~matrix(){

for(int i = 0; i < n; i++){

delete arr[i];

}

delete arr;

}// деструктор

void read(){

for(int j = 0; j < this->n; j++){

for(int k = 0; k < this->m; k++){

cin >> arr[j][k];

}

}//функция ввода

void write(){

for(int j = 0; j < this->n; j++){

for(int k = 0; k < this->m; k++){

cout << arr[j][k] << " ";

}

cout << endl;

}

}// функция вывода

void create(int x, int y){

n = x; m = y;

arr = new int long long *[n];

for(int i = 0; i < n; i++){

arr[i] = new int long long [m];

}

}//функция измененияколичества выделяемой под нас памяти

matrix& operator=(const matrix& x){

for(int j = 0; j < this->n; j++){

for(int k = 0; k < this->m; k++){

arr[j][k] = x.arr[j][k];

}

return *this;

}// переопределение оператора присваивания для матриц

const matrix operator*(const matrix& x){

matrix ans(this->n, this->m);

for(int i = 0; i < this->n; i++){

for(int j = 0; j < this->m; j++){

for(int k = 0; k < this->m; k++){

ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];

}

return ans;

}//переопределение умножения для матриц

matrix& operator*=(const matrix& x){

matrix ans(this->n, this->m);

for(int i = 0; i < this->n; i++){

for(int j = 0; j < this->m; j++){

for(int k = 0; k < this->m; k++){

ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];

}

*this=ans;

return *this;

}//переопределение присвоить равно

matrix& pow(int n){

string s;

for(int i = 0; i < sizeof(int)*8 -1; i++){// цикл где мы побитово сдвигаем вправо и умножаем на 1, если в этом бите была 1,то мы добавим в строку 1,если был 0,то 0 конъюнкия 1 будет 0

s+= to_string((n >> i)&1);;

}

int i = s.size()-1; // заводим переменную, в которой будет храниться наивисший разряд двойки

for(; s[i]!= '1'; i--){} //находим этот разряд,двигаясь с конца в поисках первой

matrix ans(this->n,this->m);

for(int j = 0; j < this->n; j++){

for(int k = 0; k < this->m; k++){

if(j == k) ans.arr[j][k] = 1; else ans.arr[j][k] = 0;

}

matrix temp(this->n,this->m);

temp = *this;

for(int j = 0; j <= i; j++){

if(s[j] == '1'){

ans*=temp;

}

temp*=temp;

}

*this=ans;

return *this;

}

};

int main() {

int n,size = 2; string s; //n число,в которую нам надо возвести в степень,размеры матрицы и строка,в которой будем для удобства хранить двоичное представление числа

cin >> n;

matrix mas(size); // создаем матрицу

mas.read();

mas.pow(n);

mas.write();

return 0;

}

link.

Осецимський Анатолій Вадимович

e-olimp 4000. Обход в глубину

30/04/2015 by Ковальський Олександр Дмитрович

Задача e-olimp 4000

Дан неориентированный невзвешенный граф, в котором выделена вершина. Вам необходимо найти количество вершин, лежащих с ней в одной компоненте связности (включая саму вершину).

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

В первой строке содержится два целых числа [latex]n[/latex] и [latex]s[/latex] [latex](1\leq s\leq n\leq 100)[/latex], где [latex]n[/latex] — количество вершин графа, а [latex]s[/latex] — выделенная вершина. В следующих [latex]n[/latex] строках записано по [latex]n[/latex] чисел — матрица смежности графа, в которой цифра «0» означает отсутствие ребра между вершинами, а цифра «1» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

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

Выведите одно число — искомое количество вершин.

Пример:

Входные данные	Выходные данные
5 1	3
0 1 1 0 0
1 0 1 0 0
1 1 0 0 0
0 0 0 0 1
0 0 0 1 0

Решение

#include <iostream>

#include <stack>

using namespace std;

int main()

{

int n;

int s;

cin>>n>>s;

s--;

int matrix[n][n];

stack<int> st;

int counter=1;

for(int i=0;i<n;i++)

{

for(int j=0;j<n;j++)

{

cin>>matrix[i][j];

}

for(int j=0;j<n;j++)

{

if(matrix[s][j] == 1) st.push(j);

}

matrix[s][s]=1;

while(!st.empty())

{

int a=st.top();

st.pop();

if(matrix[a][a]!=1)

{

for(int j=0;j<n;j++)

{

if(matrix[a][j] == 1) st.push(j);

}

counter++;

matrix[a][a]=1;

}

cout<<counter<<endl;

}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(), s = in.nextInt()-1, counter = 1;

int[][] matrix = new int[n][n];

Stack st = new Stack();

for(int i = 0;i < n; i++)

{

for(int j = 0;j < n; j++)

{

matrix[i][j] = in.nextInt();

}

for(int j = 0; j < n; j++)

{

if(matrix[s][j] == 1) st.push(j);

}

matrix[s][s] = 1;

while(!st.empty())

{

int a = (int) st.peek();

st.pop();

if(matrix[a][a] != 1)

{

for(int j = 0; j < n; j++)

{

if(matrix[a][j] == 1) st.push(j);

}

counter++;

matrix[a][a] = 1;

}

System.out.println(counter);

}

Вводим данные, затем в первом цикле проверяем строку [latex]s[/latex], и записываем в стек все вершины инцидентные данной. Так как в условии гарантируется наличие на главной диагонали нулей, то будем помечать проверенные вершины с помощью элемента расположенного на главной диагонали (то есть будем присваивать ему значение отличное от 0, к примеру 1). После будем проверять все строки в стеке до его опустошения, и увеличивать счётчик на единицу после удаления из стека не помеченной вершины.

Код на ideone.

Засчитанное решение.

Ковальський Олександр Дмитрович

А402б

26/11/2014 by Вустянюк Ігор Дмитрович

Задача

Даны натуральное число [latex] n \geq 2 [/latex], действительная квадратная матрица порядка [latex] n [/latex]. Построить последовательность [latex] b_{1}, \ldots, b_{n} [/latex] из нулей и единиц, в которой [latex] b_{i} = 1 [/latex] тогда и только тогда, когда элементы [latex] i [/latex] строки образуют возрастающую или убывающую последовательность.

Тесты

Ввод	Вывод
[latex] \begin{pmatrix} 1 & 2.5 & 3 & -5 & 2 \\ -7 & -4.5 & -2.8 & 0 & 1 \\ 8 & 3 & 0 & -2.9 & -4.62 \\ 8 & 3 & 3 & -2.9 & -4.62 \\ 1 & 2 & 3 & 3 & 4 \end{pmatrix} [/latex]	[latex] \begin{matrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \end{matrix}[/latex]

Код на С++

#include <iostream>

using namespace std;

int main() {

int m, n;

cin >> m >> n;

double M[m][n];

bool monotone[m];

for (int i = 0; i < m; i++)

for (int j = 0; j < n; j++)

cin >> M[i][j];

for (int i = 0; i < m; i++) {

bool check = true, diff;

if (M[i][0] != M[i][1]) {

diff = (M[i][1] > M[i][0]);

for (int j = 2; j < n; j++)

if ((M[i][j] == M[i][j-1]) || ((M[i][j] > M[i][j-1]) != diff)) {

check = false;

break;

}

else

check = false;

monotone[i] = check;

}

for (int i = 0; i < m; i++)

cout << monotone[i] << endl;

return 0;

}

Ideone (C++)

Код на Java

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int m = in.nextInt(), n = in.nextInt();

double[][] M = new double[m][n];

boolean[] monotone = new boolean[m];

for (int i = 0; i < m; i++)

for (int j = 0; j < n; j++)

M[i][j] = in.nextDouble();

for (int i = 0; i < m; i++) {

boolean check = true, diff;

if (M[i][0] != M[i][1]) {

diff = (M[i][1] > M[i][0]);

for (int j = 2; j < n; j++)

if ((M[i][j] == M[i][j-1]) || ((M[i][j] > M[i][j-1]) != diff)) {

check = false;

break;

}

else

check = false;

monotone[i] = check;

}

for (int i = 0; i < m; i++)

System.out.println(monotone[i]);

}

Ideone (Java)

Решение

1) Считываем матрицу

2) Просматриваем по очереди строки матрицы. Фиксируем знак разности первых двух элементов строки и пробегаем строку, сравнивая знак соседних элементов со знаком первых двух. Если последовательность убывает/возрастает, знаки всех пар должны совпадать со знаком первой и никакие два подряд идущих элемента не должны совпадать.

Вустянюк Ігор Дмитрович

А407

26/11/2014 by Бронфен-Бова Роман

Задача:
Даны натуральные числа n и m, действительное число r, действительная матрица размера nxm. Получить значение [latex]{b}_{1}{r}^{n-1}+{b}_{2}{r}^{n-2}+\dots+{b}_{n}[/latex], где [latex]{b}_{k}[/latex] — первый по порядку положительный элемент в k-й строке матрицы [latex](k=1,\dots,n)[/latex]; если в k-строке нет положительных элементов, то [latex]{b}_{k}=0.5[/latex].

Тесты:

nxm	r	Матрица	Результат	Комментарий
2х2	2.5	[latex]\begin{pmatrix} -1 & 1 \\ 1 & 0 \end{pmatrix}[/latex]	3.5	Пройдено
3×4	3.14	[latex]\begin{pmatrix}5.7 & 6.7 & -7.7 & 0.9\\-3.0 & 2.3 & -5.0 & -2.4\\6.7 & 3.5 & 0.0 & 4.4\end{pmatrix}[/latex]	70.1	Пройдено
2×4	2.71	[latex]\begin{pmatrix}-9.0 &-8.8 &-7.3 & 7.5\\-6.3 &-9.7 & 6.8 &-0.5\end{pmatrix}[/latex]	27.1	Пройдено

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

#include <iostream>

#include <math.h>

using namespace std;

int main() {

int n,m; scanf("%d %d",&n,&m);

double r; scanf("%lf",&r);

double a[n][m];

for(int i = 0; i < n; i++)

for(int j = 0; j < m; j++)

scanf("%lf", &a[i][j]);

double sum = 0;

for(int i = 0; i < n; i++) {

double b = 0.5;

for(int j = 0; j < m; j++)

if(a[i][j]>0) {

b = a[i][j];

break;

}

sum += b*pow(r,n-i-1);

}

printf("%lf",sum);

return 0;

}

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

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static Scanner sc = new Scanner(System.in);

public static void main (String[] args) throws java.lang.Exception

{

int n, m;

n = sc.nextInt();

m = sc.nextInt();

double r = sc.nextDouble();

double[][] a = new double[n][m];

for(int i = 0; i < n; i++){

for(int j = 0; j < m; j++){

a[i][j] = sc.nextDouble();

}

double sum = 0;

for(int i = 0; i < n; i++){

double b = 0.5;

for(int j = 0; j < m; j++){

if(a[i][j] > 0){

b = a[i][j];

break;

}