# UVa 11231

## 11231 - Black and white painting[edit]

## Summary[edit]

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[edit]

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.

## Gotchas[edit]

- m, n <= 8?
- OBOB

## Input[edit]

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

## Output[edit]

0 1 2 799700028