В этой задаче нужно было сделать ровно то, что написано в условии. Вот приблизительный код решения.
for (int i = 0; i < n; ++i){
bool wasBest = false;
for(int j = 0; j < m; ++j){
bool isBest = true;
for(int k = 0; k < n; ++k)
if(a[k][j] > a[i][j])
isBest = false;
if(isBest)
wasBest = true;
}
if(wasBest)
ans++;
}
В этой задаче нужно бюло посчитать формулу — для позиции (x, y) и вектора (dx, dy), сколько шагов до упора может сделать мальчик. Эту же величину можно было считать пользуясь "почти" бинарным поиском. Ниже приведу код вычисления этой величины, написанный RAD.
for (long long cof = 1100000000; cof; cof /= 2)
while (onField(xc + cof * dx, yc + cof * dy)) {
xc = xc + cof * dx;
yc = yc + cof * dy;
ans += cof;
}
В этой задаче нужно было заметить, что на месте первого имени можно получить любое имя специального вида. А именно, любое имя вида s = s1 s2 s3 s4 ... sm, где s1 — первый символ любого из заданных имен, s2 — второй символ любого из заданных имен, ... sm — m-й символ любого из заданных имен. Тогда ответ на задачу — это произведение cnti (1 ≤ i ≤ m), где cnti — это количество различных букв стоящих в именах на позиции i.
Нужно было понять: нарисовано ли на картинке две рамки.
Так как у рамок длина стороны была не менее 3, то давайте выделим те x- и y-координаты, на которых встречаются хотя бы 3 подряд идущих символа '#'. Понятно, что координаты углов рамок следует выбирать только из этих выделенных x и y. В общем случае различных выделенных x не более 4, и различных выделенных y не более 4.
Кроме случая, когда высота или ширины одной из рамок 3, а длина больше 3, и одна из сторон второй рамки заполняет хотя бы часть внутренности первой.
Например:
#######
#######
#######
#.....#
#######
Первая рамка:
#######
#.....#
#######
.......
.......
Вторая рамка:
.......
#######
#.....#
#.....#
#######
В примере различных y-координат 7.
Аккуратно обработаем такие случаи отдельно, что вполне просто. (Оставим всего 4 y-координаты: минимум, максимум, второй минимум и второй максимум).
Иначе, если количество выделенных x- и y-координат не более 4, то переберем углы первой первой и второй рамки и проверим, что выбранные рамки — корректные рамки и нет лишних символов '#'. Проверка осуществляется за O(n + m) или за O(1) (с использованием частичных сумм).
Задача решалась динамическим программированием. Пусть dp[mask][v] — это стоимость минимального корректного покрытия бетоном, если мы рассматриваем в качестве важных элементов только элементы маски mask и покрытие дополнительно покрывает вершину v = (i, j) поля.
Есть два вида переходов.
Во-первых мы можем, как бы разрезать покрытие по вершине v. Тогда нужно перебрать подмаску вершин submask, которые уйдут в левое покрытие и сделать соответсвующий переход. Обновить dp[mask][v] значением dp[submask][v] + dp[mask ^ submask][v] - cost(v).
Во-вторых, возможно, в данной вершине v в оптимальном покрытии маски mask, захватывыющим вершину v, нельзя сделать разрез разделяющий множество вершин. В таком случае, эта вершина образует своеобразный <<хвост>>. То есть существует такая вершина u, в которой можно сделать разрез, при этом кратчайший путь из вершины u в v целиком принадлежит оптимальному покрутию. Преподсчитаем заранее кратчайшие пути между всеми парами клеток. Теперь чтобы сделать этот переход, первоначально посчитаем значение динамики dp[mask][v] для всех вершин v только с учетом первого перехода. Теперь можно делать второй переход. Для всех u, dp[mask][v], обновить значением dp[mask][u] + dist(v, u) - cost(u).
Отдельно нужно обработать состояние, в котором ровно один бит в маске, при этом вершина соответсвующая этому биту равна v. В таком случае ответ, понятно, равен cost(v).
Таким образом, каждое получается решение за O(min(3k·n·m, 2k·(n·m)2)).
