Submission #93505

#	Time	Username	Problem	Language	Result	Execution time	Memory
93505		luckyboy	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	15 ms	420 KiB

numbers

/**GreenGrass**/
#include <bits/stdc++.h>
#define Ford(i,a,b) for(int i=a;i>=b;--i)
#define Forr(i,a,b) for(int i=a;i<b;++i)
#define For(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef long long ll;
ll dp[22][10][10], f[22][10], q[22], top;
void Pre(){
    For(i,1,9){
        f[1][i] = 1;
        f[2][i] = 9;
    }
    For(i,0,9)
        For(j,0,9)
            if(i!=j){
                dp[2][i][j]=1;
            }
    For(le,3,19){
        For(i,0,9){
            For(j,0,9){
                if(i==j) continue;
                For(k,0,9){
                    if(i==k||j==k) continue;
                    dp[le][i][j] += dp[le-1][j][k];
                }
                f[le][i] += dp[le][i][j];
            }
        }
    }
}
ll Calc(ll x){
    if(x<10) return x+1;
    top = 0;
    ll res = 10;
    while(x){
        q[++top] = x%10;
        x/=10;
    }
    For(i,2,top-1)
        For(j,1,9){
            res += f[i][j];
        }
    For(i,1,q[top]-1)
        res += f[top][i];
    Ford(i,top-1,1){
        For(j,0,q[i]-1){
            if(q[i+1]==j||(i<=top-2&&j==q[i+2])) continue;
            res += dp[i+1][q[i+1]][j];
        }
        if(q[i+1]==q[i]||(i<=top-2&&q[i]==q[i+2])) break;
        if(i==1) ++res;
    }
    return res;
}
void Setup(){
    ll a, b;
    cin >> a >> b;
    cout << Calc(b)-Calc(a-1);
}
int main(){
    ios_base::sync_with_stdio(NULL);
    cin .tie(NULL); cout .tie(NULL);
//    freopen("BlaBla.inp" , "r", stdin);
//    freopen("BlaBla.out", "w", stdout);
    Pre();
    Setup();
    return 0;
}

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