25022023-01-14 16:02:22mraronSzivárványszámokcpp17Accepted 45/453ms4624 KiB
#include<bits/stdc++.h>
using namespace std;
using ll = long long ;

string s;
ll dp[100][2][2][10];
ll calc(int ind, bool less, bool mid, int dig) {
    if(ind==(int)s.size()) return 1;
    if(dp[ind][less][mid][dig]!=-1) return dp[ind][less][mid][dig];
    ll ans=0;
    for(int i=0;i<10;++i) {
        if(!mid && (less || i<=s[ind]-'0')) {
            ans+=calc(ind+1, less|(i<s[ind]-'0'), dig>i, i);
        }
        if(mid && (less || i<=s[ind]-'0') && dig>=i) {
            ans+=calc(ind+1, less|(i<s[ind]-'0'), mid, i);
        }
    }
    return dp[ind][less][mid][dig]=ans;
}

int main() {
    cin>>s;
    memset(dp, -1, sizeof dp);
    
    bool is=false;
    for(int i=0;!is&&i<(int)s.size();++i) {
        bool ok=true;
        for(int j=1;j<=i;j++) {
            ok&=s[j]>=s[j-1];
        }
        for(int j=i+1;j<(int)s.size();++j) {
            ok&=s[j]<=s[j-1];
        }
        is|=ok;
    }    

    cout<<calc(0, 0, 0, 0)-is<<"\n";
}
SubtaskSumTestVerdictTimeMemory
base45/45
1Accepted0/03ms1908 KiB
2Accepted0/02ms2112 KiB
3Accepted0/02ms2196 KiB
4Accepted1/12ms2320 KiB
5Accepted1/12ms2528 KiB
6Accepted1/12ms2732 KiB
7Accepted1/12ms2808 KiB
8Accepted1/12ms2928 KiB
9Accepted1/12ms3132 KiB
10Accepted1/12ms3216 KiB
11Accepted1/12ms3340 KiB
12Accepted1/12ms3544 KiB
13Accepted2/22ms3748 KiB
14Accepted2/22ms3716 KiB
15Accepted2/22ms3852 KiB
16Accepted2/22ms3928 KiB
17Accepted1/12ms4048 KiB
18Accepted2/22ms4128 KiB
19Accepted2/22ms4124 KiB
20Accepted2/22ms4128 KiB
21Accepted3/32ms4344 KiB
22Accepted2/22ms4224 KiB
23Accepted2/22ms4356 KiB
24Accepted2/22ms4436 KiB
25Accepted2/22ms4512 KiB
26Accepted2/22ms4516 KiB
27Accepted2/22ms4492 KiB
28Accepted2/22ms4496 KiB
29Accepted2/22ms4412 KiB
30Accepted2/22ms4624 KiB