Submission #1166399

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

numbers

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[20][12][12][2];
//index,first last,second last,fix element?
ll f(int idx,int first,int second,bool con,string &s){
    if(idx==s.size()) return 1;
    if(dp[idx][first][second][con]!=-1) return dp[idx][first][second][con];
    ll ret=0;
    int now=con?s[idx]-'0':9;
    for(int i=0;i<=now;i++){
        if(i==first || i==second) continue;
        if(i==0 && first==10) ret+=f(idx+1,10,10,i==now && con,s);
        else ret+=f(idx+1,i,first,i==now && con,s);
    }
    return dp[idx][first][second][con]=ret;
}
ll solve(ll n){
    if(n<0LL) return 0;
    for(int i=0;i<20;i++) for(int j=0;j<12;j++) for(int ii=0;ii<12;ii++) dp[i][j][ii][0]=dp[i][j][ii][1]=-1;
    string s=to_string(n);
    //true=fix constraint not exceed its value
    return f(0,10,10,true,s);

}
int main(){
    ll a,b;
    cin>>a >>b;
    ll ans=solve(b)-solve(a-1LL);
    cout<<ans;
}

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