Submission #170599

#	Time	Username	Problem	Language	Result	Execution time	Memory
170599		manh9203	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	14 ms	544 KiB

numbers

#include<bits/stdc++.h>
using namespace std;
long long t,l,r,dp[20][20][20][2];
string s;
long long solve(string s){
	if(s == "-1") return 0;
	int n = s.length(); 
	s = " " + s;
	memset(dp, 0, sizeof dp);
	dp[0][0][0][1] = 1;
	for(int i=1;i<=n;i++){
		int hah = (i == 1 ? 2 : 1);
		for(int cs = hah; cs <= 10; cs++){
			if(cs == s[i] - 47){
				for(int las = 0; las <= 10; las++){
					for(int pre = 0; pre <= 10; pre++){
						if(pre != cs && las != cs){
							dp[i][las][cs][1] += dp[i-1][pre][las][1];
						}
					}
				}
			}
			if(cs < s[i] - 47){
				for(int las = 0; las <= 10; las++){
					for(int pre = 0; pre <= 10; pre++){
						if(pre != cs && las != cs){
							dp[i][las][cs][0] += dp[i-1][pre][las][1];
						}
					}
				}
			}
			for(int las = 0; las <= 10; las++){
				for(int pre = 0; pre <= 10; pre++){
					if(pre != cs && las != cs){
						dp[i][las][cs][0] += dp[i-1][pre][las][0];
					}
				}
			}
			if(i > 1 && cs > 1){
				dp[i][0][cs][0]++;
			}
		}
	}
	long long ans = 1;
	for(int cs = 0; cs <= 10; cs++){
		for(int las = 0; las <= 10; las++){
			ans += dp[n][las][cs][1] + dp[n][las][cs][0];
		}
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> l >> r;
	l--; s = to_string(l);
	long long ans1 = solve(s);
	s = to_string(r);
	long long ans2 = solve(s);
	cout << ans2 - ans1;
}

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