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

Задача. Седловые точки

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

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

Первая строка содержит целые числа $n$ и $m$. $(1 \leq n, m \leq 750)$. Далее следуют $n$ строк по $m$ чисел в каждой. $j$-ое число $i$-ой строки равно $k_{ij}$. Все $k_{ij}$ по модулю не превосходят $1000$.

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

Выведите количество седловых точек.

Тесты

Ввод Вывод
1 2 2
0 0
0 0
4
2 2 2
1 2
3 4
1
3 5 5
100 -100 100 1000 110
10 -1000 100 -1000 110
100 -1000 100 100 110
1000 -1000 1000 1000 100
1000 -1000 1000 1000 -1000
1
4 4 4
1000 1000 100 100
1000 1000 1000 1000
100 100 100 1000
100 1000 1000 1000
4
5 2 3
1 -1 1
0 -1 0
2
6 5 1
-1
0
-1
0
-1
2
7 4 2
1 2
-2 1
-1 2
-2 -1
1
8 3 3
5 1 3
3 1 2
1 1 2
3
7 3 3
5 2 3
3 4 2
1 8 2
0

Решение

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

Вариант решения за $O\left(n^2\right)$

Для этого мы просто сравниваем каждый максимум с каждым минимумом и считаем их совпадения. В этом случае алгоритм будет выполнятся за $O(n^2)$, где $n$ это наибольшая из длин массивов. Это значит что при достаточно больших массивах программа будет работать непозволительно долго. Но такой подход достаточно прост в реализации и интуитивно понятен.

Вариант решения за $O\left(n\log n\right)$

В этом случае мы сортируем массивы, для установления взаимосвязи между элементами в них. А далее заведя два указателя на элементы массивов проверяем на равенство только не меньшие элементы от текущих в разных массивах. Если равных элементов окажется несколько подряд, то их количество будет равно произведению количества их повторений в каждом из массивов. Дойдя до конца одного из них нужно не забыть проверить остались ли в другом массиве равные последнему в пройденном элементы. Проверять стоит лишь не меньшие элементы. Таким алгоритмом мы проверяем совпадения линейно за $O(n)$, где $n$ это наибольшая из длин массивов, но для него необходимо отсортировать оба массива за $O(n\log n)$. Таким образом мы получаем вычислительную сложность $O(n\log n)$, что уже быстрее предыдущего варианта.

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