Можно было перебирать каждую позицию и проверять подходит ли она под условия
a ≤ i - 1 и
n - i ≤ b (для
i от
1 до
n). Первое условие можно преобразовать в
a + 1 ≤ i, а условие
n - i ≤ b в
n - b ≤ i, тогда общее условие можно записать
max(a + 1, n - b) ≤ i и тогда наш ответ можно вычислить по формуле
n - max(a + 1, n - b) + 1.
Авторское решение
Пробуем всеми возможными способами переставить цифры в числах и для каждой перестановки проверяем разницу между максимальным и минимальным числом.
Авторское решениеВсе позиции кроме первой и тех, чей номер простое число большее
|s| / 2 должны иметь одинаковый символ. Оставшиеся же позиции могут быть любыми. Как это показать: рассмотрим позиции, которые должны совпадать для
p = 2 это 2,4,6,8... теперь возьмем позицию с номером
x ≤ |s| / 2, эта позиция должна иметь тот же символ что и на позиции
2, так как символ
x должен быть равен символу на позиции
2 * x, который в свою очередь равен символу на позиции
2. Теперь рассмотрим позиции, чей номер больше чем
|s| / 2. Если эта позиция имеет номер не простое число значит есть простое число
p на которое делится номер нашей позиции и
p ≤ |s| / 2. Символ в позиции
p равен символу в позиции
2, так как
p ≤ |s| / 2 значит и символ в нашей позиции также соответствует символу в позиции
2. Оставшиеся же позиции не объединяются ни с какими другими позициями поэтому символ который стоит в них ни на что не влияет.
Найдем символ который встречается максимальное количество раз и пробуем этот символ расставить на позиции символы в которых должны быть равны. Если этого символа на все позиции не хватает тогда ответ "NO", иначе оставшиеся символы расставляем как угодно на остальные позиции.
Авторское решение
Повернем поле на
45o преобразовав координаты клетки
(x, y) в
(x + y, x - y). Тогда клетка
(x, y) будет плохой, если будет выполняться одно из условий
x ≡ 0 (mod 2a) или
y ≡ 0 (mod 2b). Т.е. неплохие клетки будут разбиты на сектора вертикальными и горизонтальными прямыми. Для каждого сектора можно определить его координаты парой чисел, первое число которое будет увеличиваться при переходе в соседний правый сектор, а второе число пары будет увеличиваться при переходе в соседний верхний сектор. Из сектора с координатами
(x, y) можно перейти в любой соседний по стороне сектор, посетив минимум 1 плохую клетку, т.е. в
(x - 1, y),
(x + 1, y),
(x, y - 1) и
(x, y + 1). Так как числа
2a и
2b имеют одинаковую четность, то из сектора
(x, y) также можно перейти в сектор по диагонали, посетив также 1 плохую клетку, т.е. в
(x - 1, y + 1),
(x + 1, y - 1),
(x - 1, y - 1) и
(x + 1, y + 1). Тогда получается что минимальное количество плохие клеток, которые должны быть посещены по пути из сектора
(x1, y1) в сектор
(x2, y2) будет равно
max(|x1 - x2|, |y1 - y2|).
Преобразуем координаты начальной и конечной клеток по вышеописанному правилу. Потом найдем в каких секторах находятся наши клетки и вычислим ответ по вышеописанной формуле.
Авторское решениеДля начало сведем задачу к одномерной матрицы. Рассмотрим монотонный путь
(1, 1), (1, 2), ..., (1, m - 1), (1, m), (2, m), ..., (n - 1, m), (n, m) по которому получается правильная скобочная последовательность. Теперь в этом пути можно заменить клетку
(1, m) на
(2, m - 1) и по прежнему путь будет монотонным и будет образовывать правильную скобочную последовательность. Значит в клетках
(1, m) и
(2, m - 1) стоит скобка одного типа. Продолжая так дальше ( например заменить
(1, m - 1) на
(2, m - 2) или
(2, m) на
(3, m - 1)) можно увидеть, что в клетках
(i, j) и
(i - 1, j + 1) стоит скобка одного типа. Тогда у нас получается не двумерный массив
n × m, а одномерный размером
n + m - 1. Для каждой позиции можно определить какой у неё наибольший приоритет, т.е. для клетки
i (
1 ≤ i
≤ n + m - 1) приоритет будет равен минимальному значению
px, y где
1 ≤ x ≤ n,
1 ≤ y ≤ m и
x + y - 1 = i.
Теперь перебираем позиции, начиная с наиболее приоритетных. Ставим в эту позицию скобку "(" и считаем сколькими способами можно доставить оставшиеся скобки, чтобы получалась правильная скобочная последовательность. Если количество способов не меньше
k, тогда оставляем в этой позиции скобку "(", иначе уменьшаем
k на количество способов и ставим в эту позицию скобку ")". И так проходим по всем позициям. Для того чтобы посчитать количество способов каждый раз просчитывается динамика по двум параметрам
fi, j, где
i количество обработанных позиций, а
j количество открытых скобок. Если на позиции
i + 1 скобка ещё не определена тогда можно перейти в
fi + 1, j + 1 или
fi + 1, j - 1, если же определена тогда только в
fi + 1, j + 1 или только
fi + 1, j - 1 в зависимости открывающаяся или закрывающаяся скобка соответственно.
Авторское решениеОтсортируем все суффиксы строки (обозначим как массив строк
ci). Тогда ответ на задачу будет количество таких
1 ≤ i ≤ j ≤ |s| и
1 ≤ k, что префиксы длины
k у всех строк
сi..j равны. Варианты когда
i = j и
1 ≤ k ≤ |ci| можно просчитать сразу, это равно количеству подстрок в строке, т.е.
|s| * (|s| + 1) / 2. Теперь посчитаем LCP (самый длинный общий префикс) для соседних суффиксов, т.е.
ai = LCP(ci, ci + 1) для
1 ≤ i < |s|. Тогда теперь надо посчитать количество таких
1 ≤ i ≤ j < |s| и
1 ≤ k, что
k ≤ min(ai..j). Эта задача на подсчет количества прямоугольников, если есть ограничение на высоту в каждом столбце, т.е.
ai максимальная высота прямоугольника в столбце
i. Решается при помощи стека или списка.
Авторское решениеРассмотрим чему равно матожидание для фиксированного входа и выхода. Понятно что из входа в выход будет существовать всего лишь один путь, который в любом случае будет пройден. Также ещё можно пойти в неправильном направлении. Рассмотри случай когда выбрана вершина, из которой есть
k ложных путей и один верный (он есть всегда). Тогда перед тем как пойти в верном направлении возможно
2k равновероятных способов обхода ложных путей. Каждый ложный путь входить в
2k - 1 способов и увеличивает количество ходов на
2 × < размер ложного поддерева > т.е. матожидание от ложного пути увеличиться на
2 × < размер ложного поддерева > × 2k - 1 / 2k = < размер ложного поддерева > . Тогда матожидание в вершине равно сумме
< размеров ложных поддеревьев > + 1 (это ход в верном направлении) + матожидание от вершины в которую пойдем, идя в верном направлении. В итоге получается, что матожидание равно количеству достижимых ребер из входа, не проходя через выход.
Запустим обход в глубину и каждую вершину рассматривать как вершину выхода. Тогда если в каком-то поддереве определяется вход, то матожидание равно размеру этого поддерева. Просчитываем сколько в каждом поддереве будет количество входов и вычисляем количество ходов, если выход находится в текущей вершине. Также надо не забыть просчитать случаи когда текущая вершина является выходом, а вход расположен выше по обходу дерева.
Авторское решение