제출 #1314730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1314730		fv3	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	0 ms	332 KiB

numbers

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
const ll inf = LONG_LONG_MAX / 2;

ll solve(ll x) {
	if (x == 0) {
		return 0;
	}

	if (x < 100) {
		ll res = 1;
		for (int i = 1; i < x; i++) if (i / 10 != i % 10) {
			res++;
		}
		return res;
	}

	ll res = 91;
	string s = to_string(x);

	for (int d = 3; d < sz(s); d++) {
		ll a = 81;
		for (int i = 0; i < d - 2; i++) {
			a *= 8;
		}
		res += a;
	}


	ll m = 9;
	for (int i = 2; i < sz(s); i++) {
		m *= 8;
	}
	res += m * (s[0] - '0' - 1);

	for (char d = '0'; d < s[1]; d++) if (d != s[0]) {
		ll a = 1;
		for (int i = 2; i < sz(s); i++) {
			a *= 8;
		}
		res += a;
	}

	if (s[0] == s[1]) return res;

	for (int i = 2; i < sz(s); i++) {
		for (char d = '0'; d < s[i]; d++) if (d != s[i - 1] && d != s[i - 2]) {
			ll a = 1;
			for (int j = i + 1; j < sz(s); j++) {
				a *= 8;
			}
			res += a;
		}

		if (s[i] == s[i - 1] || s[i] == s[i - 2]) return res;
	}
	
	return res;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	ll a, b;
	cin >> a >> b;
	cout << solve(b + 1) - solve(a) << "\n";

	return 0;
}

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