Submission #253442

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

numbers

#include<iostream>
#include<string>
#include<sstream>
using namespace std;
#define ll unsigned long long int
ll dp[19][10][10];
ll dp2[19];
ll dp1[19][10];
ll dp3[19][10];
ll dpz[19];
/*bool c(string a)
{
	if (a.length()==1)	return true;
	if (a.length()==2)	return true;
	int N=a.length();
	int i;
	for (i=0;i<N-3;i++)
	{
		if (a[i] == a[i+1] || a[i] == a[i+2])	return false;
	}
	return true;
}*/
int num(char p)
{
	switch(p)
	{
		case '0' :	return 0;
		case '1' :	return 1;
		case '2' :	return 2;
		case '3' :	return 3;
		case '4' :	return 4;
		case '5' :	return 5;
		case '6' :	return 6;
		case '7' :	return 7;
		case '8' :	return 8;
		case '9' :	return 9;
	}
}
ll f(int k, int i , int j)
{
	if (dp[k][i][j] != -1) return dp[k][i][j];
	ll p,q,val = 0;
	if (j==0)
	{
		for (p=0;p<10;p++)
		{
			for (q=1;q<10;q++)
				if ((q!=i)&&(q!=0)&&(p!=0))
					val += f(k-2,q,p);
		}
	}
	else 
	{
		for (p=0;p<10;p++)
			if (p!=j && p!=i)
				val += f(k-1,j,p);
	}
	dp[k][i][j] = val;
	return dp[k][i][j];
}
ll count(string a)
{
	
	int i,N = a.length(),j,k,p;
	if (N==1)	return num(a[0]) - 1 ;
	ll val = 0;//dp2[N-1]
	if (N==2)
	{
		val = 9;
		k = num(a[0])*10 + num(a[1]);
		for (i=1;i<10;i++)
		{
			if (i>num(a[0]))	break;
			for (j=0;j<10;j++)
			{
				if (i==num(a[0]) && j==num(a[1]))	break;
				if (i!=j)
				{
					val++;
				}
			}
		} 
		return val;
	}
	for (i=1;i<N;i++)	val += dp2[i];
	for (i=1;i<num(a[0]);i++) // doing the first digit upto a;
		val += dp1[N][i];
	for (i=0;i<num(a[1]);i++)
	{
		 val += dp[N][num(a[0])][i];
	}
	//cout<<"Value calculated till now is "<<val<<endl;
	for (k=N-2;k>0;k--)
	{
		//cout<<"looking from digit "<<N-k<<endl;
		if ((a[N-k-2] == a[N-k-1])||(k<N-2&&a[N-k-1] == a[N-k-3]))	return val;
		else if (a[N-k-1] != '0')
			for (i=0;i<num(a[N-k]);i++)
			{
				//cout<<"entered\n";
				if (i != num(a[N-k-2]))
		 			val += dp[k+1][num(a[N-k-1])][i];
			}
		else 
			for (i=1;i<num(a[N-k]);i++)
			{
				if (i != num(a[N-k-2]))
		 		val += dp1[k][i] - dp[k][i][0];
			}
		//cout<<"Value calculated till now is "<<val<<endl;
		/*else
		{
			p=num(a[N-k-2]);
			val += dp2[k] - dp1[k][p] - dp3[k][0] + dp[k][p][0];
		}*/
		//cout<<"final value is "<<k<<" "<<dpz[k]<<endl;// - dp1[k][num(a[N-k-1])] - dp1[k][num(a[N-k-2])] - dp3[k][num(a[N-k-1])] + dp[k][num(a[N-k-2])][num(a[N-k-1])]<<endl<<endl;
	}
	if (a[N-2] != a[N-3])		
		for (i=0;i<num(a[N-1]);i++)
			if (i!=num(a[N-2])&&i!=num(a[N-3]));//	val++;
	return val;
}

int main()
{
	int i,j,k;
	ll p;
	for (j=0;j<10;j++)
			for (i=1;i<10;i++)
			{
				dp[2][i][j] = (i==j) ? 0 : 1;
				dp[3][i][j] = (i==j) ? 0 : 8;
			}
	for (k=4;k<19;k++)
		for (j=0;j<10;j++)
			for (i=1;i<10;i++)
				dp[k][i][j]= (i==j) ? 0 : -1;
	for (k=2;k<19;k++)
	{
		dp2[k] = 0;
	}
	dp2[1] = 9;	
	for (k=2;k<19;k++)
		for (j=0;j<10;j++)
			for (i=1;i<10;i++)
			{
				dp3[k][j] += f(k,i,j);
				dp1[k][i] += f(k,i,j);
				dp2[k] += f(k,i,j);
			}
	dp1[1][0] = 1;
	dp1[2][0] = 9;
	dpz[2] = 90;
	dpz[1] = 10;
	for (k=3;k<19;k++)
		{
			dp1[k][0] = dp2[k-1] - dp3[k-1][0];
			dpz[k] = dp2[k] + dp1[k][0];
		}			
	for (i=1;i<10;i++)	dp1[1][i] = 1;
	ostringstream st[2];
	string a[2];
	/*while (true){

	cin>>a[0];
	cout<<count (a[0])<<endl;	}*/
	//cout<<dp2[4]<<endl<<dp2[3];
	cin>>a[0]>>p;
	st[1]<<p+1;
	a[1] = st[1].str();
	cout<<count(a[1]) - count(a[0]);
	return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'long long unsigned int f(int, int, int)':
numbers.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (dp[k][i][j] != -1) return dp[k][i][j];
      ~~~~~~~~~~~~^~~~~
numbers.cpp:48:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if ((q!=i)&&(q!=0)&&(p!=0))
          ~^~~
numbers.cpp:55:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (p!=j && p!=i)
        ~^~~
numbers.cpp:55:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (p!=j && p!=i)
                ~^~~
numbers.cpp: In function 'long long unsigned int count(std::__cxx11::string)':
numbers.cpp:64:27: warning: unused variable 'p' [-Wunused-variable]
  int i,N = a.length(),j,k,p;
                           ^
numbers.cpp: In function 'int num(char)':
numbers.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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