Let's iterate over the first number of the pair, let it be x. Then we need to count numbers from 1 to m with the remainder of dividing 5 equal to (5 - xmod5)mod 5. For example, you can precalc how many numbers from 1 to m with every remainder between 0 and 4.
Отсортируем массив. Заведем переменную cur = 1. Пройдемся по массиву. Посмотрим на очередное число. Если оно больше или равно cur, то увеличим cur на 1. Ответ — это cur.
Let's sort the array. Let cur = 1. Then walk through the array. Let's look at current number. If it is greater or equal to cur, then let's increase cur by 1. Answer is cur.
Будем делать dfs. Пусть мы сейчас стоим в вершине u. Пусть v — это какой-то предок вершины u. Тогда dist(v, u) = dist(1, u) - dist(1, v). Если dist(v, u) > au, то вершина u заставляет вершину v грустить. Так что необходимо удалить все поддерево вершины u. Соответственно, в dfs можно поддерживать минимум среди dist(1, v), где v — это предок u(вершина, в которой мы сейчас стоим). И если разность dist(1, u) и этого минимума больше au, то удаляем au вместе со всем поддеревом.
Воспользуемся методом динамического программирования. Пусть d[i][j][cnt][end] — ответ на задачу для префикса строки s длины i и префикса строки t длины j, при том, что подпоследовательность, являющаяся ответом состоит из cnt подстрок. end = 1, если оба последних элемента данных префиксов строк входят в максимальную подпоследовательность и end = 0 в противном случае.
Находясь в состоянии d[i][j][cnt][end], можно добавить следующую букву в строках s или t, при том она не будет входить в ответную подпоследовательность. Тогда d[i + 1][j][cnt][0] = max(d[i + 1][j][cnt][0], d[i][j][cnt][end]), d[i][j + 1][cnt][0] = max(d[i][j + 1][cnt][0], d[i][j][cnt][end]). То есть новое значение end равно 0, поскольку новая буква не входит в ответную подпоследовательность.
Если s[i] = t[j], то, если end = 1, то можно обновить d[i + 1][j + 1][k][1] = max(d[i][j][k][end] + 1, d[i + 1][j + 1][k][1]). Поскольку end = 1, при добавлении элемента к ответной подпоследовательности, количество подстрок, из которых она состоит, останется таким же. Если end = 0, то можно обновить d[i + 1][j + 1][k + 1][1] = max(d[i][j][k][end] + 1, d[i + 1][j + 1][k + 1][1]). В этом случае новые символы, которые мы пытаемся добавить к ответной подпоследовательности, будут образовывать уже новую подстроку, поэтому в этом случае переход из состояния с k в состояние с k + 1.
Ответом будет являться наибольшее число среди состояний вида d[n][m][k][end], где значения k и end принимают всевозможные значения.
Найдем треугольник максимальной площади из всех треугольников, вершины которого — точки из данного набора. (за N2 с выпуклой оболочкой и двумя указателями). Утверждается, что если взять треугольник, на серединах сторон которого лежат вершины треугольника с максимальной площадью, площадь такого треугольника не превосходит 4S, и он содержит в себе все точки из набора. Допустим, что найдется точка, лежащая вне треугольника-ответа. Тогда можно из этой точки более длинную высоту на какую-то сторону опустить, следовательно мы нашли треугольник не максимальной площади(противоречие).
