Submission #1295322

#TimeUsernameProblemLanguageResultExecution timeMemory
1295322thesentroPalindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
2 ms584 KiB
/*
 _____ _          ____             _             
|_   _| |__   ___/ ___|  ___ _ __ | |_ _ __ ___  
  | | | '_ \ / _ \___ \ / _ \ '_ \| __| '__/ _ \ 
  | | | | | |  __/___) |  __/ | | | |_| | | (_) |
  |_| |_| |_|\___|____/ \___|_| |_|\__|_|  \___/ 
*/
 
#include <bits/stdc++.h>
// #pragma GCC optimize("O3")
using namespace std;
#define ll long long

ll mod = 1e9+7;

ll binpow(ll a, ll b)
{
    ll res = 1;
    while (b>0)
    {
        if (b&1)
            res = (res*a)%mod;
        a = (a*a)%mod;
        b>>=1;
    }
    return res;
}
ll gcd(ll x, ll y)
{
    if (y==0)
        return x;
    return gcd(y, x%y);
}
ll dp[20][11][11][2][2];
void cln()
{
    for (int i=0 ; i<20 ; i++)
    {
        for (int j=0 ; j<11 ; j++)
        {
            for (int k=0 ; k<11 ; k++)
            {
                for (int q=0 ; q<2 ; q++)
                {
                    for (int qq =0 ; qq<2 ; qq++)
                    {
                        dp[i][j][k][q][qq] = 0;
                    }
                }
            }
        }
    }
}
ll cnt(ll x)
{
    if (x==-1) return 0;
    cln();
    dp[0][10][10][1][1] = 1;
    string s = to_string(x);
    vector<ll>v;
    v.push_back(-1);
    for (int i=0 ; i<s.size() ; i++) v.push_back(s[i]-'0');

    for (int st=1 ; st<v.size() ; st++)
    {
        for (int i=0 ; i<=10 ; i++)
        {
            for (int j=0 ; j<=10 ; j++)
            {
                for (int k=0 ; k<=10 ; k++)
                {
                    for (int j1=0 ; j1<=1 ; j1++)
                    {
                        for (int j2=0 ; j2<=1 ; j2++)
                        { 
                            if (j2==1 and k==0) continue;
                            if (k==10 and j2!=1)
                                continue;
                            if (k==10 and j2==1){
                                dp[st][j][k][((j1)&(v[st]==0))][1] += dp[st-1][i][j][j1][j2];
                                continue;}
                            if (j1==1)
                            {
                                if (k==v[st])
                                {
                                    if (k!=j and k!=i)
                                        dp[st][j][k][1][0] += dp[st-1][i][j][j1][j2];
                                }
                                if (k<v[st])
                                {
                                    if (k!=j and k!=i)
                                        dp[st][j][k][0][0] += dp[st-1][i][j][j1][j2];
                                }
                            }
                            else
                            {
                                if (k!=j and k!=i)
                                    dp[st][j][k][0][0] += dp[st-1][i][j][j1][j2];
                            }
                        }
                    }
                }   
            }
        }
    }
    ll sum=0;
    for (int i=0 ; i<=10 ; i++)
    {
        for (int j=0 ; j<=10 ; j++)
        {
            for (int j1=0 ; j1<2 ; j1++)
            {
                for (int j2=0 ; j2<2 ; j2++)
                    sum += dp[v.size()-1][i][j][j1][j2];
            }
        }
    }
    // cout<<dp[1][10][10][0][1]<<endl;
    return sum;

}
void solve()
{   
    ll l,r;
    cin>>l>>r;
    cout<<cnt(r)-cnt(l-1);
}
int main()
{
    // freopen ("input.txt","r",stdout);
    // freopen ("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll tt = 1;
    // cin>>tt;
    while (tt--)
    {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...