Submission #1294726

#TimeUsernameProblemLanguageResultExecution timeMemory
1294726AzeTurk810Palindrome-Free Numbers (BOI13_numbers)C++20
71.25 / 100
1 ms580 KiB
/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <iostream>
#include <string>

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using namespace std;

#define ln '\n'
#define INFi 1e9
#define INFll 1e18
#define int ll

int dp[20][11][11][2];
string s;

int solve(int cur , int num1 , int num2 , char k) {
    if(dp[cur][num1][num2][k] != -1)
        return dp[cur][num1][num2][k];
    if(s.size() == cur)
        return dp[cur][num1][num2][k] = 1;
    int res = 0;
    if(num2 == 0) {
        res += solve(cur + 1 , 0 , 0 , 0);
    }
    int pos = s[cur] - '0' + 1;
    if(k == 1) {
        for(int i = 1;i < pos;i++) {
            if(num1 != i && num2 != i) {
                res += solve(cur + 1 , num2 , i , 0);
            }
        }
        if(pos != num2 && pos != num1)
            res += solve(cur + 1 , num2 , pos , k);
    } else {
        for(int i = 1;i <= 10;i++) {
            if(num1 != i && num2 != i) {
                res += solve(cur +1 , num2 , i , 0);
            }
        }
    }
    return dp[cur][num1][num2][k] = res;
}

int solve(int n) {
    for(int i = 0;i < 20;i++) {
        for(int n1 = 0; n1 < 11;n1 ++) {
            for(int n2 = 0;n2 < 11;n2++) {
                dp[i][n1][n2][0] = dp[i][n1][n2][1] = -1;
            }
        }
    }
    s = to_string(n);
    return solve(0 , 0 , 0 , 1);
}


void solve() {
    ll a , b;
    cin >> a >> b;
    cout << solve(b) - solve(max(0LL , a - 1)) << ln; 
}

// Attack on titan<3

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int t = 1;
//      cin >> t;
    for(int cases = 0 ; cases < t;cases ++) {
        solve();
    }
}
// Just Imaginary
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...