oj.uz

Submission #950465

# Submission time Handle Problem Language Result Execution time Memory
950465 2024-03-20T10:33:47 Z phoenix0423 Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
 1 ms 600 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long 
const int maxn = 1e5 + 5;

int sol(int x){
    if(x < 0) return 0;
    string s = to_string(x);
    vector<vector<vector<int>>> dp(11, vector<vector<int>>(11, vector<int>(2)));
    dp[10][10][1] = 1;
    int n = s.size();
    for(int i = 0; i < n; i++){
        vector<vector<vector<int>>> ndp(11, vector<vector<int>>(11, vector<int>(2)));
        for(int a = 0; a <= 10; a++){
            for(int b = 0; b <= 10; b++){
                for(int c = 0; c < 10; c++){
                    if(a == c || b == c) continue;
                    if(a == 10 && b == 10 && c == 0) continue;
                    if(c < s[i] - '0'){
                        ndp[b][c][0] += dp[a][b][0] + dp[a][b][1];
                    }
                    else if(c == s[i] - '0'){
                        ndp[b][c][0] += dp[a][b][0], ndp[b][c][1] += dp[a][b][1];
                    }
                    else{
                        ndp[b][c][0] += dp[a][b][0];
                    }
                }
            }
        }
        ndp[10][10][0] = 1;
        swap(dp, ndp);
    }
    int ret = 0;
    for(int i = 0; i <= 10; i++){
        for(int j = 0; j < 10; j++){
            for(int k = 0; k < 2; k++) ret += dp[i][j][k];
        }
    }
    return ret + 1;
}
signed main(void){
    int a, b;
    cin>>a>>b;
    cout<<sol(b) - sol(a - 1)<<"\n";
}

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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