Submission #518269

#	Time	Username	Problem	Language	Result	Execution time	Memory
518269		Ai7081	Palindrome-Free Numbers (BOI13_numbers)	C++17	25 / 100	1 ms	344 KiB

numbers

#include <bits/stdc++.h>
using namespace std;
#define long long long
const bool debug = 0;

long a, b, pow8[20], dp[20][15][15], d[20][15], sum[20][15];

long round(long x, long k) {
    x /= pow(10, k);
    return x * pow(10, k);
}

bool check(long x) {
    long p = -1, q = -1;
    while (x > 0) {
        if (x%10 == p || x%10 == q) return false;
        q = p;
        p = x%10;
        x /= 10;
    }
    return true;
}

long until(long x) {
    if (x < 10) return x+1;
    int tmp = x;
    vector<long> unit;
    while (x > 0) unit.push_back(x%10), x/=10;
    long ret = sum[unit.size()][unit[unit.size()-1] - 1];
    //cout << ret << endl;
    for (int j=0; j<unit[unit.size()-2]; j++) {
        ret += dp[unit.size()][unit[unit.size()-1]][j];
        //cout << unit.size() << ' ' << unit[unit.size()-1] << ' ' << j << ' ' << ret << endl;
    }
    for (int i=unit.size()-2; i>=1; i--) {
        if (!check(tmp / pow(10, i+1))) continue;
        for (int j=0; j<unit[i-1]; j++) {
            if (j != unit[i+1]) {
                ret += dp[i+1][unit[i]][j];
                //cout << i+1 << ' ' << unit[i] << ' ' << j << ' ' << ret << endl;
            }
        }
    }
    ret += check(tmp);
    //cout << ret << endl;
    return ret;
}

long sol(long x, long y) {
    if (!x) return until(y);
    return until(y) - until(x-1);
}

int main() {
    pow8[0] = 1;
    for (int i=1; i<=18; i++) pow8[i] = pow8[i-1] * 8;
    for (int i=0; i<=9; i++) for (int j=0; j<=9; j++) if (i!=j) dp[2][i][j] = 1;
    for (int u=3; u<=18; u++) {
        for (int i=0; i<=9; i++) {
            for (int j=0; j<=9; j++) {
                if (i!=j) {
                    for (int k=0; k<=9; k++) {
                        if (i!=k && j!=k) dp[u][i][j] += dp[u-1][j][k];
                    }
                }
            }
        }
    }
    for (int i=0; i<=9; i++) d[1][i] = 1;
    for (int u=2; u<=18; u++) {
        for (int i=0; i<=9; i++) {
            for (int j=0; j<=9; j++) {
                d[u][i] += dp[u][i][j];
            }
        }
    }
    sum[1][0] = 1;
    for (int u=1; u<=18; u++) {
        for (int i=0; i<=9; i++) {
            if (!i && u!=1) sum[u][i] = sum[u-1][9];
            else sum[u][i] = sum[u][i-1] + d[u][i];
        }
    }

    scanf(" %lld %lld", &a, &b);
    printf("%lld", sol(a, b));
}

Compilation message (stderr)

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

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