Submission #873740

#	Time	Username	Problem	Language	Result	Execution time	Memory
873740		fryingduc	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	3 ms	1884 KiB

numbers

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)     
#endif

#define int long long

const int maxn = 25;
int n, f[25][12][12][2][25];

int go(string &s, int id, int l1, int l2, bool tight, int started){
    if(id == (int)s.size()){
        return 1;
    }
    if(f[id][l1][l2][tight][started] != -1) return f[id][l1][l2][tight][started];
    
    int bound = 9, res = 0;
    if(tight) bound = (s[id] - '0');
    for(int i = 0; i <= bound; ++i){
        if(i == l1 || i == l2) continue;
        bool niu_tight = (i == bound ? tight : 0);
        int niu_started = (i == 0 and started == 0 ? 0 : started + 1);
        res += go(s, id + 1, (niu_started ? i : 10), (niu_started > 1 ? l1 : 10) , niu_tight, niu_started);
    }
    return f[id][l1][l2][tight][started] = res;
}
int calc(int x){
    string s = to_string(x);
    memset(f, -1, sizeof(f)); 
    return go(s, 0, 10, 10, 1, 0);
}
void solve(){
    int l, r; cin >> l >> r;
    debug(calc(r), calc(l - 1));
    cout << calc(r) - calc(l - 1);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int test = 1;
    // cin >> test;
    for(int i = 1; i <= test; i++){
      // cout << "Case " << "#" << i << ": "; 
      solve();
    }

    return 0;
}

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