435A - Queue on Bus Stop

The problem could be solved in one cycle by groups. The solution could be implemented in this way:

int result = 1;
int people = 0;

for(int i = 0; i < n; i++)
{
    if (people + a[i] <= m)
        people += a[i];
    else
    {
        result++;
        people = a[i];
    }
}

cout << result << endl;

435B - Pasha Maximizes

The problem could solved by greedy algorithm. We will try to pull maximum digits to the beginning. The algorithm could be described in this way:

1) Consider every position in the number from the first, assume that the current position is i
2) Find the nearest maximum digit from the next k digits of the number, assume that this digit is on position j
3) If this maximum digit is greater than current digit on position i, then make series of swaps, push this digit to position i, also decrease k, that is do k = k - (j - i)

435C - Cardiogram

This problem is technical, you should implement what is written in the statement. First, you need to calc coordinates of all points of the polyline. Also create matrix for the answer. Coordinate y could become negative, so it is useful to double the sizes of the matrix and move the picture up to 1000. In the end you should print the answer without unnecessary empty rows.

To paint the cardiogram you should consider every consecutive pair of points of the polyline and set characters in the answer matrix between them. If the polyline goes up then set slash, otherwise set backslash. To understand the solution better please paint the first test case on the paper, mark coordinates of the points and find what values to set in cycles in your program.

435D - Special Grid

Values n and m are not so large, so the solution with complexity O(max(n, m)³) should pass. It means that you should consider all triangles and check all conditions in O(1).

To make this check you should precalc arrays of partial sums on all diagonals, rows and columns. After that you could check, that there is no black nodes on the side using one sum-query.

Some hints about this problem and the implementation:

• all correct triangles are isosceles right triangles;
• either all legs or hypotenuse of the triangle is parallel to the sides of the grid;
• if you know how to solve the problem for two types of the triangles, you can get the whole solution making 4 rotates of the matrix.

435E - Special Graph

To solve this problem you have to paint different correct colorings on the paper. After it you could observe that there are two types of them: vertical and horizontal.

Vertical colorings looks like this:

acbcbd...
bdadac...
acbcbd...
bdadac...
acbcbd...
bdadac...
......

In other words, each vertical has only two colors, odd verticals have equal colors, even verticals have two others. The order of the colors on every vertical could be arbitrary.

Horizontal colorings are the same, they are rotated by 90 degrees. Of course, there are both vertical and horizontal colorings, but it doesn't change the solution.

So, you should consider every type of described colorings and check them. That is, you could choose what colors are on the verticals or what colors are on horizontals and check that obtained coloring matches the given matrix.

The solution's complexity is O(n × m).