Submission #361822

#	Time	Username	Problem	Language	Result	Execution time	Memory
361822		usuyus	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	5 ms	364 KiB

numbers

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll solve(ll x) {
	int a[20], n = 0;
	while (x) a[n++] = x % 10, x /= 10;

	ll ans = 0;
	for (int i=1; i<n; i++) {
		if (i == 1) ans += 10;
		else {
			ll cur = 9 * 9;
			for (int j=0; j<i-2; j++) cur *= 8;
			ans += cur;
		}
	}

	bool self = true;

	for (int i=n-1; i>=0; i--) {
		if (i < n-2 && a[i+1] == a[i+2]) {self = false; break;}
		if (i < n-3 && a[i+1] == a[i+3]) {self = false; break;}

		for (int j=0; j<a[i]; j++) {
			if (i == n-1) {
				if (j == 0) continue;

				ll cur = 9;
				for (int k=0; k<i-1; k++) cur *= 8;
				ans += cur;
			} else if (i == n-2) {
				if (j == a[i+1]) continue;

				ll cur = 1;
				for (int k=0; k<i; k++) cur *= 8;
				ans += cur;
			} else {
				if (j == a[i+1] || j == a[i+2] || a[i+1] == a[i+2]) continue;

				ll cur = 1;
				for (int k=0; k<i; k++) cur *= 8;
				ans += cur;
			}
		}
	}

	if (self && n >= 2) self = a[0] != a[1];
	if (self && n >= 3) self = a[0] != a[2];

	return ans + self;
}

bool check(ll x) {
	int a[20], n = 0;
	while (x) a[n++] = x % 10, x /= 10;

	for (int i=0; i<n; i++) {
		if (i>0 && a[i] == a[i-1]) return false;
		if (i>1 && a[i] == a[i-2]) return false;
	}

	return true;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	ll a, b; cin>>a>>b;
	
	if (b-a <= 1000000) {
		ll ans = 0;
		for (ll i=a; i<=b; i++) ans += check(i);
		cout<<ans<<endl;
	} else cout<<solve(b) - solve(a-1)<<endl;
}

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