제출 #1126695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126695		mankesh016	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	1 ms	332 KiB

numbers

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

#ifdef cp_first
#include "algo/debug.h"
#else
#define debug(...)
#endif

#define int long long


int dp[20][2][11][11];
// Key Observations, there should not be palindrome of length 2 and 3

int helper(int idx, bool tight, int last, int slast, string &s) {
	if (idx == s.size()) return 1;
	if (dp[idx][tight][last][slast] != -1) return dp[idx][tight][last][slast];

	int ans = 0;

	int till = tight ? s[idx] - '0' : 9;
	for (int i = 0; i <= till; i++) {
		if (i == last || i == slast) continue;

		if (last == -1 && i == 0) {
			// not started
			ans += helper(idx + 1, tight && i == till, last, slast, s);
		}
		else ans += helper(idx + 1, tight && i == till, i, last, s);
	}

	return dp[idx][tight][last][slast] = ans;
}

int call(int n) {
	string s = to_string(n);
	memset(dp, -1, sizeof dp);
	return helper(0, 1, -1, -1, s);
}

// December 2024
signed main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	// int TC; cin >> TC; while (TC--)
	{
		int a, b; cin >> a >> b;

		int ans = call(b);
		if (a) ans -= call(a - 1);

		cout << ans << "\n";
	}
}

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