Submission #1124274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124274		stefanneagu	Palindrome-Free Numbers (BOI13_numbers)	C++20	15.42 / 100	2 ms	332 KiB

numbers

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

using namespace std;

int mai_mare(string s) {
	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(a.size() == b.size());
	if(stoll(a) < 10 && stoll(b) < 10) {
		cout << stoll(b) - stoll(a) + 1;
		return 0;
	}
	int bb = stoi(b) + 1;
    if(a.size() == b.size()) {
	  cout << mai_mare(a) - mai_mare(to_string(bb)); 
    } else {
      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);
      }
      cout << ans;
    }
	return 0;
}

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