oj.uz

Submission #92138

# Submission time Handle Problem Language Result Execution time Memory
92138 2019-01-01T15:47:52 Z ngot23 Palindrome-Free Numbers (BOI13_numbers) C++11
100 / 100
 2 ms 380 KB 
#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

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 292 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 380 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 376 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 2 ms 380 KB Output is correct
37 Correct 2 ms 376 KB Output is correct
38 Correct 2 ms 376 KB Output is correct
39 Correct 2 ms 376 KB Output is correct
40 Correct 2 ms 376 KB Output is correct
41 Correct 2 ms 376 KB Output is correct
42 Correct 2 ms 376 KB Output is correct
43 Correct 2 ms 376 KB Output is correct
44 Correct 2 ms 376 KB Output is correct
45 Correct 2 ms 376 KB Output is correct