답안 #544605

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
544605 2022-04-02T13:31:29 Z rainboy Palindrome-Free Numbers (BOI13_numbers) C
100 / 100
1 ms 340 KB
#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);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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