Submission #1173567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173567		AlgorithmWarrior	Palindrome-Free Numbers (BOI13_numbers)	C++20	76.67 / 100	0 ms	328 KiB

numbers

#include <bits/stdc++.h>

using namespace std;

long long dp[23][13][13][2];
int cifre[23];

long long digit_dp(long long val){
    if(val<10)
        return val+1;
    int nrc=0;
    while(val){
        cifre[++nrc]=val%10;
        val/=10;
    }
    int cif1,cif2,cif3,nrcif;
    for(cif1=0;cif1<10;++cif1)
        for(cif2=0;cif2<10;++cif2)
            if(cif1!=cif2){
                dp[2][cif1][cif2][0]=1;
                if(10*cif1+cif2<=10*cifre[2]+cifre[1])
                    dp[2][cif1][cif2][1]=1;
            }
    for(nrcif=3;nrcif<=nrc;++nrcif)
        for(cif1=0;cif1<10;++cif1)
            for(cif2=0;cif2<10;++cif2)
                if(cif1!=cif2){
                    dp[nrcif][cif1][cif2][0]=0;
                    dp[nrcif][cif1][cif2][1]=0;
                    for(cif3=0;cif3<10;++cif3)
                        if(cif1!=cif3){
                            if(cif1>cifre[nrcif])
                                dp[nrcif][cif1][cif2][0]+=dp[nrcif-1][cif2][cif3][0];
                            else
                            if(cif1<cifre[nrcif]){
                                dp[nrcif][cif1][cif2][0]+=dp[nrcif-1][cif2][cif3][0];
                                dp[nrcif][cif1][cif2][1]+=dp[nrcif-1][cif2][cif3][0];
                            }
                            else{
                                dp[nrcif][cif1][cif2][0]+=dp[nrcif-1][cif2][cif3][0];
                                dp[nrcif][cif1][cif2][1]+=dp[nrcif-1][cif2][cif3][1];
                            }
                        }
                }
    long long ans=10;
    for(nrcif=2;nrcif<=nrc;++nrcif)
        for(cif1=1;cif1<10;++cif1)
            for(cif2=0;cif2<10;++cif2)
                ans+=dp[nrcif][cif1][cif2][nrcif==nrc];
    return ans;
}

int main()
{
    long long a,b;
    cin>>a>>b;
    cout<<digit_dp(b)-digit_dp(a-1);
    return 0;
}

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