oj.uz

Submission #546076

# Submission time Handle Problem Language Result Execution time Memory
546076 2022-04-06T08:35:15 Z MilosMilutinovic Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 2 ms 312 KB 
/* 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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