Submission #137506

#	Time	Username	Problem	Language	Result	Execution time	Memory
137506		silxikys	Palindrome-Free Numbers (BOI13_numbers)	C++14	37.50 / 100	3 ms	504 KiB

numbers

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

int dig[20];
ll dp[20][11][11][2]; //place, 2, 1, isover

int f(int len, int d1, int d2, bool under) {
    if (len == -1) return 1;
    ll& res = dp[len][d1][d2][under];
    if (res >= 0) return res;
    if (under) {
        res = 0;
        for (int d = 0; d <= 9; d++) {
            if (d == d1 || d == d2) continue;
            res += f(len-1,d2,d,under);
        }
        return res;
    }
    else {
        res = 0;
        for (int d = 0; d < dig[len]; d++) {
            if (d == d1 || d == d2) continue;
            res += f(len-1,d2,d,true);
        }
        if (dig[len] != d1 && dig[len] != d2) 
            res += f(len-1,d2,dig[len],under);
        return res;
    }
}

ll solve(ll x) {
    if (x == -1) return 0;
    memset(dp,-1,sizeof dp);
    int len = 0;
    while (x) {
        dig[len++] = x % 10;
        x /= 10;
    }
    return f(len-1,10,10,0);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll a, b; cin >> a >> b;
    cout << (solve(b) - solve(a-1)) << '\n';
    //cout << solve(a) << '\n';
}

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