제출 #1257117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257117		terracottalite	Palindrome-Free Numbers (BOI13_numbers)	C++20	73.75 / 100	0 ms	468 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*2+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] = 0;
	}

	for (int i=1;i<(s[0]-'0')*10+(s[1]-'0');i++) {
		if (i/10 != i%10 || !(i%10)) dp[1][i][1] = 1;
	}
	for (int i=0;i<1&&i<(s[0]-'0')*10+(s[1]-'0');i++) {
		if (i/10 != i%10 || !(i%10)) 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;
					else if (l==0&&j==0) {
						if (k == 0) res3 += dp[i-1][l*10+j][2];
						else res1 += dp[i-1][l*10+j][2];
						continue;
					} else if (!k && (l == k || j == k)) continue;
					if (k+'0' < s[i]) res1 += dp[i-1][l*10+j][0];
					res1 += dp[i-1][l*10+j][1];
					if (k+'0' == s[i]) res2 += dp[i-1][l*10+j][0];
				}
				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], 1);

	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;
}

int main()
{
	//scanf("%s", a);
	//printf("%lld\n", f(a));
	
	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);	
}

컴파일 시 표준 에러 (stderr) 메시지

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

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