Submission #1307097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307097		StefanSebez	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	1 ms	580 KiB

numbers

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int lg=18;
ll dp[lg+1][10][10];
ll dp1[lg+1][10];
ll dp2[lg+1];
ll Calc(ll x){
    if(x==-1)return 0;
    vector<int>digits;
    while(x>0)digits.pb(x%10),x/=10;
    reverse(digits.begin(),digits.end());
    ll res=0;
    int m=digits.size();
    for(int i=1;i<m;i++){
        for(int a=0;a<digits[i];a++)if(i<=1||a!=digits[i-2]){
            res+=dp[m-i-1][digits[i-1]][a];
        }
        if((i>=1&&digits[i]==digits[i-1])||(i>=2&&digits[i]==digits[i-2]))break;
    }
    bool palindrom=false;
    for(int i=0;i<m;i++){
        if((i>=1&&digits[i]==digits[i-1])||(i>=2&&digits[i]==digits[i-2]))palindrom=true;
    }
    if(!palindrom)res++;
    if(m>=1){
        for(int a=1;a<digits[0];a++)res+=dp1[m-1][a];
        res+=dp2[m-1];
    }
    return res;
}
int main(){
    for(int a=0;a<10;a++){
        for(int b=0;b<10;b++)if(a!=b){
            dp[0][a][b]=1;
        }
        dp1[0][a]=1;
    }
    dp2[0]=1;
    for(int i=1;i<=lg;i++){
        for(int a=0;a<10;a++){
            for(int b=0;b<10;b++)if(a!=b){
                for(int c=0;c<10;c++)if(a!=c){
                    dp[i][a][b]+=dp[i-1][b][c];
                }
                dp1[i][a]+=dp[i-1][a][b];
            }
            if(a!=0)dp2[i]+=dp1[i-1][a];
            else dp2[i]+=dp2[i-1];
        }
    }
    ll a,b;scanf("%lld%lld",&a,&b);
    printf("%lld\n",Calc(b)-Calc(a-1));
    return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'int main()':
numbers.cpp:57:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     ll a,b;scanf("%lld%lld",&a,&b);
      |            ~~~~~^~~~~~~~~~~~~~~~~~

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