Submission #81575

#	Time	Username	Problem	Language	Result	Execution time	Memory
81575		arman_ferdous	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	3 ms	944 KiB

numbers

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int n, arr[20];
ll dp[20][2][2][11][11];

vector<ll> v;
ll DP(int pos, int s, int t, int f1, int f2) {
	if(pos >= n) return 1;
	if(dp[pos][s][t][f1][f2] != -1) return dp[pos][s][t][f1][f2];
	int bound = (t ? arr[pos] : 9);
	ll ret = 0;
	for(int i = 0; i <= bound; i++) {
		if(i == f1 || i == f2) continue;
		ret += DP(pos+1, (i==0 ? s : 1), (i<arr[pos] ? 0 : t), (i==0 && !s)?10:i , f1);
		//        next      started?           tight?           prev value      the one before
	}
	return dp[pos][s][t][f1][f2] = ret;
}

void apply(ll x) {
	n = log10(x) + 1;
	for(int i = n-1; i >= 0; i--) {
		arr[i] = x % 10;
		x /= 10;
	}
}

int main() {
	ll a, b;
	scanf("%lld %lld", &a, &b);

	if(b == 0) { puts("1"); return 0; }

	apply(b);
	memset(dp,-1,sizeof dp);
	ll ansr = DP(0,0,1,10,10);

	if(a == 1) { printf("%lld\n", ansr - 1); return 0; }
	if(a == 0) { printf("%lld\n", ansr);     return 0; }

	apply(a-1);
	memset(dp,-1,sizeof dp);
	ll ansl = DP(0,0,1,10,10);

	printf("%lld\n", ansr - ansl);
	return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'int main()':
numbers.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld", &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~

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