Submission #1146721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146721		Matjaz	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	1 ms	328 KiB

numbers

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;



vector<int> digits(long long x){
	vector<int> d;
	if (x == 0){
		d.push_back(0);
		return d;
	}

	while (x > 0){
		d.push_back(x % 10);
		x /= 10;
	}
	reverse(d.begin(), d.end());
	return d;

}

long long nines(long long l){
	long long x = 0;
	for (int i=0;i<l;i++) x = x * 10 + 9;
	return x;
}


long long fast_count(int prev, long long l){
	long long res = 1;
	for (int i=0;i<l;i++) res *= 8;
	if (prev == 1) res = res / 8 * 9;
    return res;
}



long long palindrome_free(long long x){

	if (x < 10) return x + 1;

	vector<int> d = digits(x);

	long long count = 0;

	for (int i=0;i<d.size();i++){
        if (i == 0){
        	for (int j=1;j<d[i];j++) count += fast_count(1, (long long)d.size() - 1);
        	continue;
        }
        if (i == 1){
        	for (int j=0;j<d[i];j++){
        		if (j == d[i-1]) continue;
        		count += fast_count(2, (long long) d.size() - 2);
        	}
        	if (d[1] == d[0]) break;
        	if (i + 1 == d.size()) count += 1;
        	continue;
        }
        for (int j=0;j<d[i];j++){
        	if (j == d[i-1] || j == d[i -2]) continue;
        	count += fast_count(2, (long long) d.size() - (i + 1));

        }

        if (d[i] == d[i-1] || d[i] == d[i -2]) break;
        if (i + 1 == d.size()) count += 1; 
	}


	return count + palindrome_free(nines(d.size() - 1));
}

int main(){
	long long a,b;
	cin >> a >> b;

	if (a == 0) cout << palindrome_free(b) << endl; else cout << palindrome_free(b) - palindrome_free(a - 1) << endl;

	return 0;
}

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