2502 2023. 01. 14 16:02:22 mraron Szivárványszámok cpp17 Elfogadva 45/45 3ms 4624 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 Összpont Teszt Verdikt Idő Memória
base 45/45
1 Elfogadva 0/0 3ms 1908 KiB
2 Elfogadva 0/0 2ms 2112 KiB
3 Elfogadva 0/0 2ms 2196 KiB
4 Elfogadva 1/1 2ms 2320 KiB
5 Elfogadva 1/1 2ms 2528 KiB
6 Elfogadva 1/1 2ms 2732 KiB
7 Elfogadva 1/1 2ms 2808 KiB
8 Elfogadva 1/1 2ms 2928 KiB
9 Elfogadva 1/1 2ms 3132 KiB
10 Elfogadva 1/1 2ms 3216 KiB
11 Elfogadva 1/1 2ms 3340 KiB
12 Elfogadva 1/1 2ms 3544 KiB
13 Elfogadva 2/2 2ms 3748 KiB
14 Elfogadva 2/2 2ms 3716 KiB
15 Elfogadva 2/2 2ms 3852 KiB
16 Elfogadva 2/2 2ms 3928 KiB
17 Elfogadva 1/1 2ms 4048 KiB
18 Elfogadva 2/2 2ms 4128 KiB
19 Elfogadva 2/2 2ms 4124 KiB
20 Elfogadva 2/2 2ms 4128 KiB
21 Elfogadva 3/3 2ms 4344 KiB
22 Elfogadva 2/2 2ms 4224 KiB
23 Elfogadva 2/2 2ms 4356 KiB
24 Elfogadva 2/2 2ms 4436 KiB
25 Elfogadva 2/2 2ms 4512 KiB
26 Elfogadva 2/2 2ms 4516 KiB
27 Elfogadva 2/2 2ms 4492 KiB
28 Elfogadva 2/2 2ms 4496 KiB
29 Elfogadva 2/2 2ms 4412 KiB
30 Elfogadva 2/2 2ms 4624 KiB