Задача
Дано таблицу [latex] n \times n [/latex]. Возбуждённостью строки или столбца назовём сумму чисел в нём. Необходимо определить число, находящееся на перекрёстке наиболее возбуждённой строки и наименее возбуждённого столбца. Причём, чем выше будет этот перекрёсток (а среди них левее), тем большей будет вероятность прохождения теста.
Входные данные
Первая строка входного файла содержит число [latex]n (1 \le n \le 100)[/latex], последующие $n$ строк содержат саму таблицу. Числа в таблице натуральные и не превышают $100000$.
Для того, чтобы понять, как какая диагональ называется, внимательно присмотритесь ко второму примеру.
Выходные данные
В выходной файл выведите единственное число – ответ к задаче.
Тесты
| Вход | Выход |
| 2 4 3 2 1 |
3 |
| 3 1 1 1 1 1 1 1 1 1 |
1 |
| 4 3 2 5 8 13 32 51 9 12 22 3 17 2 1 1 5 |
13 |
| 2 32 19 65 11 |
11 |
| 3 3 9 2 13 1 0 3 1 7 |
2 |
Код программы
|
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 38 39 40 41 42 43 |
#include <iostream> using namespace std; int main() { int n; int mer=0; // most excited row int lec=0; // least excited column cin >> n; int **table=new int *[n]; for (int i=0; i<n; i++) table[i]= new int [n]; for (int i=0; i<n; i++) for (int j=0; j<n; j++) cin >> table[i][j]; int *exc= new int [n]; // excitation of the rows / columns for (int l=0; l<n; l++){ exc[l]=0; for (int i=0; i<n; i++) exc[l]+=table[l][i]; } for (int i=0; i<n; i++){ if (exc[mer] < exc[i]){ exc[mer]=exc[i]; mer=i; } } for (int k=0; k<n; k++){ exc[k]=0; for (int j=0; j<n; j++) exc[k]+=table[j][k]; } for (int i=0; i<n; i++){ if (exc[lec] > exc[i]){ exc[lec]=exc[i]; lec=i; } } cout << table[mer][lec]; for (int i = 0; i < n; i++) delete []table[i]; delete []table; return 0; } |
Решение
Создаем динамический массив, в котором вводим числа.
Отдельно создаем массивы для поиска суммы строк и суммы столбцов. Ищем наиболее возбужденную строку и наименее возбужденный столбец, а также запоминаем их с помощью отдельных переменных. После вводим запомненные «координаты», и получим востребованное нами число.
Ссылки