Submission #1288581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288581		Faisal_Saqib	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	1 ms	1340 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;
}
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;
                }
            }
        }
    }
    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;
                for(int nd=(!nz);nd<=9+(!nz);nd++)
                {
                    if(nd==10)
                    {
                        dp[i+1][k][nd][0]+=dp[i][j][k][0];
                        dp[i+1][k][nd][0]+=dp[i][j][k][1];
                        continue;
                    }
                    if((nd==j or nd==k) and nz)continue;
                    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] 
                    {
                        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;
}
int main()
{
    ios::sync_with_stdio(0);
    cout.tie(0);cin.tie(0);
    ll a,b,cnt=0;
    cin>>a>>b;
    cout<<compute(to_string(b))-compute(to_string(a))+check(a)<<endl;
    return 0;
}

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