oj.uz

답안 #153496

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
153496 2019-09-14T11:13:45 Z brcode Palindrome-Free Numbers (BOI13_numbers) C++14
62.9167 / 100
 14 ms 10412 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, int 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 >= v1.size()-1){
        if(len == 3){

           
        }
        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);
                    dp[len][a][b][1][leading]%=MOD;

                }else{
                    //can do the same thing
                    dp[len][a][b][1][leading] += rec(len+1,b,i,0,0);
                    dp[len][a][b][1][leading]%=MOD;

                }
                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);
                    dp[len][a][b][1][leading]%=MOD;
                    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);
                    dp[len][a][b][1][leading]%=MOD;
                    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);
                    dp[len][a][b][1][leading]%=MOD;

                }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);
                    dp[len][a][b][1][leading]%=MOD;

                }
                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);
                    dp[len][a][b][1][leading]%=MOD;
                    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);
                    dp[len][a][b][1][leading]%=MOD;
                    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);
                dp[len][a][b][1][leading]%=MOD;

            }
            else if(i!=a && i!=b){
                dp[len][a][b][1][leading] += rec(len+1,b,i,0,0);
                dp[len][a][b][1][leading]%=MOD;

            }

        }
        dp[len][a][b][limit][leading]%=MOD;

        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);
                dp[len][a][b][limit][leading]%=MOD;
            }else if(leading ==3){
               
                if(i!=a && i!=b){

                    dp[len][a][b][limit][leading] += rec(len+1,b,i,limit,0);
                    dp[len][a][b][limit][leading]%=MOD;
                }
            }
            else if(leading && i==0){
                dp[len][a][b][limit][leading] += rec(len+1,b,i,limit,1);

                dp[len][a][b][limit][leading]%=MOD;
                continue;
            }else if(leading){
                dp[len][a][b][limit][leading] += rec(len+1,b,i,limit,3);

                dp[len][a][b][limit][leading]%=MOD;
                continue;
            }
            else if(i!=a && i!=b){
                dp[len][a][b][limit][leading] += rec(len+1,b,i,limit,0);
                dp[len][a][b][limit][leading]%=MOD;
            }

        }
        dp[len][a][b][limit][leading]%=MOD;
        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;
                    }
                }
            }
        }
    }
    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);
            ans%=MOD;
           // cout<<ans<<endl;
            continue;
        }

        ans+=rec(1,30,i,v1[1] == i,false);
        ans%=MOD;
        //cout<<ans<<endl;

    }
    return ans;
}
int main(){
     long long a,b;
    cin>>a>>b;
    cout<<solve(b)-solve(a-1)<<endl;

}

Compilation message

numbers.cpp: In function 'long long int rec(long long int, long long int, long long int, bool, int)':
numbers.cpp:15:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(len >= v1.size()-1){
        ~~~~^~~~~~~~~~~~~~

Subtask #1
21.25 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 10360 KB Output is correct
2 Correct 12 ms 10360 KB Output is correct
3 Correct 12 ms 10360 KB Output is correct
4 Correct 12 ms 10360 KB Output is correct
5 Incorrect 11 ms 10360 KB Output isn't correct
6 Incorrect 12 ms 10360 KB Output isn't correct
7 Correct 12 ms 10360 KB Output is correct
8 Correct 12 ms 10360 KB Output is correct
9 Correct 11 ms 10360 KB Output is correct
10 Correct 11 ms 10232 KB Output is correct
11 Correct 11 ms 10360 KB Output is correct
12 Correct 12 ms 10332 KB Output is correct
13 Correct 12 ms 10360 KB Output is correct
14 Correct 12 ms 10360 KB Output is correct
15 Incorrect 14 ms 10376 KB Output isn't correct
16 Correct 12 ms 10360 KB Output is correct
17 Correct 11 ms 10360 KB Output is correct
18 Correct 12 ms 10360 KB Output is correct
19 Correct 12 ms 10360 KB Output is correct
20 Correct 12 ms 10360 KB Output is correct

Subtask #2
41.6666666667 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 10360 KB Output is correct
2 Incorrect 12 ms 10352 KB Output isn't correct
3 Incorrect 12 ms 10276 KB Output isn't correct
4 Incorrect 12 ms 10360 KB Output isn't correct
5 Correct 12 ms 10360 KB Output is correct
6 Correct 12 ms 10360 KB Output is correct
7 Correct 12 ms 10360 KB Output is correct
8 Correct 12 ms 10360 KB Output is correct
9 Correct 12 ms 10360 KB Output is correct
10 Correct 11 ms 10360 KB Output is correct
11 Correct 12 ms 10360 KB Output is correct
12 Correct 12 ms 10360 KB Output is correct
13 Correct 12 ms 10360 KB Output is correct
14 Correct 14 ms 10360 KB Output is correct
15 Correct 14 ms 10360 KB Output is correct
16 Correct 12 ms 10360 KB Output is correct
17 Correct 13 ms 10360 KB Output is correct
18 Correct 12 ms 10360 KB Output is correct
19 Correct 12 ms 10360 KB Output is correct
20 Correct 12 ms 10360 KB Output is correct
21 Incorrect 11 ms 10360 KB Output isn't correct
22 Correct 12 ms 10360 KB Output is correct
23 Incorrect 12 ms 10360 KB Output isn't correct
24 Correct 13 ms 10332 KB Output is correct
25 Incorrect 12 ms 10412 KB Output isn't correct
26 Incorrect 12 ms 10332 KB Output isn't correct
27 Incorrect 12 ms 10360 KB Output isn't correct
28 Incorrect 14 ms 10360 KB Output isn't correct
29 Correct 13 ms 10360 KB Output is correct
30 Correct 12 ms 10360 KB Output is correct
31 Incorrect 12 ms 10276 KB Output isn't correct
32 Correct 12 ms 10360 KB Output is correct
33 Incorrect 12 ms 10360 KB Output isn't correct
34 Correct 12 ms 10360 KB Output is correct
35 Incorrect 12 ms 10360 KB Output isn't correct
36 Incorrect 14 ms 10360 KB Output isn't correct
37 Incorrect 14 ms 10360 KB Output isn't correct
38 Incorrect 13 ms 10360 KB Output isn't correct
39 Incorrect 12 ms 10360 KB Output isn't correct
40 Correct 12 ms 10264 KB Output is correct
41 Incorrect 12 ms 10360 KB Output isn't correct
42 Correct 14 ms 10364 KB Output is correct
43 Incorrect 12 ms 10360 KB Output isn't correct
44 Incorrect 13 ms 10360 KB Output isn't correct
45 Incorrect 12 ms 10360 KB Output isn't correct