Submission #1228783

#TimeUsernameProblemLanguageResultExecution timeMemory
1228783PlayVoltzPalindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
1 ms328 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

string s;
int dp[19][11][11][2][2];

int ooga(int digits, int p2, int p1, bool bounded, bool have){
	if (digits==s.size())return have;
	if (dp[digits][p2+1][p1+1][bounded][have]!=-1)return dp[digits][p2+1][p1+1][bounded][have];
	int res=0, end=(bounded?s[digits]-'0':9);
	for (int i=0; i<=end; ++i){
		if (!i&&p1==-1)res+=ooga(digits+1, -1, -1, 0, 0);
		else res+=ooga(digits+1, p1, i, bounded&(i==end), have|(i==p1)|(i==p2));
	}
	return dp[digits][p2+1][p1+1][bounded][have]=res;
}

int ans(int num){
	if (num<0)return 0;
	s = to_string(num);
	memset(dp, -1, sizeof(dp));
	return ooga(0, -1, -1, 1, 0);
}

int32_t main(){
	int a, b;
	cin>>a>>b;
	cout<<(b-a+1)-ans(b)+ans(a-1);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...