Submission #544605

#	Time	Username	Problem	Language	Result	Execution time	Memory
544605		rainboy	Palindrome-Free Numbers (BOI13_numbers)	C11	100 / 100	1 ms	340 KiB

numbers

#include <stdio.h>

#define L	19
#define D	10

long long dp[L + 1][D][D];

void init() {
	int l, d1, d2, d3;

	for (d1 = 0; d1 < D; d1++)
		for (d2 = 0; d2 < D; d2++)
			if (d1 != d2)
				dp[2][d1][d2] = 1;
	for (l = 2; l < L; l++)
		for (d1 = 0; d1 < D; d1++)
			for (d2 = 0; d2 < D; d2++) {
				long long x = dp[l][d1][d2];

				if (x == 0)
					continue;
				for (d3 = 0; d3 < D; d3++)
					if (d3 != d1 && d3 != d2)
						dp[l + 1][d2][d3] += x;
			}
}

long long solve(long long n) {
	static int dd[L];
	int l, i, d1, d2;
	long long ans;

	if (n <= 10)
		return n;
	l = 0;
	while (n > 0) {
		dd[l++] = n % 10;
		n /= 10;
	}
	ans = 10;
	for (i = 2; i < l; i++)
		for (d1 = 0; d1 < D; d1++)
			for (d2 = 1; d2 < D; d2++)
				ans += dp[i][d1][d2];
	for (i = l - 1; i >= 0; i--)
		if (i == l - 1)
			for (d2 = 1; d2 < dd[i]; d2++)
				for (d1 = 0; d1 < D; d1++)
					ans += dp[i + 1][d1][d2];
		else {
			d2 = dd[i + 1];
			for (d1 = 0; d1 < dd[i]; d1++)
				if (i + 2 == l || d1 != dd[i + 2])
					ans += dp[i + 2][d1][d2];
			if (dd[i] == dd[i + 1] || i + 2 < l && dd[i] == dd[i + 2])
				break;
		}
	return ans;
}

int main() {
	long long l, r;

	init();
	scanf("%lld%lld", &l, &r);
	printf("%lld\n", solve(r + 1) - solve(l));
	return 0;
}

Compilation message (stderr)

numbers.c: In function 'solve':
numbers.c:55:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   55 |    if (dd[i] == dd[i + 1] || i + 2 < l && dd[i] == dd[i + 2])
      |                              ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
numbers.c: In function 'main':
numbers.c:65:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%lld%lld", &l, &r);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~

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