# UVa 11231

## Summary

Given the dimensions of a m x n chessboard with a specified colour of the tile in the lower right corner, count the number of 8 x 8 standard chessboards embedded within.

## Explanation

Any embedded chessboard can be identified uniquely with its lower right corner. If we count the number of valid lower-right-hand-corners, we thus have our solution.

For convenience we identify the lower right corner of the large board with coordinate (1, 1). We can write any lr-corner of a standard chessboard as (r, c) with the following restrictions:

• (r, c) must be a white tile
• the board starting at (r, c) must fit within the board, ie
• r + 8 <= #rows of the large board = m
• c + 8 <= #cols = n

For any row of width n starting with a white tile, we get the number of candidates by

``` candidates( n ) = (( n - 8 ) / 2 ) + 1, if n >= 8 else 0
```

That is, if we have at least some candidates, remove columns where the "embedded" board would stretch outside the larger board (n - 8). Get the number of white tiles in the range - half of them - ((n - 8) / 2) and compensate as we are off by one.

For any row starting with a black tile we can simply remove one column, thus getting candidates( n - 1 ) by the above formula.

We now simply calculate the number of ok starting rows (ie such that r+8 <= m) starting with a black and white tile respectively, and multiply the results together. This can be done in O(1) with explicit formula, or O(m) if one lazily loops over the rows.

• m, n <= 8?
• OBOB

```8 8 0
8 8 1
9 9 1
40000 39999 0
0 0 0
```

```0
1
2
799700028
```