Submission #703847

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

numbers

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 1e6;
const int INF = 1e9;
const int mod = 1e9 + 7;

int inp[MAX_N];

ll dp[25][11][11][2];

ll sol( int n, int a, int b, bool st ){

	ll& nas = dp[n][a][b][st];
	if( ~nas ) return nas;
	if( inp[n] == 10 ) return nas = 1;

	nas = 0;

	for( int i=0 ; i <= ( st ? 9 : inp[n] ) ;  i++ ){

		if( i == a || i == b ) continue;

		if( i == 0 and a == 10 and b == 10 ) nas += sol( n+1, a, b, true );
		else nas += sol( n+1, i, a, ( st || ( i != inp[n]) ) );
	}

	return nas;
}

ll get( ll a ){

	/*
	for( int i=0 ; i<a.size() ; i++ ) inp[i] = a[i] - '0';
	inp[a.size()] = 10;
	*/
	int size = 0;
	ll A = a;
	while( A ){
		size++;
		A/=10;
	}

	for( int i = size-1 ; i>=0 ; i-- ){
		inp[i] = a%10;
		a/=10;
	}
	inp[size] = 10;

	/*
	for( int i=0 ; i<=size ; i++ ) std::cout<<inp[i]<<" ";
	std::cerr<<"\n";
	*/

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

	return sol( 0, 10, 10, false );
}

int main () {

	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);

	ll a, b;
	std::cin>>a>>b;
	std::cout<<get(b) - get(a-1);
	

	return 0;
}

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