In this problem you should do exactly what is written in the statement. Here is rough code of solution:
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++;
}
Let's find a formula for the position (x, y) and vector (dx, dy), how many steps to stop the boy can do. You should use "almost" binary search, for example, see the code written by 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;
}
In this task, it was necessary to understand that in position 1 Vasya can get any name of a special form. More exactly, it's the name of form s = s1 s2 s3 s4 ... sm, where s1 — the first letter of any of the names, s2 — the second letter of any of the names, ... sm — m-th letter of any of the names. Then the answer to the problem is the product of cnti (1 ≤ i ≤ m), where cnti is a number of different letters in the names placed in position i.
It was necessary to understand if there are two borders or not.
Let's distinguish those x — and y-coordinates, in which there are at least 3 consecutive symbols '#', becouse the length of each border is no less then 3. It is clear that the coordinates of the corners of borders should be chosen only from those selected x and y. In general, the various selected x no more then 4 and various selected y no more then 4.
Except that case when the height or width of the first border is 3, and length of the second side of this border is more than 3, and one side of the second border fills a part of the inside first at least.
For example:
#######
#######
#######
#.....#
#######
The first border:
#######
#.....#
#######
.......
.......
The second border:
.......
#######
#.....#
#.....#
#######
There are 7 different y-coordinates in the example.
Carefully processed these cases separately, it is quite simple. (Let's choose 4 y-coordinates: minimum, maximum, second minimum and second maximum).
Otherwise, if the amount selected x — and y-coordinates no more then 4, then let's choose opposite corners of the first and second borders and verify that the selected borders — the correct borders and there are no other characters '#'. Checking is carried out at O(n + m) or O(1) (using partial sums).
The solution of this problem is based on dynamic programming. dp[mask][v] — the value of the minimum correct concrete cover, if we consider as important elements only elements of the mask mask, and there are additionally covered the vertex v = (i, j) of the field.
There are two types of transfers.
First of all we can, as if to cut coverage on the vertex v. Then you need to go through subpattern of vertex submask, which will go to the left coverage and make an optimizing transfer. Update dp[mask][v] with the value dp[submask][v] + dp[mask ^ submask][v] - cost(v).
Second, perhaps in the vertex v in the optimal coverage mask mask, which covers the vertex v, you can not make the cut separating the set of vertices. In this case, this vertex forms something a kind of <>. And there a vertex u exists, on which we can make the cut, with the whole shortest path from a vertex u to v belongs to the optimal coverage. Let's precalculate the shortest paths between all pairs of cells. Now to make this transition, we should count the value of dynamics dp[mask][v] for all vertices v only on the basis of the first transition. Now you can make the second transition. For all u, dp[mask][v], update the value of dp[mask][u] + dist(v, u) - cost(u).
Let's process separately state in which exactly one bit in the mask, and the vertex which corresponding to this bit is equal to v. In this case the answer is equal to cost(v), of course.
Thus, each solution is obtained for the O(min(3k·n·m, 2k·(n·m)2)).
