Problem A2: Cottontail Climb (Part 2)
12 points

Validate Solution & Submit
Problem
My Submissions
This problem shares some similarities with problem A1, with key differences in bold.
Monty the mountain cottontail rabbit is preparing for an expedition in the Rockies. However, Monty is a mathematician first and a mountaineer second, and would like to first assess his route in terms of numbers.
A number is a "mountain" if the following criteria are met:
it has 
2
k
+
1
2k+1 digits, 
D
1
.
.
.
D
2
k
+
1
D 
1
​
 ...D 
2k+1
​
 , for some integer 
k
≥
0
k≥0
none of its digits are zero
the first 
k
+
1
k+1 digits are monotonically non-decreasing
D
i
+
1
≥
D
i
D 
i+1
​
 ≥D 
i
​
  for 
1
≤
i
<
k
+
1
1≤i<k+1
the last 
k
+
1
k+1 digits are monotonically non-increasing
D
i
+
1
≤
D
i
D 
i+1
​
 ≤D 
i
​
  for 
k
+
1
≤
i
<
2
k
+
1
k+1≤i<2k+1
the middle digit is unique
Example of mountains are 
132
132, 
1223221
1223221, and 
4778321
4778321, but not 
12221
12221 or 
1232
1232.
Given an inclusive range 
[
A
,
B
]
[A,B] and an integer 
M
M, help Monty count the number of mountains in the range that are a multiple of 
M
M.
Constraints
1
≤
T
≤
95
1≤T≤95
0
≤
A
≤
B
≤
1
0
18
0≤A≤B≤10 
18
 
1
≤
M
≤
1
0
9
1≤M≤10 
9
 
Input Format
Input begins with an integer 
T
T, the number of test cases. Each case is a single line with the integers 
A
A, 
B
B, and 
M
M.
Output Format
For the 
i
ith test case, print "Case #i: " followed by the number of mountains in the range 
[
A
,
B
]
[A,B] that are a multiple of 
M
M.
Sample Explanation
In the first case, the only number in the range 
[
121
,
121
]
[121,121] is 
121
121, which is both a mountain and a multiple of 
11
11.
In the second case, the mountains in the range 
[
0
,
100
]
[0,100] are the single-digit numbers 
1
1 through 
9
9, of which 
4
4 are multiples of 
2
2.
In the third case, the mountains in the range 
[
0
,
132
]
[0,132] are the single-digit numbers 
1
1 through 
9
9, as well as 
121
121, 
131
131, and 
132
132.
In the sixth case, 
22322
22322 is a mountain.
Sample Input
6
121 121 11
0 100 2
0 132 1
121 132 1
121 131 1
22322 22322 1
Sample Output
Case #1: 1
Case #2: 4
Case #3: 12
Case #4: 3
Case #5: 2
Case #6: 1


solution to the first part, all you have to do is change it up a bit:

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
using namespace std;

void fastIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

vector<int> generate_peaks() {
    vector<int> peaks;
    for (int k = 0; k < 10; ++k) { 
        int num_digits = 2 * k + 1;
        if (num_digits > 19) continue;

        for (int D1 = 1; D1 <= 9 - k; ++D1) {
            vector<int> digits;

            for (int i = 0; i <= k; ++i) {
                digits.push_back(D1 + i);
            }
            for (int i = 0; i < k; ++i) {
                digits.push_back(D1 + k - 1 - i);
            }

            int number = 0;
            for (int digit : digits) {
                number = number * 10 + digit;
            }
            peaks.push_back(number);
        }
    }
    sort(peaks.begin(), peaks.end());
    return peaks;
}

int count_peaks(const vector<int>& peaks, int A, int B, int M) {
    int count = 0;
    for (int p : peaks) {
        if (A <= p && p <= B && p % M == 0) {
            count++;
        }
    }
    return count;
}

int main() {
    fastIO();
    
    vector<int> peaks = generate_peaks();
    int T;
    cin >> T;

    for (int case_num = 1; case_num <= T; ++case_num) {
        int A, B, M;
        cin >> A >> B >> M;

        int res = count_peaks(peaks, A, B, M);
        cout << "Case #" << case_num << ": " << res << '\n';
    }

    return 0;
}