제출 #363291

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

numbers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll fin(ll x){
	if(x == -1)return 0;
	ll dp[11][10][20];
	memset(dp,0,sizeof dp);
	string s = to_string(x);
	if(s.size() == 1)return x+1;
	for(int i = 0; i < s[0]-'0'; ++i){
		dp[10][i][0]++;
	}
	bool ok = 1;
	for(int i = 1; i <(int)s.size(); ++i){
		for(int j = 0; j < 10; ++j){
			for(int k = 0; k < 10; ++k){
				for(int x = 0; x < 10; ++x){
					if((j == x || k == x) && j != k)continue;
					dp[k][x][i]+=dp[j][k][i-1];
				}
			}
		}
		for(int j = 0; j < 10; ++j){
			for(int k = 0; k < 10; ++k){
				if(j == 0){
					dp[10][k][i]+=dp[10][j][i-1];
				}
				else{
					if(j != k)dp[j][k][i]+=dp[10][j][i-1];
				}
			}
		}
		if(ok){
			if(s[i] == s[i-1] || (i > 1 && s[i] == s[i-2]))ok=0;
			for(int j = 0; j < s[i]-'0'; ++j){
				if(j == s[i-1]-'0' || (i > 1 && j == s[i-2]-'0'))continue;
				dp[s[i-1]-'0'][j][i]++;
			}

		}
	}
	ll res = 0;
	for(int i = 0; i < 11; ++i){
		for(int j = 0; j < 10; ++j){
			res+=dp[i][j][s.size()-1];
		}
	}
	if(!ok ||( s[s.size()-1] == s[s.size()-2] || (s.size()>2 && s[s.size()-1] == s[s.size()-3]))){
		res--;
	}
	return res+1;
}

int main(){
	ll a, b; cin >> a >> b;
	cout << fin(b)-fin(a-1) << '\n';
}

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