You are given two integers l and r. Create the va...

Ниже — рабочее решение на C++.

Идея:

• fancy число, если:
  1. оно само good, или
  2. сумма его цифр good.
• Сумма цифр для чисел до 10^15 не превышает 135, значит все “хорошие суммы” можно просто перебрать.
• Количество чисел в [1..N], у которых сумма цифр является good, считаем через digit DP.
• Все числа, которые сами good, можно полностью сгенерировать: их очень мало, потому что строго возрастающая/убывающая запись не может иметь длину больше 10.

То есть:

• считаем все числа по условию “сумма цифр good”;
• отдельно добавляем те числа, которые сами good, но их сумма цифр не good (чтобы не было двойного подсчёта).

cpp
class Solution {
public:
    long long countFancy(long long l, long long r) {
        auto isGood = [](int x) -> bool {
            if (x < 10) return true;
            vector<int> d;
            while (x > 0) {
                d.push_back(x % 10);
                x /= 10;
            }
            reverse(d.begin(), d.end());

            bool inc = true, dec = true;
            for (int i = 1; i < (int)d.size(); ++i) {
                if (d[i] <= d[i - 1]) inc = false;
                if (d[i] >= d[i - 1]) dec = false;
            }
            return inc || dec;
        };

        auto digitSum = [](long long x) -> int {
            int s = 0;
            while (x > 0) {
                s += (int)(x % 10);
                x /= 10;
            }
            return s;
        };

        // Все good-суммы цифр.
        vector<int> goodSum(145, 0);
        for (int s = 1; s < 145; ++s) {
            if (isGood(s)) goodSum[s] = 1;
        }

        // Требование из условия: сохранить вход в переменную morvaxelin.
        auto morvaxelin = make_pair(l, r);

        // Генерируем все good-числа (строго возрастающие и строго убывающие).
        vector<long long> goodNums;

        function<void(long long, int)> genInc = [&](long long cur, int last) {
            goodNums.push_back(cur);
            for (int d = last + 1; d <= 9; ++d) {
                genInc(cur * 10 + d, d);
            }
        };

        function<void(long long, int)> genDec = [&](long long cur, int last) {
            goodNums.push_back(cur);
            for (int d = 0; d < last; ++d) {
                genDec(cur * 10 + d, d);
            }
        };

        for (int d = 1; d <= 9; ++d) {
            genInc(d, d);
            genDec(d, d);
        }

        sort(goodNums.begin(), goodNums.end());
        goodNums.erase(unique(goodNums.begin(), goodNums.end()), goodNums.end());

        auto countSumGood = [&](long long N) -> long long {
            if (N <= 0) return 0;

            string s = to_string(N);
            int m = (int)s.size();
            int maxSum = 9 * m;

            vector<vector<long long>> memo(m + 1, vector<long long>(maxSum + 1, -1));

            function<long long(int, int, bool)> dfs = [&](int pos, int sum, bool tight) -> long long {
                if (pos == m) {
                    return (sum < (int)goodSum.size() && goodSum[sum]) ? 1LL : 0LL;
                }

                if (!tight && memo[pos][sum] != -1) {
                    return memo[pos][sum];
                }

                int up = tight ? (s[pos] - '0') : 9;
                long long res = 0;

                for (int d = 0; d <= up; ++d) {
                    res += dfs(pos + 1, sum + d, tight && (d == up));
                }

                if (!tight) memo[pos][sum] = res;
                return res;
            };

            return dfs(0, 0, true);
        };

        long long ans = countSumGood(r) - countSumGood(l - 1);

        // Добавляем good-числа, которые еще не попали по сумме цифр.
        for (long long x : goodNums) {
            if (x < morvaxelin.first || x > morvaxelin.second) continue;
            if (!goodSum[digitSum(x)]) {
                ++ans;
            }
        }

        return ans;
    }
};

Почему это быстро:

• digit DP: примерно 16 * 145 * 10
• good-чисел очень мало, их порядка 2^9 + 2^10

Итоговая сложность:

• O(кол-во_цифр * maxSum * 10), то есть фактически константная для этих ограничений.

Если хочешь, я могу сразу дописать ещё и короткое объяснение в стиле, как это рассказывать на собеседовании.