oj.uz

답안 #26380

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26380 2017-06-29T14:45:22 Z samir_droubi Palindrome-Free Numbers (BOI13_numbers) C++14
1.25 / 100
 0 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)
				sm[i]+=calc(i,j,k);
		sm[i]+=sm[i-1];
	}

	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)
               ^

Subtask #1
1.25 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2040 KB Output isn't correct
2 Incorrect 0 ms 2040 KB Output isn't correct
3 Incorrect 0 ms 2040 KB Output isn't correct
4 Incorrect 0 ms 2040 KB Output isn't correct
5 Incorrect 0 ms 2040 KB Output isn't correct
6 Incorrect 0 ms 2040 KB Output isn't correct
7 Incorrect 0 ms 2040 KB Output isn't correct
8 Incorrect 0 ms 2040 KB Output isn't correct
9 Incorrect 0 ms 2040 KB Output isn't correct
10 Incorrect 0 ms 2040 KB Output isn't correct
11 Incorrect 0 ms 2040 KB Output isn't correct
12 Incorrect 0 ms 2040 KB Output isn't correct
13 Incorrect 0 ms 2040 KB Output isn't correct
14 Incorrect 0 ms 2040 KB Output isn't correct
15 Incorrect 0 ms 2040 KB Output isn't correct
16 Incorrect 0 ms 2040 KB Output isn't correct
17 Incorrect 0 ms 2040 KB Output isn't correct
18 Correct 0 ms 2040 KB Output is correct
19 Incorrect 0 ms 2040 KB Output isn't correct
20 Incorrect 0 ms 2040 KB Output isn't correct

Subtask #2
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2040 KB Output isn't correct
2 Incorrect 0 ms 2040 KB Output isn't correct
3 Incorrect 0 ms 2040 KB Output isn't correct
4 Incorrect 0 ms 2040 KB Output isn't correct
5 Incorrect 0 ms 2040 KB Output isn't correct
6 Incorrect 0 ms 2040 KB Output isn't correct
7 Incorrect 0 ms 2040 KB Output isn't correct
8 Incorrect 0 ms 2040 KB Output isn't correct
9 Incorrect 0 ms 2040 KB Output isn't correct
10 Incorrect 0 ms 2040 KB Output isn't correct
11 Incorrect 0 ms 2040 KB Output isn't correct
12 Incorrect 0 ms 2040 KB Output isn't correct
13 Incorrect 0 ms 2040 KB Output isn't correct
14 Incorrect 0 ms 2040 KB Output isn't correct
15 Incorrect 0 ms 2040 KB Output isn't correct
16 Incorrect 0 ms 2040 KB Output isn't correct
17 Incorrect 0 ms 2040 KB Output isn't correct
18 Incorrect 0 ms 2040 KB Output isn't correct
19 Incorrect 0 ms 2040 KB Output isn't correct
20 Incorrect 0 ms 2040 KB Output isn't correct
21 Incorrect 0 ms 2040 KB Output isn't correct
22 Incorrect 0 ms 2040 KB Output isn't correct
23 Incorrect 0 ms 2040 KB Output isn't correct
24 Incorrect 0 ms 2040 KB Output isn't correct
25 Incorrect 0 ms 2040 KB Output isn't correct
26 Incorrect 0 ms 2040 KB Output isn't correct
27 Incorrect 0 ms 2040 KB Output isn't correct
28 Incorrect 0 ms 2040 KB Output isn't correct
29 Incorrect 0 ms 2040 KB Output isn't correct
30 Incorrect 0 ms 2040 KB Output isn't correct
31 Incorrect 0 ms 2040 KB Output isn't correct
32 Incorrect 0 ms 2040 KB Output isn't correct
33 Incorrect 0 ms 2040 KB Output isn't correct
34 Incorrect 0 ms 2040 KB Output isn't correct
35 Incorrect 0 ms 2040 KB Output isn't correct
36 Incorrect 0 ms 2040 KB Output isn't correct
37 Incorrect 0 ms 2040 KB Output isn't correct
38 Incorrect 0 ms 2040 KB Output isn't correct
39 Incorrect 0 ms 2040 KB Output isn't correct
40 Incorrect 0 ms 2040 KB Output isn't correct
41 Incorrect 0 ms 2040 KB Output isn't correct
42 Incorrect 0 ms 2040 KB Output isn't correct
43 Incorrect 0 ms 2040 KB Output isn't correct
44 Incorrect 0 ms 2040 KB Output isn't correct
45 Incorrect 0 ms 2040 KB Output isn't correct