из серии блестим соплей на солнце пока Гаусс думал о новой задаче
Quote:
|
Given an integer matrix A(m, n). Prove that applying the operations of change of sign in a row or in a column one can get a matrix with nonnegative sums of elements in all rows and columns.
|
решение:
представим отрицательные числа в матрице 0 а положительные соответсвенно 1 имеем следующий паттерн:
1
0 0 1 1 1
0 0 0 0 0 1
0
0 1 1 1 1
1
1 1 1 1 1
0
1 1 1 1 1
......
сморим на ряд/колонку с явной отрицательной суммой в ряде/колонке и начинаем менять знак на обратный в итоге меняя знак каждого элемента мы увеличиваем сумму элементов в этом ряду/колонке из негативного в положительный а так как задача говорит что отсальные элементы остаются неизменными то и сумма соответсвенно всех элементов вместе взятых увеличивается соответсвенно что и требовалось доказать ....
возражения?
решение еще одной задачки из теории алгоритмов - может кому и пригодится
