Задача
Есть таблица $n × n.$ Оживленностью строки или столбца назовем сумму чисел в ней. Нам очень хочется определить число на перекрестке самой оживленной строки и самого неоживленного столбца. Причем, чем выше будет этот перекресток (а среди них – чем левее), тем больше будет вероятность прохождения теста.
Входные данные
В первой строке находится число $n (1 \leq n \leq 100).$ В следующих $n$ строчках задана таблица. Числа в таблице натуральные и не превышают $100000.$
Выходные данные
Выведите число на перекрестке самой оживленной строки и самого неоживленного столбца.
Тесты
| Входные данные | Выходные данные | |
| 1 | 2 4 3 2 1 |
3 |
| 2 | 3 1 1 1 1 1 1 1 1 1 |
1 |
| 3 | 5 13 15 17 2 9 4 56 8 90 0 4 3 5 7 5 23 4 5 71 4 5 6 7 8 10 |
0 |
| 4 | 4 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 |
1 |
Код
С помощью одномерного массива
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> using namespace std; int main() { int n, ns; cin >> n; ns = n*n; int *x = new int[ns]; for (int i = 0; i < ns; i++) cin >> x[i]; int I, J, min, max; for (int i = 0; i < ns; i += n) { int lmax = 0; for (int j = 0; j < n; j++) lmax += x[i + j]; if (lmax > max || i == 0) { max = lmax; I = i; } } for (int j = 0; j < n; j++) { int lmin = 0; for (int i = 0; i < ns; i += n) lmin += x[i + j]; if (lmin < min || j == 0) { min = lmin; J = j; } } cout << x[I + J]; delete []x; return 0; } |
С помощью двумерного массива
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <iostream> using namespace std; int main() { int n; cin >> n; int **x = new int*[n]; for (int i = 0; i < n; i++) x[i] = new int [n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> x[i][j]; int I, J, min, max; for (int i = 0; i < n; i++) { int lmax = 0; for (int j = 0; j < n; j++) lmax += x[i][j]; if (lmax > max || i == 0) { max = lmax; I = i; } } for (int j = 0; j < n; j++) { int lmin = 0; for (int i = 0; i < n; i++) lmin += x[i][j]; if (lmin < min || j == 0) { min = lmin; J = j; } } cout << x[I][J]; for (int i = 0; i < n; i++) delete []x[i]; delete []x; return 0; } |
Решение
Для решения данной задачи используем двумерный массив размера $n \times n$. С помощью цикла for ищем самую оживленную строку, затем самый неоживленный столбец, и выводим элемент таблицы на их перекрёстке.
Для решения с помощью одномерного массива действуем аналогично, работая с массивом длинны $n^2$, используя следующее соответствие: $x[i][j] \sim x[i \cdot n + j]$