Submission #1257440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257440		terracottalite	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	1 ms	736 KiB

numbers

#include <stdio.h>
#include <string.h>

char a[32];
char b[32];

void printmat(long long *a, int c) {
	putchar('\n');
	for (int i=0;i<100;i++) {
		if (i%10 == 0) putchar('\n');
		//printf("%lld ", a[i*3]+a[i*3+1]+a[i*3+2]);
		printf("%lld ", a[i*3+c]);
	}
}

long long dp[20][100][3] = { 0 };
long long f(char *s) {
	int length = strlen(s);
	if (length <= 1) return s[0]-'0'+1;

	for (int i=0;i<100;i++) {
		dp[1][i][0] = dp[1][i][1] = dp[1][i][2] = 0;
	}

	for (int i=10;i<(s[0]-'0')*10+(s[1]-'0');i++) {
		if (i/10 != i%10) dp[1][i][1] = 1;
	}
	for (int i=0;i<10&&i<(s[0]-'0')*10+(s[1]-'0');i++) {
		dp[1][i][2] = 1;
	}

	if (s[0] != s[1]) dp[1][(s[0]-'0')*10+(s[1]-'0')][0] = 1;

	for (int i=2;i<length;i++) {
		for (int j=0;j<10;j++) {
			for (int k=0;k<10;k++) {
				long long res1 = 0;
				long long res2 = 0;
				long long res3 = 0;
				for (int l=0;l<10;l++) {
					if ((l == k || j == k) && k) continue;
					if (j == 0) res3 += dp[i-1][l*10+j][2];
					else res1 += dp[i-1][l*10+j][2];
					if (l == k || j == k) continue;
					if (k+'0' < s[i]) res1 += dp[i-1][l*10+j][0];
					else if (k+'0' == s[i]) res2 += dp[i-1][l*10+j][0];
					res1 += dp[i-1][l*10+j][1];
				}
				dp[i][j*10+k][1] = res1;
				dp[i][j*10+k][0] = res2;
				dp[i][j*10+k][2] = res3;
			}
		}
	}

	//printmat((long long*)dp[1], 0);
	//printmat((long long*)dp[1], 1);
	//printmat((long long*)dp[2], 0);
	//printmat((long long*)dp[2], 0);

	long long ans = 0;
	for (int i=0;i<100;i++) {
		ans += dp[length-1][i][0] + dp[length-1][i][1] + dp[length-1][i][2];
	}
	
	return ans;
}

//#define TEST

int main()
{
#ifdef TEST
	scanf("%s", a);
	printf("%lld\n", f(a));
#else
	
	scanf("%s %s", a, b);

	long long x = f(b)-f(a);
	int free = 1;
	for (int i=1;i<strlen(a);i++) {
		if (i >= 2 && a[i] == a[i-2]) free = 0;
		if (i >= 1 && a[i] == a[i-1]) free = 0;
	}
	x += free;
	printf("\n%lld\n", x);	
#endif
}

Compilation message (stderr)

numbers.cpp: In function 'int main()':
numbers.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf("%s %s", a, b);
      |         ~~~~~^~~~~~~~~~~~~~~

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