Submission #102368

#	Time	Username	Problem	Language	Result	Execution time	Memory
102368		MoNsTeR_CuBe	Palindrome-Free Numbers (BOI13_numbers)	C++17	73.75 / 100	4 ms	556 KiB

numbers

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

#define int long long

bool check(string a){
    for(int i = 0; i < (int)a.size()-1; i++){
        if(a[i] == a[i+1]) return true;
    }
    for(int i = 0; i < (int)a.size()-2; i++){
        if(a[i] == a[i+2]) return false;
    }
    return true;
}

string toString(int a){
    if(a == 0) return "0";
    string s = "";
    while(a){
        s = ((char)(a%10+'0'))+s;
        a/=10;
    }
    return s;
}

vector<int> v;

string a;
string b;

int memo[2][2][19][11][2][11];

int dp(bool isPal, bool canTakeAnything, int n, int last, bool isMini, int lastlast){
   // cout << isPal << ' ' << canTakeAnything << ' ' << n << ' ' << last << ' ' << isMini << endl;
    if(n == a.size()){
        if(isPal) return 1;
        else return 0;
    }
    //cout << memo[isPal][canTakeAnything][n][last][isMini] << endl;
    if(memo[isPal][canTakeAnything][n][last][isMini][lastlast] != -1) return memo[isPal][canTakeAnything][n][last][isMini][lastlast];
    memo[isPal][canTakeAnything][n][last][isMini][lastlast] = 0;
    if(canTakeAnything){
        int c = a[n]-'0'+1;
        for(int i = (isMini ? c : 1); i <= 10; i++){
            bool cond = false;
            if(isMini && i == c){
                cond = true;
            }
            if(i == last || i == lastlast){
                memo[isPal][canTakeAnything][n][last][isMini][lastlast] += dp(1,canTakeAnything,n+1,i,cond,last);
            }else{
                memo[isPal][canTakeAnything][n][last][isMini][lastlast] += dp(isPal, canTakeAnything, n+1, i,cond,last);
            }
        }
    }else{
        int c = a[n]-'0'+1;
        int d = b[n]-'0'+1;
        for(int i = (isMini ? c : 1); i<= d; i++){
            bool cond = false;
            if(isMini && i == c){
                cond = true;
            }
            if(i == last || i== lastlast){
                memo[isPal][canTakeAnything][n][last][isMini][lastlast] += dp(1, i < d, n+1,i,cond,last);
            }else{
                memo[isPal][canTakeAnything][n][last][isMini][lastlast] += dp(isPal, i < d, n+1,i, cond,last);
            }
        }
    }
    return memo[isPal][canTakeAnything][n][last][isMini][lastlast];
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int c, d;
    cin >> c >> d;
    string s = "";
    a = toString(c);
    b = toString(d);
    for(int i = 0; i < (int)(b.size()-a.size()); i++){
        s += '0';
    }
    a = s + a;
    int tot = (d-c+1);
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            for(int k = 0; k < 19; k++){
                for(int l = 0; l <= 10; l++){
                    for(int m = 0; m < 2; m++){
                        for(int n = 0; n <= 10; n++){
                            memo[i][j][k][l][m][n] = -1;
                        }
                    }
                }
            }
        }
    }
    tot-=dp(0,0,0,0,1,0);
    cout << tot << endl;
}

Compilation message (stderr)

numbers.cpp: In function 'long long int dp(bool, bool, long long int, long long int, bool, long long int)':
numbers.cpp:35:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(n == a.size()){
        ~~^~~~~~~~~~~

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