Problem Description
Input: N (1-20)
Requirement: Count how many numbers with at most N digits do not contain consecutive digit 6s.
Example:
2, 0~99, invalid [66]This problem asks for the count of all numbers with up to N digits that do not contain consecutive 6s. A standard solution is digit DP: build numbers digit by digit while tracking whether the previous digit was 6 and whether the current prefix is still bounded by the upper limit. This avoids brute force and works efficiently even when N is as large as 20.
END
