Submission #61378996

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
vector<vector<vector<ll>>> dp;
ll countSnakeNumbers(const string& num, int pos, bool isLimit, bool isLeading, int firstDigit) {
    if (pos == num.size()) {
        return 1;
    }
    if (!isLimit && !isLeading && dp[pos][isLimit][firstDigit] != -1) {
        return dp[pos][isLimit][firstDigit];
    }
    ll res = 0;
    int limit = isLimit ? num[pos] - '0' : 9;
    for (int d = 0; d <= limit; ++d) {
        if (isLeading && d == 0) {
            res += countSnakeNumbers(num, pos + 1, isLimit && d == limit, true, firstDigit);
        } else {
            if (firstDigit == 0 || d < firstDigit) {
                res += countSnakeNumbers(num, pos + 1, isLimit && d == limit, false, isLeading ? d : firstDigit);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
vector<vector<vector<ll>>> dp;
ll countSnakeNumbers(const string& num, int pos, bool isLimit, bool isLeading, int firstDigit) {
    if (pos == num.size()) {
        return 1;
    }
    if (!isLimit && !isLeading && dp[pos][isLimit][firstDigit] != -1) {
        return dp[pos][isLimit][firstDigit];
    }
    ll res = 0;
    int limit = isLimit ? num[pos] - '0' : 9;
    for (int d = 0; d <= limit; ++d) {
        if (isLeading && d == 0) {
            res += countSnakeNumbers(num, pos + 1, isLimit && d == limit, true, firstDigit);
        } else {
            if (firstDigit == 0 || d < firstDigit) {
                res += countSnakeNumbers(num, pos + 1, isLimit && d == limit, false, isLeading ? d : firstDigit);
            }
        }
    }
    if (!isLimit && !isLeading) {
        dp[pos][isLimit][firstDigit] = res;
    }
    return res;
}
ll solve(ll L, ll R) {
    string RStr = to_string(R);
    dp.assign(RStr.size(), vector<vector<ll>>(2, vector<ll>(10, -1)));
    ll countR = countSnakeNumbers(RStr, 0, true, true, 0);
    string LStr = to_string(L - 1);
    dp.assign(LStr.size(), vector<vector<ll>>(2, vector<ll>(10, -1)));
    ll countL = countSnakeNumbers(LStr, 0, true, true, 0);
    return countR - countL;
}
int main() {
    ll L, R;
    cin >> L >> R;
    cout << solve(L, R) << endl;
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘ll countSnakeNumbers(const std::string&, int, bool, bool, int)’:
Main.cpp:8:13: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    8 |     if (pos == num.size()) {
      |         ~~~~^~~~~~~~~~~~~

Judge Result