답안 #117129

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
117129 2019-06-14T23:46:47 Z MB81 Palindrome-Free Numbers (BOI13_numbers) C++11
100 / 100
4 ms 412 KB
#include <bits/stdc++.h>

using namespace std;
typedef long long int64;
typedef pair<int,int> pii;
typedef pair<int64,int> pii32;
typedef pair<int64,int64> pii64;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int maxn = 1e5+10;
const int64 MO = 1e9+7;
const int64 IN = 1e9;

int64 dp[20][11][11];
int a[20];
int64 n, m;

int getl (int64 x) {
	int res = 0;
	while (x) {
		res++;
		x /= 10;
	}
	return res;
}

bool ok (int64 x) {
	int len = getl(x);
	for (int i = 0; i < len; i++) {
		a[i] = x % 10;
		x /= 10;
	}
	for (int i = 0; i < len - 1; i++)
		if (a[i] == a[i + 1])
			return 0;
	for (int i = 0; i < len - 2; i++)
		if (a[i] == a[i + 2])
			return 0;
	return 1;
}

int64 solve (int64 x) {
	if (x == -1)
		return 0;
	if (x == 0)
		return 1;
	int len = getl(x);
	memset(dp, 0, sizeof dp);
	for (int i = 1; i < 10; i++)
		dp[0][10][i] = 1;
	int64 ans = ((len > 1) ? 9 : 0);
	for (int i = 1; i < len - 1; i++) {
		for (int t = 0; t <= 10; t++)
			for (int j = 0; j <= 9; j++)
				for (int k = 0; k <= 10; k++) {
					if (j == t || j == k)
						continue;
					dp[i][t][j] += dp[i - 1][k][t];	
				}
		for (int t = 0; t <= 10; t++)
			for (int j = 0; j <= 10; j++)
				ans += dp[i][t][j];
	}
	int64 tmp = x;
	for (int l = len - 1; l >= 0; l--) {
		a[l] = tmp % 10;
		tmp /= 10;
	}
	for (int l = 0; l < len; l++) {
		memset(dp, 0, sizeof dp); 
		if (l == 0)
			for (int i = 1; i < a[0]; i++)
				dp[0][10][i] = 1;
		else
			dp[0][10][a[0]] = 1;
		for (int i = 1; i < len; i++) 
			for (int t = 0; t <= 10; t++)
				for (int j = 0; j <= 9; j++)
					for (int k = 0; k <= 10; k++) {
						if (j == t || j == k)
							continue;
						if ((i == l && j >= a[i]) || (i < l && j != a[i]))
							continue;
						dp[i][t][j] += dp[i - 1][k][t];
					}
		for (int i = 0; i <= 10; i++)
			for (int t = 0; t <= 10; t++)
				ans += dp[len - 1][i][t];
	}
	if (ok(x))
		ans++;
	return ans + 1;
}

int main () {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	cout << solve(m) - solve(n - 1) << "\n";
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 396 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 392 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 3 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 3 ms 384 KB Output is correct
31 Correct 3 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 3 ms 384 KB Output is correct
34 Correct 3 ms 384 KB Output is correct
35 Correct 3 ms 384 KB Output is correct
36 Correct 3 ms 384 KB Output is correct
37 Correct 3 ms 384 KB Output is correct
38 Correct 3 ms 384 KB Output is correct
39 Correct 3 ms 384 KB Output is correct
40 Correct 3 ms 384 KB Output is correct
41 Correct 3 ms 412 KB Output is correct
42 Correct 4 ms 384 KB Output is correct
43 Correct 3 ms 384 KB Output is correct
44 Correct 4 ms 384 KB Output is correct
45 Correct 3 ms 384 KB Output is correct