Submission #93502

#	Time	Username	Problem	Language	Result	Execution time	Memory
93502		luckyboy	Palindrome-Free Numbers (BOI13_numbers)	C++14	30.83 / 100	2 ms	508 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;
int 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 = -1;
    ll res = 1;
    while(x){
        q[++top] = x%10;
        x/=10;
    }
    For(i,0,top-1)
        For(j,1,9){
            res += f[i+1][j];
        }
    q[top+1]=-1;
    Ford(i,top,0){
        For(j,0,q[i]-1){
            if(q[i+1]==j) continue;
            if(i==top&&!j) continue;
            if(i<=top-2&&j==q[top+2]) continue;
            if(i){
                For(k,0,9){
                    if(k==q[i+1]||k==j) continue;
                    res += dp[i+1][j][k];
                }
            }
        }
        if(q[i+1]==q[i]) break;
        if(i<=top-2&&q[i]==q[top+2]) break;
        if(!i) ++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: 12.5 / 25
• Subtask 2: 18.333333333333332 / 75