제출 #815995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
815995		QwertyPi	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	2 ms	360 KiB

numbers

#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 / 25
• Subtask 2: 75 / 75