AvoidFour
SRM 444 · 2009-07-08 · by vexorian
SRM 444 · 2009-07-08 · by vexorian · Advanced Math, Dynamic Programming
Problem Statement
Problem Statement
It is a known fact that of all numbers, 4 is the one that brings the worst luck. It is for this reason that when generating number sequences, we need to avoid patterns related to the number 4 as much as possible.
You are given along n. Count the number of positive integers that satisfy all of the following conditions:
Return the total count of these numbers modulo 1000000007.
You are given a
- The number contains at most n digits.
- The number does not contain four consecutive '4' digits. For example, 43444124 is allowed, but 45444474 is not.
- The number of digits in the number is not a multiple of any of the integers greater than 10 that contain only '4' in their decimal representations (44, 444, 4444, 44444, ...).
Return the total count of these numbers modulo 1000000007.
Constraints
- n will be between 1 and 40000000000 (4e10), inclusive.
Examples
0)
4 Returns: 9998
Of all the 9999 positive integers containing 1, 2, 3 or 4 digits, 4444 is the only one that contains four consecutive '4' digits.
1)
5 Returns: 99980
The numbers to ignore are: 4444, 44440, 44441, 44442, ..., 44449, 14444, 24444, 34444, 54444, ... , 94444.
2)
87 Returns: 576334228
3)
88 Returns: 576334228
88 is a multiple of 44, so all numbers with 88 digits are ignored.
4)
4128 Returns: 547731225
Submissions are judged against all 102 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class AvoidFour with a public method int count(long long n) · 102 test cases · 2 s / 256 MB per case