Tile Codes
Time limit2sMemory limit128 MB
Count distinct tilings of a 2xN board using 1x2, 2x1, and 2x2 tiles, where mirror-image tilings under left-right flip count as one.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Combinatorics, Math
- Solved
- No attempts yet
Problem
A 2 x N board must be tiled completely using 1 x 2, 2 x 1, and 2 x 2 tiles. Each tiling is used as a code.
However, two tilings that become identical when the board is flipped left-to-right are considered the same code.
Given N, compute the number of distinct tile codes.
Input
The first line contains the board length N (1 <= N <= 30).
Output
Print the number of distinct tile codes.