Submission #701064

#TimeUsernameProblemLanguageResultExecution timeMemory
701064hgmhcPalindrome-Free Numbers (BOI13_numbers)C++17
100 / 100
1 ms304 KiB
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

ll pw(ll x, ll e) {
    ll r = 1;
    while (e > 0) {
        if (e%2) r *= x;
        e /= 2, x *= x;
    }
    return r;
}

ll calc(vector<int> &v, int n, int k = 0) {
    if (v[k] == v[k+1]) return 0;
    if (n == 2) return 1;
    ll r = 0;
    rep(i,0,v[k+2]-1) if (i != v[k] and i != v[k+1]) {
        r += pw(8,n-3);
    }
    if (v[k] != v[k+2]) r += calc(v,n-1,k+1);
    return r;
}

ll f(ll x) {
    if (x <= 9) return x+1;
    ll c = 10;
    vector<int> v; //digits
    for (int i = 0; i < siz(to_string(x)); ++i) {
        v.push_back(to_string(x)[i]-'0');
    }
    rep(i,1,v[0]-1) rep(j,0,9) if (j != i)
        c += pw(8,siz(v)-2); //first case - (1)
    rep(j,0,v[1]-1) if (j != v[0])
        c += pw(8,siz(v)-2); //first case - (2)
    rep(i,1,siz(v)-2) c += pw(8,siz(v)-2-i)*9*9; //suffix is $...
    return c+calc(v,siz(v)); //calc upper cases
}

int main() {
    ll a, b;
    scanf("%lld %lld", &a, &b);
    printf("%lld", f(b)-f(a-1));
}

Compilation message (stderr)

numbers.cpp: In function 'int main()':
numbers.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%lld %lld", &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...