Submission #117129

#	Time	Username	Problem	Language	Result	Execution time	Memory
117129		MB81	Palindrome-Free Numbers (BOI13_numbers)	C++11	100 / 100	4 ms	412 KiB

numbers

#include <bits/stdc++.h>

using namespace std;
typedef long long int64;
typedef pair<int,int> pii;
typedef pair<int64,int> pii32;
typedef pair<int64,int64> pii64;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int maxn = 1e5+10;
const int64 MO = 1e9+7;
const int64 IN = 1e9;

int64 dp[20][11][11];
int a[20];
int64 n, m;

int getl (int64 x) {
	int res = 0;
	while (x) {
		res++;
		x /= 10;
	}
	return res;
}

bool ok (int64 x) {
	int len = getl(x);
	for (int i = 0; i < len; i++) {
		a[i] = x % 10;
		x /= 10;
	}
	for (int i = 0; i < len - 1; i++)
		if (a[i] == a[i + 1])
			return 0;
	for (int i = 0; i < len - 2; i++)
		if (a[i] == a[i + 2])
			return 0;
	return 1;
}

int64 solve (int64 x) {
	if (x == -1)
		return 0;
	if (x == 0)
		return 1;
	int len = getl(x);
	memset(dp, 0, sizeof dp);
	for (int i = 1; i < 10; i++)
		dp[0][10][i] = 1;
	int64 ans = ((len > 1) ? 9 : 0);
	for (int i = 1; i < len - 1; i++) {
		for (int t = 0; t <= 10; t++)
			for (int j = 0; j <= 9; j++)
				for (int k = 0; k <= 10; k++) {
					if (j == t || j == k)
						continue;
					dp[i][t][j] += dp[i - 1][k][t];	
				}
		for (int t = 0; t <= 10; t++)
			for (int j = 0; j <= 10; j++)
				ans += dp[i][t][j];
	}
	int64 tmp = x;
	for (int l = len - 1; l >= 0; l--) {
		a[l] = tmp % 10;
		tmp /= 10;
	}
	for (int l = 0; l < len; l++) {
		memset(dp, 0, sizeof dp); 
		if (l == 0)
			for (int i = 1; i < a[0]; i++)
				dp[0][10][i] = 1;
		else
			dp[0][10][a[0]] = 1;
		for (int i = 1; i < len; i++) 
			for (int t = 0; t <= 10; t++)
				for (int j = 0; j <= 9; j++)
					for (int k = 0; k <= 10; k++) {
						if (j == t || j == k)
							continue;
						if ((i == l && j >= a[i]) || (i < l && j != a[i]))
							continue;
						dp[i][t][j] += dp[i - 1][k][t];
					}
		for (int i = 0; i <= 10; i++)
			for (int t = 0; t <= 10; t++)
				ans += dp[len - 1][i][t];
	}
	if (ok(x))
		ans++;
	return ans + 1;
}

int main () {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	cout << solve(m) - solve(n - 1) << "\n";
}

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