Submission #26385

#	Time	Username	Problem	Language	Result	Execution time	Memory
26385		samir_droubi	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	3 ms	2040 KiB

numbers

#include <bits/stdc++.h>
using namespace std;
long long a,b;
long long dp[20][12][12];
long long calc(int i,int lst1,int lst2)
{
	if(i==2)return lst1!=lst2;
	if(dp[i][lst1][lst2]!=-1)return dp[i][lst1][lst2];
	long long ans=0;
	for(int j=0;j<=9;++j)
	{
		if(j!=lst1&&j!=lst2)
			ans=ans+calc(i-1,j,lst1);
	}
	return dp[i][lst1][lst2]=ans;
}
long long sm[20];
vector<int>v;
long long f(long long x)
{
	v.clear();
	int y=x;
	while(x!=0)
	{
		v.push_back(x%10);
		x/=10;
	}
	if(v.size()==1)
		return y-1;
	if(v.size()==2)
		return y-1-(v[1]-1)-(v[0]-1>=v[1]);

	long long ans=0;
	for(int i=0;i<v.size();++i)
	{
		int lst1=10;
		int lst2=10;
		if(i<v.size()-1)lst1=v[i+1];
		if(i<v.size()-2)lst2=v[i+2];
		if(i<v.size()-1&&v[i]==v[i+1])ans=0;
		if(i<v.size()-2&&v[i]==v[i+2])ans=0;
		for(int j=(i==v.size()-1);j<v[i];++j)
		{
			if(j==lst2||j==lst1)continue;
			ans=ans+calc(i+2,j,lst1);
		}		
	}
	return ans+sm[v.size()-1];
}
bool check(long long x)
{
	int a=-1;
	int b=-1;
	while(x)
	{
		int y=x%10;
		if(y==a||y==b)return false;
		b=a;
		a=y;
		x/=10;
	}
	return true;
}
int main()
{
	memset(dp,-1,sizeof dp);
	scanf("%lld%lld",&a,&b);
	sm[1]=9;
	for(int i=2;i<=18;++i)
	{
		for(int j=1;j<=9;++j)
			for(int k=0;k<=9;++k)
			{
				if(j==k)continue;
				sm[i]+=calc(i,k,j);
			}
		sm[i]+=sm[i-1];
	}
	if(b-a<=(1e5))
	{
		long long ans=0;
		for(long long i=a;i<=b;++i)
			ans+=check(i);
		printf("%lld\n",ans);
		return 0;
	}
	long long sa=f(a);
	long long sb=f(b);
	printf("%lld\n",sb-sa+check(b));
	return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'long long int f(long long int)':
numbers.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();++i)
               ^
numbers.cpp:38:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i<v.size()-1)lst1=v[i+1];
       ^
numbers.cpp:39:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i<v.size()-2)lst2=v[i+2];
       ^
numbers.cpp:40:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i<v.size()-1&&v[i]==v[i+1])ans=0;
       ^
numbers.cpp:41:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i<v.size()-2&&v[i]==v[i+2])ans=0;
       ^
numbers.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=(i==v.size()-1);j<v[i];++j)
               ^
numbers.cpp: In function 'int main()':
numbers.cpp:67:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&a,&b);
                         ^

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