Submission #1288903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288903		g4yuhg	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	2 ms	584 KiB

numbers

#include<bits/stdc++.h>
typedef long long ll;
#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 200055
#define LOG 17
using namespace std;

const ll mod = 1e9 + 7;

ll inv2 = (mod + 1) / 2;

bool ghuy4g;

ll n;

string s;

ll f[20][2][12][12][2];

ll dp(ll i, ll lower, ll l1, ll l2, ll bd) {
	if (i > n) {
		return 1;
	}
	if (f[i][lower][l1][l2][bd] != -1) {
		return f[i][lower][l1][l2][bd];
	}
	ll res = 0;
	for (int j = 0; j <= 9; j ++) {
		if (bd && (j == l1 || j == l2)) continue;
		if (lower == 0 && j > s[i] - '0') continue;
		ll new_bd = bd;
		if (j > 0) new_bd = 1;
		ll new_lower = lower, new_l2 = l1, new_l1 = j;
		if (new_bd == 0) {
			new_l1 = 10; new_l2 = 10;
		}
		if (j < s[i] - '0') {
			new_lower = 1;
		}
		res += dp(i + 1, new_lower, new_l1, new_l2, new_bd);
	}
	f[i][lower][l1][l2][bd] = res;
	return res;
}

ll dem(ll u) {
	memset(f, -1, sizeof(f));
	s = to_string(u);
	n = s.size();
	s = '*' + s;
	return dp(1, 0, 10, 10, 0);
}

bool klinh;

signed main() {
   // freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    ll a, b;
    cin >> a >> b;
    ll R = dem(b), L = 0;
    if (a >= 1) {
    	L = dem(a - 1);
    }
    else {
    	L = 0; // so 0 cung la 1 so palindome free
    }
    cout << R - L;
    
   	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

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