Count Black Cells

Description:

Imagine a white rectangular grid of n rows and m columns divided into two parts by a diagonal line running from the upper left to the lower right corner. Now let’s paint the grid in two colors according to the following rules:

  • A cell is painted black if it has at least one point in common with the diagonal;
  • Otherwise, a cell is painted white.

Count the number of cells painted black.

Example

  • For n = 3 and m = 4, the output should be
    countBlackCells(n, m) = 6.

    There are 6 cells that have at least one common point with the diagonal and therefore are painted black.

  • For n = 3 and m = 3, the output should be
    countBlackCells(n, m) = 7.

    7 cells have at least one common point with the diagonal and are painted black.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer n

    The number of rows.

    Constraints:
    1 ≤ n ≤ 105.

  • [input] integer m

    The number of columns.

    Constraints:
    1 ≤ m ≤ 105.

  • [output] integer

    The number of black cells.

Tests:
Solution:

int countBlackCells(int n, int m) {
    int answer = 0;
    for (int x = 1; x <= n; x++) {
        int L = (int) (m * 1L * (x - 1) / n);
        if (m * 1L * (x - 1) % n == 0) {
            L--;
        }
        int R = (int) (m * 1L * x / n);
        L = Math.Max(0, L);
        R = Math.Min(R, m - 1);
        answer += R - L + 1;
    }
    return answer;
}

2 thoughts on “Count Black Cells

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s