SmoothMultiples
SRM 842 · 2022-12-01 · by misof
Problem Statement
A positive integer is K-smooth if each pair of its consecutive digits differs by at most K.
For example:
- 7, 77, and 333 are all 0-smooth while 12 and 20 are not.
- 7, 77, 234, 1010, 4323, and 556566765454 are all 1-smooth while 42, 90, and 54222 are not.
- 7, 42, 1357, 86420, and 865454321001 are all 2-smooth while 36, 204, and 9090 are not.
Count all K-smooth integers that lie between A and B, inclusive, and are multiples of C.
Constraints
- K will be between 0 and 9, inclusive.
- A will be between 1 and 10^11 - 1, inclusive.
- B will be between A and 10^11 - 1, inclusive.
- C will be between 1 and 10^11 - 1, inclusive.
1 10 33 1 Returns: 8
We are counting all 1-smooth integers in the range [10,33]. There are eight of them: 10, 11, 12, 21, 22, 23, 32, and 33.
1 97 102 1 Returns: 4
The 1-smooth integers in this range are 98, 99, 100, and 101.
1 97 102 2 Returns: 2
The even 1-smooth integers in this range are 98 and 102.
9 123 45678 3 Returns: 15186
All positive integers are 9-smooth. There are 15,186 multiples of three in the given range.
3 1234 5678 73 Returns: 13
These are the 13 numbers: 1241, 1314, 2336, 2555, 3212, 3358, 3431, 3577, 4234, 4453, 4745, 5256, and 5475.
7 1234567 98765432100 2499 Returns: 23097617
23097617
0 123 4567 1 Returns: 12
These are the 12 numbers: 222, 333, ..., 999, 1111, 2222, 3333, and 4444.
Submissions are judged against all 195 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SmoothMultiples with a public method long long count(int K, long long A, long long B, long long C) · 195 test cases · 2 s / 256 MB per case