236892026-01-27 17:35:31abcdSzivárványszámokpython3Runtime error 0/4517ms3124 KiB
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

const int maxn=76;
ll dp[maxn][10][2][2];
string s;
int n;

ll cnt(int pos,int dig,bool tight,bool up){
    if(pos==n)return 1;
    if(dp[pos][dig][tight][up]!=-1)return dp[pos][dig][tight][up];
    ll res=0;
    int lim=tight?s[pos]-'0':9;
    for(int i=0;i<=lim;i++){
        if(i==dig)res+=cnt(pos+1,i,tight&&i==lim,up);
        if(i>dig&&up)res+=cnt(pos+1,i,tight&&i==lim,true);
        if(i>dig&&!up)continue;
        if(i<dig)res+=cnt(pos+1,i,tight&&i==lim,false);
    }
    return dp[pos][dig][tight][up]=res;
}

int main(){
    cin>>s;
    n=s.size();
    memset(dp,-1,sizeof(dp));
    bool yes=true,up=true;;
    int prev=s[0]-'0';
    for(int i=1;i<n;i++){
        int x=s[i]-'0';
        if(x>prev&&!up)yes=false;
        if(x<prev)up=false;
    }
    cout<<cnt(0,0,true,true)-yes<<'\n';
}
SubtaskSumTestVerdictTimeMemory
base0/45
1Runtime error0/014ms2876 KiB
2Runtime error0/016ms2868 KiB
3Runtime error0/016ms2856 KiB
4Runtime error0/116ms2868 KiB
5Runtime error0/114ms2820 KiB
6Runtime error0/116ms2976 KiB
7Runtime error0/114ms2940 KiB
8Runtime error0/116ms3008 KiB
9Runtime error0/116ms2868 KiB
10Runtime error0/117ms2940 KiB
11Runtime error0/116ms3092 KiB
12Runtime error0/116ms3064 KiB
13Runtime error0/216ms2980 KiB
14Runtime error0/216ms2980 KiB
15Runtime error0/216ms2884 KiB
16Runtime error0/214ms3032 KiB
17Runtime error0/116ms3056 KiB
18Runtime error0/216ms2868 KiB
19Runtime error0/216ms2972 KiB
20Runtime error0/216ms2868 KiB
21Runtime error0/316ms2932 KiB
22Runtime error0/216ms3044 KiB
23Runtime error0/214ms2872 KiB
24Runtime error0/216ms2868 KiB
25Runtime error0/216ms3064 KiB
26Runtime error0/216ms2972 KiB
27Runtime error0/216ms3124 KiB
28Runtime error0/216ms2880 KiB
29Runtime error0/214ms2868 KiB
30Runtime error0/216ms3064 KiB