oj.uz

Submission #93505

# Submission time Handle Problem Language Result Execution time Memory
93505 2019-01-09T02:53:23 Z luckyboy Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 15 ms 420 KB 
/**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.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 292 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 1 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 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 3 ms 376 KB Output is correct
5 Correct 2 ms 396 KB Output is correct
6 Correct 2 ms 420 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 276 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 376 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 15 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 376 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