Submission #546048

#	Time	Username	Problem	Language	Result	Execution time	Memory
546048		MilosMilutinovic	Palindrome-Free Numbers (BOI13_numbers)	C++14	12.08 / 100	1 ms	292 KiB

numbers

/* idea is correct, find bug */
#include <stdio.h>
#include <string.h>

#define L	18
#define K	10

long long solve(int n) {
	static int dd[L + 1];
	static long long dp[L + 1][K][K][2];
	int l, i, d, d_, dd_;

	l = 0;
	while (n > 0) {
		dd[l++] = n % 10;
		n /= 10;
	}
//	for (i = 0; i < l; i++)
//		printf("%d", dd[i]);
//	printf("\n");
	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;
	dp[l][0][0][1] = 1;
	for (i = l - 1; i >= 0; i--)
		for (d = 0; d < K; d++)
			for (d_ = 0; d_ < K; d_++)
				if (d != d_)
					for (dd_ = 0; dd_ < K; dd_++) {
						dp[i][d][d_][0] += dp[i + 1][d_][dd_][0];
						if (i < l - 1 || 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];
					}
//	for (i = l - 1; i >= 0; i--)
//		for (d = 0; d < K; d++)
//			for (d_ = 0; d_ < K; d_++)
//				printf("dp[%d][%d][%d][0]: %d\n", i, d, d_, dp[i][d][d_][0]);
	long long ans = 0;
	for (d = 0; d < K; d++)
		for (d_ = 0; d_ < K; d_++)
				ans += dp[0][d][d_][0];
	return ans;
}

int main() {
	long long l, r;

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

Compilation message (stderr)

numbers.cpp: In function 'int main()':
numbers.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%lld%lld", &l, &r);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~

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