Submission #1294733

#TimeUsernameProblemLanguageResultExecution timeMemory
1294733AzeTurk810Palindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
52 ms576 KiB
/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <cassert>
#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) {
        // if(num2 == 0)
        //     return 0;
        return dp[cur][num1][num2][k] = 1;
    }
    int res = 0;
    if(num2 == 0) {
        assert(num1 == 0);
        // if(cur + 1 != s.size())
            res += solve(cur + 1 , 0 , 0 , 0);
    }
    int pos = s[cur] - '0' + 1;
    int mal_0_qoysun = (num2 == 0) + 1;
    if(num2 == 0 && cur + 1 == s.size()) {
        mal_0_qoysun = 1;
    }
    if(k == 1) {
        for(int i = mal_0_qoysun;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 = mal_0_qoysun;i <= 10;i++) {
            if(num1 != i && num2 != i) {
                res += solve(cur +1 , num2 , i , 0);
                cerr << i << ln;
            }
        }
    }
    cerr << cur << ' '<< s<< ' '<< num1 - 1 << ' ' << num2 - 1 << ' '  << res << ln;
    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;
    if(a != 0)
        cout << solve(b) - solve(a - 1) << ln; 
    else 
        cout << solve(b) - 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...