Submission #199449

#	Time	Username	Problem	Language	Result	Execution time	Memory
199449		TadijaSebez	Palindrome-Free Numbers (BOI13_numbers)	C++11	100 / 100	9 ms	504 KiB

numbers

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
ll dp[10][10][2],tmp[10][20][2];
void Clear(){
	for(int j=0;j<10;j++)
		for(int k=0;k<10;k++)
			for(int l=0;l<2;l++)
				dp[j][k][l]=0;
}
void Copy(){
	for(int j=0;j<10;j++)
		for(int k=0;k<10;k++)
			for(int l=0;l<2;l++)
				tmp[j][k][l]=dp[j][k][l];
}
ll Solve(ll x){
	//printf("%lld\n",x);
	if(x==0)return 1;
	ll y=x;
	vector<int> cif;
	while(x)cif.pb(x%10),x/=10;
	reverse(cif.begin(),cif.end());
	ll mul=1;for(int i=1;i<cif.size();i++)mul*=10;
	ll ans=Solve(mul-1);
	if(cif.size()==1)return y+ans;
	Clear();
	for(int i=1;i<=9;i++)for(int j=0;j<=9;j++)if(i!=j){
		if(i==cif[0] && j==cif[1])dp[i][j][1]=1;
		else if(i<cif[0] || i==cif[0] && j<cif[1])dp[i][j][0]=1;
	}
	for(int len=2;len<cif.size();len++){
		Copy();
		Clear();
		for(int i=0;i<=9;i++)for(int j=0;j<=9;j++){
			for(int k=0;k<=9;k++)if(j!=i && j!=k){
				dp[i][j][0]+=tmp[k][i][0];
				if(j<cif[len])dp[i][j][0]+=tmp[k][i][1];
			}
		}
		if(cif[len]!=cif[len-1] && cif[len]!=cif[len-2])dp[cif[len-1]][cif[len]][1]=tmp[cif[len-2]][cif[len-1]][1];
	}
	for(int i=0;i<=9;i++)for(int j=0;j<=9;j++)ans+=dp[i][j][0]+dp[i][j][1];
	//printf("%lld %lld\n",y,ans);
	return ans;
}
int main(){
	ll l,r;
	scanf("%lld %lld",&l,&r);
	printf("%lld\n",Solve(r)-(l>0?Solve(l-1):0));
	return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'long long int Solve(long long int)':
numbers.cpp:25:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  ll mul=1;for(int i=1;i<cif.size();i++)mul*=10;
                       ~^~~~~~~~~~~
numbers.cpp:31:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   else if(i<cif[0] || i==cif[0] && j<cif[1])dp[i][j][0]=1;
numbers.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int len=2;len<cif.size();len++){
                ~~~^~~~~~~~~~~
numbers.cpp: In function 'int main()':
numbers.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&l,&r);
  ~~~~~^~~~~~~~~~~~~~~~~~~

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