Submission #1300082

#TimeUsernameProblemLanguageResultExecution timeMemory
1300082kirakosyanPalindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
2 ms580 KiB
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<unordered_map>
#include<unordered_set>


using namespace std;
using ll = long long;
ll mod = 1e9 + 7;
ll gcd(ll a, ll b) {
    if (b == 0)return a;
    else return gcd(b, a % b);
}
ll get(ll n) {
    vector<vector<vector<vector<ll>>>>dp(19, vector<vector<vector<ll>>>(11, vector<vector<ll>>(11, vector<ll>(2))));
    dp[0][10][10][1] = 1;
    string s = to_string(n);
    for (ll i = 1; i <= s.size(); i++) {
        for (ll k = 0; k <= 10; k++) {
            for (ll x = 0; x <= 10; x++) {
                for (ll j = 0; j <= 10; j++) {
                    if (k == 0 && x == 10)continue;
                    if (k == 10) {
                        dp[i][k][k][0] = 1;
                    }

                    else if (x == 10) {
                        if (i != 1) {
                            dp[i][k][x][0] = 1;
                        }
                        else if (k < (s[i - 1] - '0')) {
                            dp[i][k][x][0] = 1;
                        }
                        else if (k == (s[i - 1] - '0')) {
                            dp[i][k][x][1] = 1;
                        }
                    }
                    else {
                        if (k != x && k != j && j != x) {
                            if (k < (s[i - 1] - '0')) {
                                dp[i][k][x][0] += dp[i - 1][x][j][0];
                                dp[i][k][x][0] += dp[i - 1][x][j][1];

                            }
                            else if (k == (s[i - 1] - '0')) {
                                dp[i][k][x][1] += dp[i - 1][x][j][1];

                                dp[i][k][x][0] += dp[i - 1][x][j][0];
                                

                            }
                            else {
                                dp[i][k][x][0] += dp[i - 1][x][j][0];
                            }
                        }
                    }
                }
            }
        }
    }
    ll ans = 0;
    for (ll i = 0; i <= 9; i++) {
        for (ll j = 0; j <= 10; j++) {
            ans += dp[s.size()][i][j][0];
            ans += dp[s.size()][i][j][1];

        }
    }
    return ans;


} 
void solve() {
    ll l, r; cin >> l >> r;
    if (l == 0) {
        cout << get(r) + 1 << endl;

    }
    else cout << get(r) - get(l - 1) << endl;
    //cout<<get(r)<<" " << get(l-1) << endl;




}

signed main() {

    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...