Submission #232035

#	Time	Username	Problem	Language	Result	Execution time	Memory
232035		mosiashvililuka	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	5 ms	384 KiB

numbers

#include<bits/stdc++.h>
using namespace std;
long long c,d,e,zx,xc,i,j,ii,jj,dp[22][12][12],p[22],pi,pas,sz;
string a,b,aa,bb;
void rec(long long q, bool bo1, bool bo2, long long w){
	//cout<<q<<" "<<bo1<<" "<<bo2<<" "<<w<<"  x  "<<pi<<endl;
	//for(long long h=1; h<=pi; h++) cout<<p[h]<<" kala ";
	//cout<<endl;
	if(q>=a.size()){
		//cout<<"CAT"<<endl<<endl<<endl;
		pas++;
		return;
	}
	if(bo1==1&&bo2==1){
		long long hj=pas;
		if(a.size()-q>=2){
		for(i=0; i<=9; i++){
			for(j=0; j<=9; j++){
				if(i==j) continue;
				if((w<pi&&p[pi]==i)||(w<pi&&p[pi]==j)||(w<pi-1&&p[pi-1]==i)) continue;
				pas+=dp[a.size()-q][i][j];
			}
		}
		}else{
			for(i=0; i<=9; i++){
				if((i==p[pi]&&w<pi)||(i==p[pi-1]&&w<pi-1)) continue;
				pas+=dp[1][i][0];
			}
		}
		//cout<<"DOG  +"<<pas-hj<<endl<<endl<<endl;
		return;
	}
	for(long long h=0; h<=9; h++){
		if(bo1==0&&h<a[q]-'0') continue;
		if(bo2==0&&h>b[q]-'0') continue;
		if(pi>w&&h==p[pi]) continue;
		if(pi-1>w&&h==p[pi-1]) continue;
		bool qw=bo1,we=bo2;
		if(h>a[q]-'0') qw=1;
		if(h<b[q]-'0') we=1;
		pi++;p[pi]=h;
		if(w==100&&h!=0) rec(q+1,qw,we,q); else rec(q+1,qw,we,w);
		pi--;
	}
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b;
	while(a.size()<b.size()) a.insert(0,"0");
	dp[0][0][0]=1;
	for(i=0; i<=9; i++) dp[1][i][0]=1;
	for(i=2; i<=19; i++){
		for(ii=0; ii<=9; ii++){
			for(j=0; j<=9; j++){
				if(ii==j) continue;
				if(i==2){
					dp[i][ii][j]+=dp[i-1][j][0];
					continue;
				}
				for(jj=0; jj<=9; jj++){
					if(ii==jj||j==jj) continue;
					dp[i][ii][j]+=dp[i-1][j][jj];
				}
			}
		}
	}
	p[0]=-1;
	rec(0,0,0,100);
	cout<<pas;
	return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'void rec(long long int, bool, bool, long long int)':
numbers.cpp:9:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(q>=a.size()){
     ~^~~~~~~~~~
numbers.cpp:15:13: warning: unused variable 'hj' [-Wunused-variable]
   long long hj=pas;
             ^~

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