Submission #544605

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
544605	2022-04-02T13:31:29 Z	rainboy	Palindrome-Free Numbers (BOI13_numbers)	C	100 / 100	1 ms	340 KB

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

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.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	304 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	252 KB	Output is correct
4	Correct	0 ms	308 KB	Output is correct
5	Correct	0 ms	308 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	304 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	300 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	304 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct

Subtask #2

75.0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	296 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	300 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	300 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	308 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	0 ms	304 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	0 ms	300 KB	Output is correct
27	Correct	0 ms	212 KB	Output is correct
28	Correct	0 ms	212 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Correct	1 ms	212 KB	Output is correct
33	Correct	1 ms	212 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	0 ms	212 KB	Output is correct
36	Correct	0 ms	212 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct
38	Correct	0 ms	212 KB	Output is correct
39	Correct	0 ms	212 KB	Output is correct
40	Correct	0 ms	212 KB	Output is correct
41	Correct	1 ms	212 KB	Output is correct
42	Correct	1 ms	308 KB	Output is correct
43	Correct	0 ms	212 KB	Output is correct
44	Correct	1 ms	304 KB	Output is correct
45	Correct	1 ms	212 KB	Output is correct