25022023-01-14 16:02:22mraronSzivárványszámokcpp17Elfogadva 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";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base45/45
1Elfogadva0/03ms1908 KiB
2Elfogadva0/02ms2112 KiB
3Elfogadva0/02ms2196 KiB
4Elfogadva1/12ms2320 KiB
5Elfogadva1/12ms2528 KiB
6Elfogadva1/12ms2732 KiB
7Elfogadva1/12ms2808 KiB
8Elfogadva1/12ms2928 KiB
9Elfogadva1/12ms3132 KiB
10Elfogadva1/12ms3216 KiB
11Elfogadva1/12ms3340 KiB
12Elfogadva1/12ms3544 KiB
13Elfogadva2/22ms3748 KiB
14Elfogadva2/22ms3716 KiB
15Elfogadva2/22ms3852 KiB
16Elfogadva2/22ms3928 KiB
17Elfogadva1/12ms4048 KiB
18Elfogadva2/22ms4128 KiB
19Elfogadva2/22ms4124 KiB
20Elfogadva2/22ms4128 KiB
21Elfogadva3/32ms4344 KiB
22Elfogadva2/22ms4224 KiB
23Elfogadva2/22ms4356 KiB
24Elfogadva2/22ms4436 KiB
25Elfogadva2/22ms4512 KiB
26Elfogadva2/22ms4516 KiB
27Elfogadva2/22ms4492 KiB
28Elfogadva2/22ms4496 KiB
29Elfogadva2/22ms4412 KiB
30Elfogadva2/22ms4624 KiB