oj.uz

Submission #283094

# Submission time Handle Problem Language Result Execution time Memory
283094 2020-08-25T09:56:57 Z Fasho Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 1 ms 512 KB 
#include <bits/stdc++.h>
#define N 20
#define ll long long int
#define fo(i,x,y)	for(int i=x;i<=y;i++)
#define fs(ar,n) fo(i,1,n) cin>>ar[i]
#define sp " "
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll> 
#define fast2 freopen ("in.txt","r",stdin);freopen ("out.txt","w",stdout);
#define mod 1000000007
using namespace std;

ll n,m,ar[N],sum,t,pw[30],dp[N][11][11][3][2];

char s[N],c[N];

ll f(int ind,int l1,int l2,int flag,int tut)
{
	if(dp[ind][l1][l2][flag][tut]!=-1)
		return dp[ind][l1][l2][flag][tut];
	if(ind>n)
		return min(flag,1);

	ll top=0;
	// tutmac=max(tutmac,2);
	if(!tut)
	{
		fo(i,0,ar[ind])
		{
			ll x=tut;
			if(i!=ar[ind])
				x=1;
			if(i!=l1 && i!=l2)
				top+=f(ind+1,l2,i,min(flag+1,2),x);
			if(i==0 && flag==1)
				top+=f(ind+1,l2,i,min(flag+1,2),x);
		}
	}
	else
		fo(i,0,9)
		{
			ll x=tut;
			if(i!=ar[ind])
				x=1;
			if(i!=l1 && i!=l2)
				top+=f(ind+1,l2,i,min(flag+1,2),1);
			if(i==0 && flag==1 && l1==0 && l2!=0)
				top+=f(ind+1,l2,i,min(flag+1,2),1);
		}
	if(!flag)
		top+=f(ind+1,0,0,0,1);
	// cout<<ind<<sp<<l1<<sp<<l2<<sp<<top<<endl;
	return dp[ind][l1][l2][flag][tut]=top;
}

ll calc()
{
	return f(1,0,0,0,0);
}


int main()
{
	fast;
	cin>>c+1;
	cin>>s+1;
	memset(dp,-1,sizeof(dp));
	
	pw[0]=1;
	fo(i,1,20)
	pw[i]=pw[i-1]*8;
	n=strlen(s+1);
	fo(i,1,n)
		ar[i]=s[i]-'0';
	sum=calc();
	// cout<<"[d]"<<sp;
	// cout<<sum<<endl;
	n=strlen(c+1);
	fo(i,1,n)
	ar[i]=c[i]-'0';
	memset(dp,-1,sizeof(dp));
	ll y=calc();
	sum-=y;
	// cout<<"[d]"<<sp;
	// cout<<y<<endl;
	ar[0]=10;
	ll flag=1;
	fo(i,2,n)
	if(ar[i]==ar[i-1] || ar[i]==ar[i-2])
		flag=0;
	sum+=flag;
	cout<<sum<<endl;


}

Compilation message

numbers.cpp: In function 'long long int f(int, int, int, int, int)':
numbers.cpp:47:7: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   47 |    ll x=tut;
      |       ^
numbers.cpp: In function 'int main()':
numbers.cpp:70:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |  cin>>c+1;
      |       ~^~
numbers.cpp:71:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |  cin>>s+1;
      |       ~^~

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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