oj.uz

Submission #153532

# Submission time Handle Problem Language Result Execution time Memory
153532 2019-09-14T14:46:18 Z brcode Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 15 ms 10488 KB 
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
const long long MOD = 1e9+7;
vector<long long> v1;
long long dp[50][32][32][5][5];
 
long long rec(long long len,long long a,long long b,bool limit, long long leading){
   // cout<<len<<" "<<a<<" "<<b<<" "<<limit<<" "<<leading<<endl;
    if(dp[len][a][b][limit][leading]!=-1){
        return dp[len][a][b][limit][leading];
    }
    if(len >= (long long)v1.size()-1){
 
        return 1;
    }
    if(limit){
        //last digit added was the largest possible digit
        dp[len][a][b][limit][leading] = 0;
        for(long long i=0;i<=9;i++){
 
            if(i>v1[len+1]){
                //can't add a larger digit
                break;
            }
            if(leading == 3 && i==0){
                //a new digit was just added after a bunch of zeroes
                if(i==v1[len+1]){
                    //largest possible digit I can add(Can add a 0, leading 0s don't count as a palindrome)
                    dp[len][a][b][1][leading] += rec(len+1,b,i,1,0);
 
                }else{
                    //can do the same thing
                    dp[len][a][b][1][leading] += rec(len+1,b,i,0,0);
 
                }
                continue;
            }
            else if(leading ==3){
                //a number that's not 0 is being added after a number that's just been added after a bunch of 0s
                if((i!=a && i!=b) && i == v1[len+1]){
                    //if this number's not a palindrome and it's the largest possible digit to add, add it
                    dp[len][a][b][1][leading] += rec(len+1,b,i,1,0);
                    continue;
                }
                else if(i!=a && i!=b){
                    //same as above, but it's not the larges possible digit to add
                    dp[len][a][b][1][leading] += rec(len+1,b,i,0,0);
                    continue;
 
                }
            }
            else if(leading && i==0){
                //have leading 0s, want to add another 0
                if(i==v1[len+1]){
                    //largest digit we can add is this 0(I don't think this case would actually exist)
                    dp[len][a][b][1][leading] += rec(len+1,b,i,1,1);
 
                }else{
                    //we add this 0 and continue (our current string is just a bunch of 0s)
                    dp[len][a][b][1][leading] += rec(len+1,b,i,0,1);
 
                }
                continue;
            }
            else if(leading){
                //we have a bunch of leading 0s and we want to add a non zero digit
                 if((i!=a && i!=b) && i == v1[len+1]){
                    //first 2 conditions will always hold true I think,the third is a check to see if this digit is the max digit we can add. If it is we shift our leading state to 3(dealt with above)
                    dp[len][a][b][1][leading] += rec(len+1,b,i,1,3);
                    continue;
                }
                else if(i!=a && i!=b){
                    //Again first 2 conditions will always hold true
                    dp[len][a][b][1][leading] += rec(len+1,b,i,0,3);
                    continue;
 
                }
            }
            else if((i!=a && i!=b) && i == v1[len+1]){
                //after a bunch of leading 0s(or none), we have a non zero digit + x more digits (where x+1>=2)
                dp[len][a][b][1][leading] += rec(len+1,b,i,1,0);
 
            }
            else if(i!=a && i!=b){
                dp[len][a][b][1][leading] += rec(len+1,b,i,0,0);
 
            }
        }
 
        return dp[len][a][b][limit][leading];
    }else{
        dp[len][a][b][limit][leading] = 0;
 
        for(long long i=0;i<=9;i++){
 
            if(leading == 3 && i == 0){
                dp[len][a][b][limit][leading] += rec(len+1,b,i,limit,0);
            }else if(leading ==3){
               
                if(i!=a && i!=b){
 
                    dp[len][a][b][limit][leading] += rec(len+1,b,i,limit,0);
                }
            }
            else if(leading && i==0){
                dp[len][a][b][limit][leading] += rec(len+1,b,i,limit,1);
 
            }else if(leading){
                dp[len][a][b][limit][leading] += rec(len+1,b,i,limit,3);
                continue;
            }
            else if(i!=a && i!=b){
                dp[len][a][b][limit][leading] += rec(len+1,b,i,limit,0);
            }
 
        }
        return dp[len][a][b][limit][leading];
    }
}
long long solve(long long curr){
    v1.clear();
    for(long long i=0;i<=49;i++){
        for(long long j=0;j<=31;j++){
            for(long long k=0;k<=31;k++){
                for(long long l=0;l<=4;l++){
                    for(long long m=0;m<=4;m++){
                        dp[i][j][k][l][m] = -1;
                    }
                }
            }
        }
    }
    if(curr == 0){
        return 1;
    }
    while(curr){
       v1.push_back(curr%10);
 
       curr/=10;
    }
 
    v1.push_back(0);
    reverse(v1.begin(),v1.end());
    long long ans = 0;
    for(long long i=0;i<=9;i++){
        if(v1[1]<i){
            break;
        }
 
        if(i ==0){
            ans+=rec(1,30,0,false,true);
      
           // cout<<ans<<endl;
            continue;
        }
 
        ans+=rec(1,30,i,v1[1] == i,false);
     
 
    }
    return ans;
}
int main(){
     long long a,b;
    cin>>a>>b;

    cout<<solve(b)-solve(a-1)<<endl;
 
}

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10360 KB Output is correct
2 Correct 12 ms 10360 KB Output is correct
3 Correct 12 ms 10408 KB Output is correct
4 Correct 12 ms 10360 KB Output is correct
5 Correct 11 ms 10376 KB Output is correct
6 Correct 11 ms 10364 KB Output is correct
7 Correct 11 ms 10360 KB Output is correct
8 Correct 11 ms 10360 KB Output is correct
9 Correct 12 ms 10488 KB Output is correct
10 Correct 11 ms 10360 KB Output is correct
11 Correct 12 ms 10360 KB Output is correct
12 Correct 11 ms 10388 KB Output is correct
13 Correct 11 ms 10360 KB Output is correct
14 Correct 12 ms 10360 KB Output is correct
15 Correct 12 ms 10364 KB Output is correct
16 Correct 12 ms 10376 KB Output is correct
17 Correct 12 ms 10364 KB Output is correct
18 Correct 12 ms 10360 KB Output is correct
19 Correct 12 ms 10352 KB Output is correct
20 Correct 12 ms 10332 KB Output is correct
21 Correct 12 ms 10360 KB Output is correct
22 Correct 11 ms 10360 KB Output is correct
23 Correct 12 ms 10360 KB Output is correct
24 Correct 12 ms 10380 KB Output is correct
25 Correct 12 ms 10360 KB Output is correct
26 Correct 12 ms 10360 KB Output is correct
27 Correct 12 ms 10360 KB Output is correct
28 Correct 12 ms 10360 KB Output is correct
29 Correct 12 ms 10352 KB Output is correct
30 Correct 12 ms 10360 KB Output is correct
31 Correct 12 ms 10360 KB Output is correct
32 Correct 12 ms 10360 KB Output is correct
33 Correct 12 ms 10360 KB Output is correct
34 Correct 12 ms 10356 KB Output is correct
35 Correct 12 ms 10360 KB Output is correct
36 Correct 12 ms 10360 KB Output is correct
37 Correct 11 ms 10352 KB Output is correct
38 Correct 12 ms 10360 KB Output is correct
39 Correct 12 ms 10360 KB Output is correct
40 Correct 12 ms 10388 KB Output is correct
41 Correct 12 ms 10360 KB Output is correct
42 Correct 12 ms 10488 KB Output is correct
43 Correct 12 ms 10360 KB Output is correct
44 Correct 14 ms 10408 KB Output is correct
45 Correct 12 ms 10360 KB Output is correct