Submission #92138

#	Time	Username	Problem	Language	Result	Execution time	Memory
92138		ngot23	Palindrome-Free Numbers (BOI13_numbers)	C++11	100 / 100	2 ms	380 KiB

numbers

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define mp make_pair
#define pii pair<int, int>
#define PB push_back
#define F first
#define S second
#define Task ""
using namespace std;
long long dp[22][10][10], f[22][10], a, b;
int cnt, c[22];

void pre() {
    rep(i, 0, 9) {
        f[1][i]=1;
        f[2][i]=9;
    }
    rep(i, 0, 9)
        rep(j, 0, 9) {
            if(i!=j) dp[2][i][j]=1;
        }

    rep(l, 3, 19) {
        rep(i, 0, 9) {
            rep(j, 0, 9) {
                if(i==j) continue;
                rep(k, 0, 9) {
                    if(i==k||j==k) continue;
                    dp[l][i][j]+=dp[l-1][j][k];
                }
            }
            rep(j, 0, 9) f[l][i]+=dp[l][i][j];
        }
    }
}

long long tinh(long long a) {
    if(a<0) return 0;
    if(a<=9) return a+1;

    cnt=0;
    while(a) {
        c[++cnt]=a%10;
        a/=10;
    }
    long long ret=0;
    rep(k, 2, cnt-1)
        rep(i, 1, 9) ret+=f[k][i];

    if(cnt>1) ret+=10;

    for(int i=c[cnt]-1 ; i>0 ; --i)
        ret+=f[cnt][i];

    for(int i=cnt-1 ; i ; --i) {
        for(int j=c[i]-1 ; j>=0 ; --j) {
            if(c[i+1]==j||(i<=cnt-2&&c[i+2]==j)) continue;
            ret+=dp[i+1][c[i+1]][j];
        }
        if((c[i]==c[i+1])||(i<=cnt-2&&c[i]==c[i+2])) break;

        if(i==1) ++ret;
    }

    return ret;
}

void koFull() {
    pre();
    cout << tinh(b)-tinh(a-1) << '\n';
    //cout << tinh(b) << '\n';
}

bool check(int u) {
    cnt=0;
    while(u) {
        c[++cnt]=u%10;
        u/=10;
    }
    rep(i, 1, cnt-1) {
        if(c[i]==c[i+1]) return false;
        if(i<=cnt-2&&c[i]==c[i+2]) return false;
    }
    return true;
}

void trau() {
    int ret=0, ret1=0;
    rep(i, a, b) {
        if(!check(i)) continue;
       ret++;
       // else ret++;
    }
    cout << ret;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    cin >> a >> b;
    //srand(time(NULL));
    //a=rand()%9+1;
    //b=a+(1ll*rand()*rand()%10 + 1);
    koFull();
    //trau();
    return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'void trau()':
numbers.cpp:88:16: warning: unused variable 'ret1' [-Wunused-variable]
     int ret=0, ret1=0;
                ^~~~

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