Submission #362365

#	Time	Username	Problem	Language	Result	Execution time	Memory
362365		shahriarkhan	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	1 ms	372 KiB

numbers

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

const int unvisited = -1 ;

long long dp[20][11][11][2] ;

long long calc(string &s , int siz , int pos , int prev1 , int prev2 , int smaller)
{
    if(pos>=siz) return 1 ;
    if(dp[pos][prev1][prev2][smaller]!=unvisited) return dp[pos][prev1][prev2][smaller] ;

    int mx = s[pos] - '0' , cur = s[pos] - '0' ;
    if(smaller) mx = 9 ;

    long long res = 0 ;

    for(int i = 0 ; i <= mx ; ++i)
    {
        if(i==prev1 || i==prev2) continue ;
        if(cur>i) res += calc(s,siz,pos+1,prev2,i,1) ;
        else res += calc(s,siz,pos+1,prev2,i,smaller) ;
    }

    return dp[pos][prev1][prev2][smaller] = res ;
}

void clean()
{
    for(int i = 0 ; i < 20 ; ++i)
    {
        for(int j = 0 ; j < 11 ; ++j)
        {
            for(int k = 0 ; k < 11 ; ++k)
            {
                dp[i][j][k][0] = unvisited ;
                dp[i][j][k][1] = unvisited ;
            }
        }
    }
}

int main()
{
    long long A , B , zero = 0 ;
    scanf("%lld%lld",&A,&B) ;
    if(A) --A ;
    else zero = 1 ;
    string a = to_string(A) , b = to_string(B) ;
    int a_siz = a.size() , b_siz = b.size() ;
    clean() ;
    long long fst = calc(a,a_siz,0,0,10,0) ;
    for(int i = 1 ; i < a_siz ; ++i)
    {
        fst += calc(a,a_siz,i,0,10,1) ;
    }
    clean() ;
    long long sst = calc(b,b_siz,0,0,10,0) ;
    for(int i = 1 ; i < b_siz ; ++i)
    {
        sst += calc(b,b_siz,i,0,10,1) ;
    }
    printf("%lld\n",sst-fst+zero) ;
    return 0 ;
}

Compilation message (stderr)

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

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