Submission #165165

#	Time	Username	Problem	Language	Result	Execution time	Memory
165165		Lawliet	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	15 ms	508 KiB

numbers

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXL = 10;
const int MAXD = 20;

int v[MAXD];

lli A, B;

lli dp[MAXD][MAXL][MAXL][2];

lli solve(int i, int l1, int l2, int eq)
{
	lli& ans = dp[i][l1][l2][eq];

	if( ans != -1 ) return ans;

	if( i == 0 ) return ans = 1;

	ans = 0;

	if( eq == 1 )
	{
		if( v[i] != l1 && v[i] != l2 ) ans += solve( i - 1 , v[i] , l1 , 1 );

		for(int j = 0 ; j < v[i] ; j++)
			if( j != l1 && j != l2 ) ans += solve( i - 1 , j , l1 , 0 );
	}
	else
	{
		for(int j = 0 ; j < 10 ; j++)
			if( j != l1 && j != l2 ) ans += solve( i - 1 , j , l1 , 0 );
	}

	return ans;
}

lli s(lli k)
{
	if( k <= 10 ) return k + 1;

	int last;

	for(int i = 1 ; i <= 19 ; i++)
	{
		v[i] = k%10;
		k /= 10;

		if( v[i] != 0 ) last = i;
	}

	memset( dp , -1 , sizeof(dp) );

	lli ans = 0;

	for(int i = 1 ; i < 10 ; i++)
	{
		for(int j = 0 ; j < 10 ; j++)
		{
			if( i == j ) continue;
			if( i > v[last] ) continue;
			if( i == v[last] && j > v[last - 1] ) continue;

			if( i == v[last] && j == v[last - 1] ) ans += solve( last - 2 , j , i , 1 );
			else ans += solve( last - 2 , j , i , 0 );
		}
	}

	for(int sz = 2 ; sz < last ; sz++)
		for(int i = 1 ; i < 10 ; i++)
			for(int j = 0 ; j < 10 ; j++) if( i != j ) ans += solve( sz - 2 , j , i , 0 );

	return ans + 10;
}

int main()
{
	scanf("%lld %lld",&A,&B);

	printf("%lld\n",s( B ) - s( A - 1 ));
}

Compilation message (stderr)

numbers.cpp: In function 'int main()':
numbers.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&A,&B);
  ~~~~~^~~~~~~~~~~~~~~~~~~
numbers.cpp: In function 'lli s(lli)':
numbers.cpp:64:18: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if( i > v[last] ) continue;
            ~~~~~~^

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