oj.uz

Submission #475627

# Submission time Handle Problem Language Result Execution time Memory
475627 2021-09-23T13:56:33 Z Pietra Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 1 ms 336 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std ; 

int a, b, dp[22][2][11][11] ; 
vector<int> num ; 

int solve(int pos, bool flag, int p1, int p2){

	if(pos == num.size()) return 1 ; 
	if(dp[pos][flag][p1][p2] != -1) return dp[pos][flag][p1][p2] ; 

	int tot = 0 ; 

	if(flag){ // garantido 
		for(int i = 0 ; i < 10 ; i++){
			if(i == p1 || i == p2) continue ;
			tot += solve(pos+1, flag, p2, i) ; 
		}
	}

	else{
		for(int i = 0 ; i <= num[pos] ; i++){
			if(i == p1 || i == p2) continue ; 
			tot += solve(pos + 1, (i != num[pos]), p2, i) ; 
		}
	}

	return dp[pos][flag][p1][p2] = tot ; 

}

int calc(int a){

	if(a < 0) return 0 ; 
	if(a == 0) return 1 ; 
	num.clear() ; 
	while(a){
		num.push_back(a%10) ; a /= 10 ;
	}

	reverse(num.begin(), num.end()) ; 

	memset(dp, -1, sizeof dp) ; 

	int ans = 0 ; 
	for(int i = 0 ; i < num.size() ; i++) ans += solve(i, i != 0, (i == num.size() - 1 ? 10 : 0), 10) ; 
	return ans ; 

}

int32_t main(){

	cin >> a >> b ; 
	cout << calc(b) - calc(a-1) << "\n" ; 

}

Compilation message

numbers.cpp: In function 'long long int solve(long long int, bool, long long int, long long int)':
numbers.cpp:10:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  if(pos == num.size()) return 1 ;
      |     ~~~~^~~~~~~~~~~~~
numbers.cpp: In function 'long long int calc(long long int)':
numbers.cpp:47:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i = 0 ; i < num.size() ; i++) ans += solve(i, i != 0, (i == num.size() - 1 ? 10 : 0), 10) ;
      |                  ~~^~~~~~~~~~~~
numbers.cpp:47:67: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i = 0 ; i < num.size() ; i++) ans += solve(i, i != 0, (i == num.size() - 1 ? 10 : 0), 10) ;
      |                                                                 ~~^~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 296 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 284 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 300 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 304 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1 ms 336 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 332 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 1 ms 332 KB Output is correct
38 Correct 1 ms 332 KB Output is correct
39 Correct 1 ms 332 KB Output is correct
40 Correct 1 ms 332 KB Output is correct
41 Correct 1 ms 332 KB Output is correct
42 Correct 1 ms 332 KB Output is correct
43 Correct 1 ms 332 KB Output is correct
44 Correct 1 ms 332 KB Output is correct
45 Correct 1 ms 332 KB Output is correct