#include <bits/stdc++.h>
using namespace std;
#define int long long
bool check(string a){
for(int i = 0; i < (int)a.size()-1; i++){
if(a[i] == a[i+1]) return true;
}
for(int i = 0; i < (int)a.size()-2; i++){
if(a[i] == a[i+2]) return false;
}
return true;
}
string toString(int a){
if(a == 0) return "0";
string s = "";
while(a){
s = ((char)(a%10+'0'))+s;
a/=10;
}
return s;
}
vector<int> v;
string a;
string b;
int memo[2][2][19][11][2][11];
int dp(bool isPal, bool canTakeAnything, int n, int last, bool isMini, int lastlast){
// cout << isPal << ' ' << canTakeAnything << ' ' << n << ' ' << last << ' ' << isMini << endl;
if(n == a.size()){
if(isPal) return 1;
else return 0;
}
//cout << memo[isPal][canTakeAnything][n][last][isMini] << endl;
if(memo[isPal][canTakeAnything][n][last][isMini][lastlast] != -1) return memo[isPal][canTakeAnything][n][last][isMini][lastlast];
memo[isPal][canTakeAnything][n][last][isMini][lastlast] = 0;
if(canTakeAnything){
int c = a[n]-'0'+1;
for(int i = (isMini ? c : 1); i <= 10; i++){
bool cond = false;
if(isMini && i == c){
cond = true;
}
if(i == last || i == lastlast){
memo[isPal][canTakeAnything][n][last][isMini][lastlast] += dp(1,canTakeAnything,n+1,i,cond,last);
}else{
memo[isPal][canTakeAnything][n][last][isMini][lastlast] += dp(isPal, canTakeAnything, n+1, i,cond,last);
}
}
}else{
int c = a[n]-'0'+1;
int d = b[n]-'0'+1;
for(int i = (isMini ? c : 1); i<= d; i++){
bool cond = false;
if(isMini && i == c){
cond = true;
}
if(i == last || i== lastlast){
memo[isPal][canTakeAnything][n][last][isMini][lastlast] += dp(1, i < d, n+1,i,cond,last);
}else{
memo[isPal][canTakeAnything][n][last][isMini][lastlast] += dp(isPal, i < d, n+1,i, cond,last);
}
}
}
return memo[isPal][canTakeAnything][n][last][isMini][lastlast];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int c, d;
cin >> c >> d;
string s = "";
a = toString(c);
b = toString(d);
for(int i = 0; i < (int)(b.size()-a.size()); i++){
s += '0';
}
a = s + a;
int tot = (d-c+1);
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
for(int k = 0; k < 19; k++){
for(int l = 0; l <= 10; l++){
for(int m = 0; m < 2; m++){
for(int n = 0; n <= 10; n++){
memo[i][j][k][l][m][n] = -1;
}
}
}
}
}
}
tot-=dp(0,0,0,0,1,0);
cout << tot << endl;
}
Compilation message
numbers.cpp: In function 'long long int dp(bool, bool, long long int, long long int, bool, long long int)':
numbers.cpp:35:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(n == a.size()){
~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 5 |
Correct |
3 ms |
412 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 9 |
Correct |
2 ms |
512 KB |
Output is correct |
| 10 |
Correct |
2 ms |
512 KB |
Output is correct |
| 11 |
Correct |
3 ms |
512 KB |
Output is correct |
| 12 |
Correct |
2 ms |
512 KB |
Output is correct |
| 13 |
Correct |
3 ms |
512 KB |
Output is correct |
| 14 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 16 |
Correct |
2 ms |
512 KB |
Output is correct |
| 17 |
Correct |
2 ms |
512 KB |
Output is correct |
| 18 |
Correct |
2 ms |
512 KB |
Output is correct |
| 19 |
Correct |
2 ms |
512 KB |
Output is correct |
| 20 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
3 ms |
512 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 6 |
Correct |
2 ms |
512 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 10 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 11 |
Correct |
2 ms |
512 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 13 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 14 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
456 KB |
Output isn't correct |
| 16 |
Correct |
2 ms |
512 KB |
Output is correct |
| 17 |
Correct |
2 ms |
512 KB |
Output is correct |
| 18 |
Correct |
3 ms |
512 KB |
Output is correct |
| 19 |
Correct |
2 ms |
512 KB |
Output is correct |
| 20 |
Correct |
2 ms |
512 KB |
Output is correct |
| 21 |
Correct |
2 ms |
512 KB |
Output is correct |
| 22 |
Correct |
2 ms |
556 KB |
Output is correct |
| 23 |
Correct |
2 ms |
512 KB |
Output is correct |
| 24 |
Correct |
3 ms |
512 KB |
Output is correct |
| 25 |
Correct |
3 ms |
512 KB |
Output is correct |
| 26 |
Correct |
3 ms |
512 KB |
Output is correct |
| 27 |
Correct |
3 ms |
512 KB |
Output is correct |
| 28 |
Correct |
3 ms |
512 KB |
Output is correct |
| 29 |
Correct |
3 ms |
512 KB |
Output is correct |
| 30 |
Correct |
2 ms |
512 KB |
Output is correct |
| 31 |
Correct |
3 ms |
512 KB |
Output is correct |
| 32 |
Correct |
3 ms |
512 KB |
Output is correct |
| 33 |
Correct |
3 ms |
512 KB |
Output is correct |
| 34 |
Correct |
2 ms |
512 KB |
Output is correct |
| 35 |
Correct |
2 ms |
512 KB |
Output is correct |
| 36 |
Correct |
3 ms |
512 KB |
Output is correct |
| 37 |
Correct |
3 ms |
512 KB |
Output is correct |
| 38 |
Correct |
3 ms |
512 KB |
Output is correct |
| 39 |
Correct |
2 ms |
512 KB |
Output is correct |
| 40 |
Correct |
3 ms |
512 KB |
Output is correct |
| 41 |
Correct |
4 ms |
512 KB |
Output is correct |
| 42 |
Correct |
2 ms |
512 KB |
Output is correct |
| 43 |
Correct |
3 ms |
512 KB |
Output is correct |
| 44 |
Correct |
3 ms |
512 KB |
Output is correct |
| 45 |
Correct |
2 ms |
512 KB |
Output is correct |
