Submission #1142600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142600		h11mpela	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	1 ms	328 KiB

numbers

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll ans(ll x){
    if(x <= 0) return x;
    vector <int> num;

    ll dp[20][11][11][2] = {0}; // pref, last1, last2, tight; 10 <=> digit doesnt exist
    while(x){
        num.push_back(x % 10);
        x /= 10;
    }
    reverse(num.begin(), num.end());
    int n = num.size();

    for(int i = 0; i < n; i++){
        for(int j = 1; j < 10; j++){
            if(i == 0 && j == num[i]){
                dp[i][10][j][1] = 1;
                break;
            }
            dp[i][10][j][0] = 1;
        }
        if(i == 0) continue;
        for(int j = 0; j < 10; j++)
            for(int k = 0; k < 10; k++)
                for(int l = 0; l <= 10; l++)
                    for(int z = 0; z < 2; z++)
                        if(j != k && j != l && !(z && j > num[i])) 
                            dp[i][k][j][z & (j == num[i])] += dp[i - 1][l][k][z];
                    
    }
    ll res = 0;
    for(int i = 0; i <= 10; i++)
        for(int j = 0; j <= 10; j++)
            res += dp[n - 1][i][j][0] + dp[n - 1][i][j][1];

    return res;
}

int main(){
    cin.tie(0);ios_base::sync_with_stdio(0);
    ll a, b; cin >> a >> b;
    cout << ans(b) - ans(a - 1);   
}

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75