제출 #1244509

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

numbers

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define int long long
using namespace std;


ll mypow(ll a, ll b) {
    ll val = 1;
    for (int i=0;i<b;i++) {
        val *= a;
    }
    return val;
}


ll numofdigits(ll a) {
    ll val = 0;
    while (a != 0) {
        val += 1;
        a /= 10;
    }
    return val;
}


ll pfnum(ll a) {
    if (a == 0) return 1;
    if (a == -1) return 0;
    ll digitnum = numofdigits(a), ans = 0, base = 1, digit, dummy;
    if (digitnum == 1) {
        return a + 1;
    }
    ans += 10;
    for (int i=2;i<digitnum;i++) {
        ans += (mypow(8, i) / 64) * 9 * 9;
    }
    //cout << ans << '\n';
    ll bruh = a / mypow(10, digitnum - 2);
    for (int i=10;i<bruh;i++) {
        if (i / 10 == i % 10) continue;
        ans += mypow(8, digitnum - 2);
    }
    //cout << ans << '\n';
    ll prev1 = bruh % 10, prev2 = bruh / 10;
    if (prev1 == prev2) return ans;
    for (int i=digitnum - 2;i>0;i--) {
        digit = (a / mypow(10, i - 1)) % 10;
        for (int j=0;j<digit;j++) {
            if (j == prev1 || j == prev2) continue;
            ans += mypow(8, i - 1);
        }
        if (digit == prev1 || digit == prev2) {
            ans -= 1;
            break;
        }
        prev2 = prev1;
        prev1 = digit;
    }
    ans += 1;
    if (digitnum == 2 && bruh % 10 == bruh / 10) ans -= 1;
    return ans;
}


int32_t main() {
    ll a, b; cin >> a >> b;
    cout << pfnum(b) - pfnum(a - 1);
}

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