답안 #546076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
546076	2022-04-06T08:35:15 Z	MilosMilutinovic	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	2 ms	312 KB

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

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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	2 ms	212 KB	Output is correct
5	Correct	0 ms	212 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	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	1 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	2 ms	284 KB	Output is correct
15	Correct	2 ms	212 KB	Output is correct
16	Correct	1 ms	212 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	212 KB	Output is correct
20	Correct	2 ms	212 KB	Output is correct

Subtask #2

75.0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 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	1 ms	212 KB	Output is correct
11	Correct	1 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	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	312 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	2 ms	212 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	1 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	2 ms	212 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct
38	Correct	1 ms	212 KB	Output is correct
39	Correct	1 ms	212 KB	Output is correct
40	Correct	1 ms	212 KB	Output is correct
41	Correct	1 ms	212 KB	Output is correct
42	Correct	1 ms	212 KB	Output is correct
43	Correct	1 ms	212 KB	Output is correct
44	Correct	1 ms	212 KB	Output is correct
45	Correct	1 ms	212 KB	Output is correct