제출 #49168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49168		aome	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	3 ms	1028 KiB

numbers

#include <bits/stdc++.h>

using namespace std;

int A[20], B[20];
long long f[20][11][11][2][2][2];

long long calc(int p, int prv1, int prv2, bool oka, bool okb, bool nonzero) {
	long long &ret = f[p][prv1][prv2][oka][okb][nonzero];
	if (ret != -1) return ret;
	if (p == 18) return 1;
	ret = 0;
	int l, r;
	l = 0, r = 9;
	if (!oka) l = A[p];
	if (!okb) r = B[p];
	for (int i = l; i <= r; ++i) {
		if (i == prv1 || i == prv2) continue;
		if (!i && !nonzero) {
			ret += calc(p + 1, 10, 10, oka | (i > l), okb | (i < r), 0);
		} 
		else {
			ret += calc(p + 1, i, prv1, oka | (i > l), okb | (i < r), 1);
		} 
	} 
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	long long a, b; cin >> a >> b;
	for (int i = 0; i < 18; ++i) A[17 - i] = a % 10, a /= 10;
	for (int i = 0; i < 18; ++i) B[17 - i] = b % 10, b /= 10;
	memset(f, -1, sizeof f);
	cout << calc(0, 10, 10, 0, 0, 0);
}

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