Переберем первое число пары, пусть оно равно x. Тогда нам нужно посчитать количество чисел от 1 до m с остатком от деления на 5 равным (5 - xmod5)mod5. Например, можно предпосчитать, сколько чисел от 1 до m с каждым остатком от 0 до 4.
Отсортируем массив. Заведем переменную cur = 1. Пройдемся по массиву. Посмотрим на очередное число. Если оно больше или равно cur, то увеличим cur на 1. Ответ — это 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, и он содержит в себе все точки из набора. Допустим, что найдется точка, лежащая вне треугольника-ответа. Тогда можно из этой точки более длинную высоту на какую-то сторону опустить, следовательно мы нашли треугольник не максимальной площади(противоречие).
