Submission #96950

#	Time	Username	Problem	Language	Result	Execution time	Memory
96950		dalgerok	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	7 ms	1152 KiB

numbers

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


long long ans;
string s;
long long dp[20][10][10][20][2];

long long rec(int pos, int d1, int d2, int curpos, bool pref){
    ///cout << (int)s.size() << " " << pos << " " << d1 << " " << d2 << " " << curpos << " " << pref << " " << dp[pos][d1][d2][curpos][pref] << "\n";
    if(pos >= (int)s.size()){
        return 1;
    }
    if(dp[pos][d1][d2][curpos][pref] != -1){
        return dp[pos][d1][d2][curpos][pref];
    }
    long long &cur = dp[pos][d1][d2][curpos][pref];
    cur = 0;
    int bound = (pref ? s[pos] - '0' : 9);
    for(int i = 0; i <= bound; i++){
        if(curpos == 0){
            if(i){
                cur += rec(pos + 1, i, 0, 1, (pref && bound == i));
            }
            else{
                cur += rec(pos + 1, 0, 0, 0, (pref && bound == i));
            }
        }
        else if(i != d1){
            if(curpos >= 2 && i != d2){
                cur += rec(pos + 1, i, d1, curpos + 1, (pref && bound == i));
            }
            else if(curpos == 1){
                cur += rec(pos + 1, i, d1, curpos + 1, (pref && bound == i));
            }
        }
    }
    return cur;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    long long a, b;
    cin >> a >> b;
    if(a == 0){
        ans += 1;
    }
    else{
        a -= 1;
    }
    s = to_string(b);
    memset(dp, -1, sizeof(dp));
    ans += rec(0, 0, 0, 0, true);
    s = to_string(a);
    memset(dp, -1, sizeof(dp));
    ans -= rec(0, 0, 0, 0, true);
    cout << ans;
}

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