Submission #99524

#	Time	Username	Problem	Language	Result	Execution time	Memory
99524		MohamedAhmed0	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	5 ms	512 KiB

numbers

#include <bits/stdc++.h>

using namespace std;

long long dp[19][2][2][11][11] ;
vector<int>v ;

long long cnt(int idx , bool f , bool f2 , int prv , int prv2)
{
    if(idx == v.size())
        return 1 ;
    long long &ret = dp[idx][f][f2][prv][prv2] ;
    if(ret != -1)
        return ret ;
    int LMT ;
    if(f)
        LMT = 9 ;
    else
        LMT = v[idx] ;
    ret = 0ll ;
    for(int i = 0 ; i <= LMT ; ++i)
    {
        int nf = f ;
        int nf2 = f2 ;
        if(i < LMT)
            nf = 1 ;
        if(i == prv || i == prv2)
            continue;
        if(i != 0)
            nf2 = 1 ;
        if(nf2 == 0)
            ret += cnt(idx+1 , nf , nf2 , 10 , 10) ;
        else
            ret += cnt(idx+1 , nf , nf2 , i , prv) ;
    }
    return ret ;
}
long long solve(long long x)
{
    if(x < 0)
        return 0 ;
    v.clear();
    memset(dp , -1 , sizeof(dp)) ;
    while(x > 0)
    {
        v.push_back(x % 10) ;
        x /= 10 ;
    }
    reverse(v.begin() , v.end()) ;
    long long ans = cnt(0 , 0 , 0 , 10 , 10) ;
    return ans ;
}

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

Compilation message (stderr)

numbers.cpp: In function 'long long int cnt(int, bool, bool, int, int)':
numbers.cpp:10:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(idx == v.size())
        ~~~~^~~~~~~~~~~

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