237042026-01-27 18:58:19abcdSzivárványszámokpython3Runtime error 0/4517ms3228 KiB
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

const int maxn=80;
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/016ms3116 KiB
2Runtime error0/016ms2868 KiB
3Runtime error0/014ms2868 KiB
4Runtime error0/116ms3040 KiB
5Runtime error0/116ms2980 KiB
6Runtime error0/114ms2868 KiB
7Runtime error0/116ms3068 KiB
8Runtime error0/114ms2868 KiB
9Runtime error0/116ms2968 KiB
10Runtime error0/116ms2984 KiB
11Runtime error0/114ms2852 KiB
12Runtime error0/114ms2960 KiB
13Runtime error0/217ms2940 KiB
14Runtime error0/216ms2964 KiB
15Runtime error0/217ms2860 KiB
16Runtime error0/217ms2880 KiB
17Runtime error0/116ms3100 KiB
18Runtime error0/214ms2872 KiB
19Runtime error0/216ms3224 KiB
20Runtime error0/216ms3036 KiB
21Runtime error0/316ms2948 KiB
22Runtime error0/214ms2948 KiB
23Runtime error0/216ms3040 KiB
24Runtime error0/216ms3056 KiB
25Runtime error0/216ms3052 KiB
26Runtime error0/214ms3228 KiB
27Runtime error0/216ms2876 KiB
28Runtime error0/216ms3064 KiB
29Runtime error0/216ms2868 KiB
30Runtime error0/214ms2928 KiB