oj.uz

Submission #26385

# Submission time Handle Problem Language Result Execution time Memory
26385 2017-06-29T15:17:54 Z samir_droubi Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 3 ms 2040 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2040 KB Output is correct
2 Correct 0 ms 2040 KB Output is correct
3 Correct 3 ms 2040 KB Output is correct
4 Correct 0 ms 2040 KB Output is correct
5 Correct 0 ms 2040 KB Output is correct
6 Correct 0 ms 2040 KB Output is correct
7 Correct 0 ms 2040 KB Output is correct
8 Correct 0 ms 2040 KB Output is correct
9 Correct 0 ms 2040 KB Output is correct
10 Correct 0 ms 2040 KB Output is correct
11 Correct 0 ms 2040 KB Output is correct
12 Correct 0 ms 2040 KB Output is correct
13 Correct 0 ms 2040 KB Output is correct
14 Correct 0 ms 2040 KB Output is correct
15 Correct 0 ms 2040 KB Output is correct
16 Correct 0 ms 2040 KB Output is correct
17 Correct 0 ms 2040 KB Output is correct
18 Correct 0 ms 2040 KB Output is correct
19 Correct 3 ms 2040 KB Output is correct
20 Correct 0 ms 2040 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2040 KB Output is correct
2 Correct 0 ms 2040 KB Output is correct
3 Correct 0 ms 2040 KB Output is correct
4 Correct 0 ms 2040 KB Output is correct
5 Correct 0 ms 2040 KB Output is correct
6 Correct 0 ms 2040 KB Output is correct
7 Correct 0 ms 2040 KB Output is correct
8 Correct 0 ms 2040 KB Output is correct
9 Correct 0 ms 2040 KB Output is correct
10 Correct 0 ms 2040 KB Output is correct
11 Correct 0 ms 2040 KB Output is correct
12 Correct 0 ms 2040 KB Output is correct
13 Correct 0 ms 2040 KB Output is correct
14 Correct 0 ms 2040 KB Output is correct
15 Correct 0 ms 2040 KB Output is correct
16 Correct 0 ms 2040 KB Output is correct
17 Correct 0 ms 2040 KB Output is correct
18 Correct 0 ms 2040 KB Output is correct
19 Correct 0 ms 2040 KB Output is correct
20 Correct 0 ms 2040 KB Output is correct
21 Correct 0 ms 2040 KB Output is correct
22 Correct 0 ms 2040 KB Output is correct
23 Correct 0 ms 2040 KB Output is correct
24 Correct 0 ms 2040 KB Output is correct
25 Correct 0 ms 2040 KB Output is correct
26 Correct 0 ms 2040 KB Output is correct
27 Correct 0 ms 2040 KB Output is correct
28 Correct 0 ms 2040 KB Output is correct
29 Correct 0 ms 2040 KB Output is correct
30 Correct 0 ms 2040 KB Output is correct
31 Correct 0 ms 2040 KB Output is correct
32 Correct 0 ms 2040 KB Output is correct
33 Correct 0 ms 2040 KB Output is correct
34 Correct 0 ms 2040 KB Output is correct
35 Correct 0 ms 2040 KB Output is correct
36 Correct 0 ms 2040 KB Output is correct
37 Correct 0 ms 2040 KB Output is correct
38 Correct 0 ms 2040 KB Output is correct
39 Correct 0 ms 2040 KB Output is correct
40 Correct 0 ms 2040 KB Output is correct
41 Correct 0 ms 2040 KB Output is correct
42 Correct 0 ms 2040 KB Output is correct
43 Correct 0 ms 2040 KB Output is correct
44 Correct 0 ms 2040 KB Output is correct
45 Correct 0 ms 2040 KB Output is correct