A potter tiles a triangular wall. Row r (starting at 0) has r + 1 tiles in columns
0 to r. The single tile of row 0 is glazed. Every later tile (r, c) is glazed when
exactly one of the two tiles above it, (r - 1, c - 1) and (r - 1, c), is glazed.
Positions outside the triangle count as unglazed.
Write glazed_tiles(n, m) returning how many glazed tiles lie in rows 0 to n - 1
and columns 0 to m - 1. Return 0 when n or m is 0.
Examples
Input: n = 4, m = 4
Output: 9
Explanation: rows 0-3 are 1 / 1 1 / 1 0 1 / 1 1 1 1 (1 = glazed): 1 + 2 + 2 + 4.
Input: n = 5, m = 2
Output: 7
Explanation: column 0 is glazed in all 5 rows; column 1 is glazed in rows 1 and 3.
Constraints
0 <= n, m <= 10**18- The wall can have about
10**36tiles, so it cannot be built.
Goals
- Spot that the tile pattern is made of three shrunken copies of itself
- Split a rectangular query across the copies without visiting single tiles
- Keep the recursion to one open branch per level by handling whole-row and whole-column cases separately