Submission #1318168

#TimeUsernameProblemLanguageResultExecution timeMemory
1318168SamakahhhPalindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
1 ms332 KiB
#include <bits/stdc++.h>
using namespace std;


typedef long long ll;


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 < s.size(); d++)
    {
        ll a = 81;
        for (int i = 0; i < d - 2; i++)
        {
            a *= 8;
        }
        res += a;
    }


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


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

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

    for (int i = 2; i < s.size(); 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 < s.size(); j++)
                {
                    a *= 8;
                }
                res += a;
            }

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

    return res;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

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

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...