oj.uz

Submission #815995

# Submission time Handle Problem Language Result Execution time Memory
815995 2023-08-09T03:28:24 Z QwertyPi Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 2 ms 360 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

int dp[20][10][10][3];

bool ok(int x){
    string s = to_string(x); int n = s.size();
    for(int i = 0; i < n - 1; i++) if(s[i] == s[i + 1]) return false;
    for(int i = 0; i < n - 2; i++) if(s[i] == s[i + 2]) return false;
    return true;
}

int count_prefix(int r){
    memset(dp, 0, sizeof(dp));
    int ans = 0;
    for(int i = 0; i < 100; i++) ans += (i <= r) && ok(i);
    int pw10 = 100;
    for(int x = 0; x < 10; x++){
        for(int y = 0; y < 10; y++){
            if(x == y) continue;
            int val = x + y * 10;
            int type = 0; if(val > r % pw10) type = 2; if(val == r % pw10) type = 1; 
            dp[2][x][y][type]++;
        }
    }

    for(int d = 3; d <= 18; d++){
        pw10 *= 10;
        for(int x = 0; x < 10; x++){
            for(int y = 0; y < 10; y++){
                for(int ty = 0; ty < 3; ty++){
                    for(int z = 0; z < 10; z++){
                        if(z == x || z == y) continue;
                        int nty;
                        if(z > r % pw10 / (pw10 / 10)) nty = 2;
                        else if(z == r % pw10 / (pw10 / 10)) nty = ty;
                        else nty = 0;
                        dp[d][y][z][nty] += dp[d - 1][x][y][ty];
                    }
                }
            }
        }
        
        for(int x = 0; x < 10; x++){
            for(int y = 1; y < 10; y++){
                for(int ty = 0; ty < 3; ty++){
                    if(pw10 - 1 > r && ty == 2) continue;
                    ans += dp[d][x][y][ty];
                }
            }
        }
    }
    return ans;
}

int32_t main(){
    cin.tie(0); cout.tie(0)->sync_with_stdio(false);
    int a, b; cin >> a >> b;
    int ans = count_prefix(b) - count_prefix(a - 1);
    cout << ans << endl;
}

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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