Submission #306344

#	Time	Username	Problem	Language	Result	Execution time	Memory
306344		syy	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	392 KiB

numbers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a, b, dp[11][11][20][2]; //pp, p, idx, same
string str;

ll f(ll pp, ll p, ll idx, bool same) { //returns num of palin free num from here to limit
    if (dp[pp][p][idx][same] != -1) return dp[pp][p][idx][same];
    if (idx == str.length()) return 1; //reach past end of str -> palin free
    dp[pp][p][idx][same] = 0;
    
    if (same) {
        for (ll i = 0; i <= str[idx] - '0'; i++) {
            if (i == pp or i == p) continue;
            dp[pp][p][idx][same] += f(p, i, idx + 1, i == str[idx] - '0');
        }
    } else {
        for (ll i = 0; i <= 9; i++) {
            if (i == pp or i == p) continue;
            dp[pp][p][idx][same] += f(p, i, idx + 1, 0);
        }
    }
    return dp[pp][p][idx][same];
}

ll f2(ll x) { //palin free num from 1 to x
    ll ret = 1; //0 is palin free
    str = to_string(x);
    memset(dp, -1, sizeof dp);
    if (x == 0) return 1;
    else if (x == -1) return 0;
    
    for (ll i = 1; i <= str[0] - '0'; i++) {
        ret += f(i, i, 1, i == str[0]  - '0');
    }
    
    //try all the leading zeros
    for (ll pos = 2; pos <= str.length(); pos++) {
        for (ll i = 1; i <= 9; i++) {
            ret += f(i, i, pos, 0);
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> a >> b;
    cout << f2(b) - f2(a-1);
}

Compilation message (stderr)

numbers.cpp: In function 'll f(ll, ll, ll, bool)':
numbers.cpp:10:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     if (idx == str.length()) return 1; //reach past end of str -> palin free
      |         ~~~~^~~~~~~~~~~~~~~
numbers.cpp: In function 'll f2(ll)':
numbers.cpp:39:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (ll pos = 2; pos <= str.length(); pos++) {
      |                      ~~~~^~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75