제출 #1228783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228783		PlayVoltz	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	1 ms	328 KiB

numbers

#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);
}

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