Submission #497316

#	Time	Username	Problem	Language	Result	Execution time	Memory
497316		zhougz	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	424 KiB

numbers

/**
 *    author: zhougz
 *    created: 23/12/2021 10:31:38
**/
#include <bits/stdc++.h>

using namespace std;

long long memo[21][10][10][2];
int d[21];

long long dp(int len, int first, int second, int bounded) {
	if (len <= 2) {
		return 1;
	}
	long long &res = memo[len][first][second][bounded];
	if (res != -1) {
		return res;
	}
	res = 0;
	if (!bounded) {
		for (int i = 0; i <= 9; i++) {
			if (i == first || i == second) {
				continue;
			}
			res += dp(len - 1, second, i, false);
		}
		return res;
	}
	for (int i = 0; i <= d[len - 2]; i++) {
		if (i == first || i == second) {
			continue;
		}
		res += dp(len - 1, second, i, i == d[len - 2]);
	}
	return res;
}

long long slv(long long x) {
	memset(memo, -1, sizeof memo);
	memset(d, 0, sizeof d);
	int len = 0;
	do { // In case x == 0
		d[++len] = x % 10;
		x /= 10;
	} while (x != 0);
	long long res = 1;
	for (int i = 2; i <= len; i++) {
		for (int j = 1; j <= 9; j++) {
			res += dp(i, j, j, false);
		}
	}
	for (int j = 1; j <= d[len]; j++) {
		res += dp(len + 1, j, j, j == d[len]);
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	long long a, b;
	cin >> a >> b;
	cout << slv(b) - (a != 0 ? slv(a - 1) : 0) << '\n';
	return 0;
}

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