Submission #1288580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288580		Faisal_Saqib	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	2 ms	596 KiB

numbers

#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool check(ll x)
{
    string s=to_string(x);
    for(int i=0;i<s.size();i++)
    {
      if(i>0 and s[i]==s[i-1])return 0;
      if(i>1 and s[i-2]==s[i])return 0;
    }
    return 1;
}
set<string> pre[100];
// len 2ndlast last equal/less anynonzero

ll dp[20][12][12][4];
ll compute(string b)
{
    int n=b.size();
    for(int i=0;i<20;i++)
    {
        for(int j=0;j<12;j++)
        {
            for(int k=0;k<12;k++)
            {
                for(int p=0;p<4;p++)
                {
                    dp[i][j][k][p]=0;
                }
            }
        }
    }
    // assume trailing zero is equal to 10 then we can do it easily
    dp[0][10][10][1]=1;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=10;j++)
        {
            for(int k=0;k<=10;k++)
            {
                int nz=1;
                if(j==10 and k==10)nz=0;
                // if(dp[i][j][k][0]>0 or dp[i][j][k][1]>0)
                // {
                //     cout<<"DP: "<<i<<' '<<j<<' '<<k<<endl;
                //     cout<<dp[i][j][k][0]<<endl;
                //     cout<<dp[i][j][k][1]<<endl;
                // }
                {
                    // nz=1 [0,9]
                    // nz=0 [1,10]
                    for(int nd=(!nz);nd<=9+(!nz);nd++) // is non zero then we can place 0 else we always place 10
                    {
                        // cout<<"AT "<<nd<<endl;
                        if(nd==10) // adding leading zeros hope so no issue
                        {
                            // cout<<"FUCK "<<i<<' '<<j<<' '<<k<<' '<<0<<' '<<dp[i][j][k][1]<<endl;
                            dp[i+1][k][nd][0]+=dp[i][j][k][0];
                            dp[i+1][k][nd][0]+=dp[i][j][k][1];
                            continue;
                        }
                        // we want a real digit
                        if((nd==j or nd==k) and nz)continue;
                        // if(i==0 and j==10 and k==10)
                        // {
                        //     cout<<"Update "<<nd<<endl;
                        // }
                        if(nd==(b[i]-'0'))
                        {
                            dp[i+1][k][nd][0]+=dp[i][j][k][0]; // already smaller
                            dp[i+1][k][nd][1]+=dp[i][j][k][1];
                        }
                        else if(nd<(b[i]-'0'))
                        {
                            dp[i+1][k][nd][0]+=dp[i][j][k][0]; // already smaller
                            dp[i+1][k][nd][0]+=dp[i][j][k][1]; // equal before this now smaller
                        }
                        else// nd > b[i-1] 
                        {
                            // only possible 
                            dp[i+1][k][nd][0]+=dp[i][j][k][0]; // if smaller already we can this else we will go above b which we ddont want
                        }
                    }
                }
            }
        }
    }
    ll ans=0;
    for(int l=0;l<=10;l++)
    {
        for(int l1=0;l1<=10;l1++)
        {
            ans+=dp[n][l][l1][0];
            ans+=dp[n][l][l1][1];
        }
    }
    return ans;
    // dp[n][l1][l2][]
}
int main()
{
    
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cout.tie(0);cin.tie(0);
    ll a,b,cnt=0;
    cin>>a>>b;
    // for(int x=0;x<=9;x++)pre[1].insert(to_string(x));
    // for(int x=10;x<=99;x++)if(check(x))pre[2].insert(to_string(x));
    // for(int i=2;i<9;i++)
    // {
    //     for(auto x:pre[i])
    //     {
    //         // no leading zeros allowed
    //         // if(x=='0')continue; 
    //         for(char j='0';j<='9';j++)
    //         {
    //             if(x.back()==j)continue;
    //             if(x.size()>=2 and x[x.size()-2]==j)continue;
    //             pre[i+1].insert(x+j);
    //         }
    //     }
    //     cout<<pre[i].size()<<endl;;
    // }
    // ll sm=0;
    // for(int i=1;i<=9;i++)
    // {
    //     sm+=pre[i].size();
    //     cout<<sm<<endl;
    // }
    // for(ll x=0;x<=b;x++)
    // {
    //     if(check(x))
    //     {
    //         cnt++;
    //     }
    // }
    // cout<<"OG: "<<cnt<<endl;
    cout<<compute(to_string(b))-compute(to_string(a))+check(a)<<endl;
    return 0;
}

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