Submission #97243

#	Time	Username	Problem	Language	Result	Execution time	Memory
97243		Shafin666	Palindrome-Free Numbers (BOI13_numbers)	C++14	66.67 / 100	3 ms	432 KiB

numbers

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<ll, ll>
#define to second
#define cost first
typedef long long ll;
typedef long double ld;
using namespace std;

std::vector<int> num;
int dp[20][12][12][2][2];

int answer(int idx, int a, int b, int noconst, int start) {
	if(idx == (int)num.size()) return 1;
	if(dp[idx][a][b][noconst][start] != -1) return dp[idx][a][b][noconst][start];

	int ret = 0, limit;
	if(noconst) limit = 9; else limit = num[idx];

	for(int i = 0; i <= limit; i++) {
		if(i == a || i == b) continue;
		if(i == 0 && start == 0) ret += answer(idx+1, 10, 10, 1, 0);
		else ret += answer(idx+1, b, i, noconst | (i < num[idx]), 1);
	} return dp[idx][a][b][noconst][start] = ret;
}

int solve(ll n) {
	//if(n < 0) return 0;
	//if(n < 10) return n+1;

	num.clear();
	while(n) {
		num.pb(n%10);
		n /= 10;
	} 
	reverse(num.begin(), num.end());
	memset(dp, -1, sizeof dp);
	return answer(0, 10, 10, 0, 0);
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	ll a, b;

	cin >> a >> b;
	ll ans = solve(b);
	ans -= solve(a-1);

	cout << ans << endl;
    return 0;
}

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