Submission #518313

#	Time	Username	Problem	Language	Result	Execution time	Memory
518313		Sirapetch	Palindrome-Free Numbers (BOI13_numbers)	C++14	16.25 / 100	1087 ms	1112 KiB

numbers

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

long long int N,M,dp[10][10][100][10];
vector <long long int> s;

long long int cnt(long long int p1,long long int p2,long long int pos,long long int ma)
{
    long long int sum=0,i;
    if(pos>=s.size()) return 1;
    if(dp[p1][p2][pos][ma]!=-1) return dp[p1][p2][pos][ma];
    if(ma==0)
    {
        for(i=0;i<=9;i++)
        {
            if(i==p1||i==p2) continue;
            sum+=cnt(i,p1,pos+1,0);
        }
    }
    else
    {
        for(i=0;i<s[pos];i++)
        {
            if(i==p1||i==p2) continue;
            sum+=cnt(i,p1,pos+1,0);
        }
        if(s[pos]==p1||s[pos]==p2){}
        else sum+=cnt(s[pos],p1,pos+1,1);
    }
    dp[p1][p2][pos][ma]=sum;
    return sum;
}

long long int cp(long long int n)
{
    if(n<0) return 0;
    if(n==0) return 1;
    s.clear();
    memset(dp,-1,sizeof(dp));
    long long int i,j,x,sum=1;
    x=n;
    while(x!=0)
    {
        s.push_back(x%10);
        x/=10;
    }
    reverse(s.begin(),s.end());
    for(i=1;i<s[0];i++)
    {
        sum+=cnt(i,i,1,0);
    }
    sum+=cnt(s[0],s[0],1,1);
    for(j=2;i<=s.size();j++)
    {
        for(i=1;i<=9;i++)
        {
            sum+=cnt(i,i,j,0);
        }
    }
    return sum;
}

int main()
{
    scanf("%lld %lld",&N,&M);
    printf("%lld",cp(M)-cp(N-1));
    return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'long long int cnt(long long int, long long int, long long int, long long int)':
numbers.cpp:10:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     if(pos>=s.size()) return 1;
      |        ~~~^~~~~~~~~~
numbers.cpp: In function 'long long int cp(long long int)':
numbers.cpp:53:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(j=2;i<=s.size();j++)
      |             ~^~~~~~~~~~
numbers.cpp: In function 'int main()':
numbers.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%lld %lld",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

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