Submission #40809

#	Time	Username	Problem	Language	Result	Execution time	Memory
40809		someone_aa	Palindrome-Free Numbers (BOI13_numbers)	C++14	96.25 / 100	2 ms	1008 KiB

numbers

#include <bits/stdc++.h>
#define ll long long
using namespace std;
string x;
ll dp[10][10][20][2];
ll a, b;

ll recursion(int first, int second, int position, bool f) {
    if(position >= x.length()) {
        return 1;
    }
    else {
        if(dp[first][second][position][f] == -1) {
            ll sum = 0;
            if(f) {
                for(int i=0;i<=9;i++) {
                    if(i!=first && i!=second)
                        sum += recursion(second, i, position+1, f);
                }
            }
            else {
                int temp = x[position] - '0';
                for(int i=0;i<temp;i++) {
                    if(i!=first && i!=second) {
                        sum += recursion(second,i,position+1, true);
                    }
                }

                if(temp!=first && temp!=second) {
                    sum += recursion(second,temp,position+1,false);
                }
            }
            dp[first][second][position][f] = sum;
        }
        return dp[first][second][position][f];
    }
}

ll solve(ll y) {
    stringstream ss; ss << y; x = ss.str();

    memset(dp,-1,sizeof(dp));
    ll result = 1;
    int temp = x[0]-'0';

    for(int i=1;i<=temp;i++) {
        result += recursion(i,i,1,i!=temp);
    }

    for(int i=2;i<=x.length();i++) {
        for(int j=1;j<10;j++) {
            result += recursion(j,j, i, true);
        }
    }
    return result;
}

int main() {
    cin>>a>>b;
    cout<<solve(b)-solve(a-1)<<"\n";
    return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'long long int recursion(int, int, int, bool)':
numbers.cpp:9:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(position >= x.length()) {
                 ^
numbers.cpp: In function 'long long int solve(long long int)':
numbers.cpp:50:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=2;i<=x.length();i++) {
                  ^

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