Submission #535181

#TimeUsernameProblemLanguageResultExecution timeMemory
535181Koful123Palindrome-Free Numbers (BOI13_numbers)C++17
100 / 100
2 ms352 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define endl "\n"
#define mod 1000000007
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

int dp[20][12][12][2];

int f(string s,int indx,int x,int y,int ok){
	
	if(indx == s.size())
		return 1;

	int &cur = dp[indx][x][y][ok];
	if(cur != -1)
		return cur;

	int fi = (indx == 0),se;
	if(ok) se = 9;
	else se = s[indx]-'0';

	for(int i=fi;i<=se;i++){
		if(i == x || i == y) continue;
		cur += f(s,indx+1,y,i,(ok||i<s[indx]-'0'));
	}

	return cur+=1;
}

void solve(){			

	int a,b;
	cin >> a >> b;

	memset(dp,-1,sizeof(dp));
	string tmp = to_string(a-1);
	int res = f(tmp,0,10,10,0);

	for(int i=2;i<tmp.size();i++){
		res += 81*pow(8,i-2);
	}

	memset(dp,-1,sizeof(dp));
	tmp = to_string(b);

	for(int i=2;i<tmp.size();i++){
		res -= 81*pow(8,i-2);
	}

	if(a > 9) res += 10;
	else if(a) res++; 
	if(b > 9) res -= 10;
	else res--;

	cout << f(tmp,0,10,10,0) - res << endl;
}

signed main(){

	ios_base::sync_with_stdio(0);	
	cin.tie(0);	

	#ifndef ONLINE_JUDGE
	//	freopen("in.txt","r",stdin);
	//	freopen("out.txt","w",stdout);
	#endif
 
	int t = 1;
	//cin >> t;

 	for(int i=1;i<=t;i++){
 		solve();
	}

	return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'long long int f(std::string, long long int, long long int, long long int, long long int)':
numbers.cpp:16:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  if(indx == s.size())
      |     ~~~~~^~~~~~~~~~~
numbers.cpp: In function 'void solve()':
numbers.cpp:44:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=2;i<tmp.size();i++){
      |              ~^~~~~~~~~~~
numbers.cpp:51:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=2;i<tmp.size();i++){
      |              ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...