Submission #1173581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173581		AlgorithmWarrior	Palindrome-Free Numbers (BOI13_numbers)	C++20	36.67 / 100	1099 ms	420 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;
}

bool check(long long val){
    vector<int>ult(10,-10);
    int id=0;
    while(val){
        if(id-ult[val%10]<=2)
            return 0;
        ult[val%10]=id;
        val/=10;
        ++id;
    }
    return 1;
}

long long brut(long long a,long long b){
    long long i;
    long long cnt=0;
    for(i=a;i<=b;++i){
        long long val=i;
        cnt+=check(val);
    }
    return cnt;
}

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

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