제출 #1124305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124305		stefanneagu	Palindrome-Free Numbers (BOI13_numbers)	C++20	26.67 / 100	1 ms	452 KiB

numbers

#include <bits/stdc++.h>
#define int long long

using namespace std;

int mai_mare(string s) {
    if(s.size() == 1) {
      int a = stoll(s);
      return 10 - a;
    }
	s = "$" + s;
	int dp[s.size() + 1][s.size() + 1][10][10];
	memset(dp, 0, sizeof(dp));
	if(s[1] != s[2]) {
      dp[2][2][s[1] - '0'][s[2] - '0']++;
	}
	for(int j = s[2] - '0' + 1; j <= 9; j++) {
		if(s[1] - '0' != j) {
			dp[2][1][s[1] - '0'][j]++;
		}
	}
	for(int i = s[1] - '0' + 1; i <= 9; i++) {
		for(int j = 0; j <= 9; j++) {
			if(i != j) {
				dp[2][0][i][j]++;
			}
		}
	}
	for(int i = 2; i <= (int) s.size() - 2; i++) {
		// nu continua
		for(int j = 0; j < i; j++) {
			for(int nr1 = 0; nr1 < 10; nr1++) {
				for(int nr2 = 0; nr2 < 10; nr2++) {
					if(nr1 == nr2 || dp[i][j][nr1][nr2] ==  0) {
						continue;
					}
					for(int nr3 = 0; nr3 < 10; nr3++) {
						if(nr3 == nr1 || nr3 == nr2) {
							continue;
						}
						dp[i + 1][j][nr2][nr3] += dp[i][j][nr1][nr2];
					}
				}
			}
		}
		// continua
		if(s[i] == s[i - 1]) {
			continue;
		}
		for(int nr = s[i + 1] - '0' + 1; nr < 10; nr++) {
			if(nr == s[i] - '0' || nr == s[i - 1] - '0') {
				continue;
			}
			dp[i + 1][i][s[i] - '0'][nr]++;
		}
		if(s[i + 1] != s[i] && s[i + 1] != s[i - 1]) {
			dp[i + 1][i + 1][s[i] - '0'][s[i + 1] - '0']++;
		} 
	}
	int ans = 0;
	for(int i = 0; i < 10; i++) {
		for(int j = 0; j < 10; j++) {
			for(int lot = 0; lot < (int) s.size(); lot++) {
				ans += dp[s.size() - 1][lot][i][j];
			}
		}
    }
	return ans;
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	string a, b;
	cin >> a >> b;
    assert(stoll(b) < (int) 1e9);
	int bb = stoll(b) + 1;
    int ans = mai_mare(a) - mai_mare(to_string(bb));
    string s = "1";
    while(s.size() < a.size()) {
      s += "0";
    }
    for(int i = a.size() + 1; i <= (int) b.size(); i++) {
      s += "0";
      ans += mai_mare(s);
    }
    s += "0";
    if(stoll(s) == bb) {
      ans += mai_mare(to_string(bb));
    }
    cout << ans;
	return 0;
}

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