Submission #546076

#	Time	Username	Problem	Language	Result	Execution time	Memory
546076		MilosMilutinovic	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	2 ms	312 KiB

numbers

/* idea is correct, find bug */
#include <stdio.h>
#include <string.h>

#define L	18
#define K	10

long long solve(long long n) {
	if (n < 10)
		return n;
	static int dd[L + 1];
	static long long dp[L + 1][K][K][2];
	int l, i, j, d, d_, dd_;

	l = 0;
	while (n > 0) {
		dd[l++] = n % 10;
		n /= 10;
	}
	for (i = 0; i < L + 1; i++)
		for (d = 0; d < K; d++)
			for (d_ = 0; d_ < K; d_++)
				dp[i][d][d_][0] = dp[i][d][d_][1] = 0;
	for (i = 1; i <= dd[l - 1]; i++)
		 for (j = 0; j < (i == dd[l - 1] ? dd[l - 2] + 1 : K); j++)
			if (i != j || (i == 0))
				dp[l - 2][j][i][(i == dd[l - 1] && j == dd[l - 2]) ? 1 : 0] = 1;
	for (i = l - 3; i >= 0; i--)
		for (d = 0; d < K; d++)
			for (d_ = 0; d_ < K; d_++)
				if (d != d_)
					for (dd_ = 0; dd_ < K; dd_++)
						if (d != dd_) {
							dp[i][d][d_][0] += dp[i + 1][d_][dd_][0];
							if (d < dd[i])
								dp[i][d][d_][0] += dp[i + 1][d_][dd_][1];
							if (d == dd[i])
								dp[i][d][d_][1] += dp[i + 1][d_][dd_][1];
						}
	long long ans = 0;
	for (d = 0; d < K; d++)
		for (d_ = 0; d_ < K; d_++)
				ans += dp[0][d][d_][0];
	return ans;
}

long long calc(long long n) {
	long long ans;
	long long d;

	ans = solve(n), d = 9;
	while (d < n) {
		ans += solve(d);
		d = d * 10 + 9;
	}
	return ans;
}

long long brute_force(long long n) {
	static int dd[L + 1];
	long long i, j, l, ans;

	ans = 0;
	for (i = 0; i <= n; i++) {
		l = 0;

		long long x = i;
		while (x > 0) {
			dd[l++] = x % 10;
			x /= 10;
		}

		bool ok = true;
		for (j = 1; j < l; j++)
			ok &= (dd[j] != dd[j - 1] && (j == 1 || (dd[j - 2] != dd[j])));
		ans += ok;
	}
	return ans;
}

int main() {
	long long l, r;

	scanf("%lld%lld", &l, &r);
	if (l <= 100 && r - l <= 100000)
		printf("%lld\n", brute_force(r) - brute_force(l - 1));
	else
		printf("%lld\n", calc(r + 1) - calc(l));
	return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'int main()':
numbers.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |  scanf("%lld%lld", &l, &r);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~

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