oj.uz

답안 #26378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26378 2017-06-29T13:53:42 Z samir_droubi Palindrome-Free Numbers (BOI13_numbers) C++14
13.75 / 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];
		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];
}
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+1);
	printf("%lld\n",sb-sa);
	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: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:51: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
13.75 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2040 KB Output is correct
2 Correct 0 ms 2040 KB Output is correct
3 Incorrect 0 ms 2040 KB Output isn't correct
4 Incorrect 0 ms 2040 KB Output isn't 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 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 Correct 0 ms 2040 KB Output is 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

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