Cod sursa(job #2632309)

Utilizator AokijiAlex M Aokiji Data 2 iulie 2020 19:00:08
Problema Cifre Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;


ifstream fin("cifre.in");
ofstream fout("cifre.out");

const int N=100;
int comb[N][N];

int expow(int a,int b) {
    if(b<0) {
        return 0;
    }
    int ans=1;
    while(b>0) {
        if(b%2==1) {
            ans*=a;
        }
        a*=a;
        b/=2;
    }
    return ans;
}

int prefix(int val,int cif,int k) {
    if(val<0) {
        return 0;
    }
    if(val==0) {
        if(cif==0 && k==1) {
            return 1;
        }
        return 0;
    }
    int v[15],n=0;
    while(val>0) {
        v[++n]=val%10;
        val/=10;
    }
    reverse(v+1,v+n+1);
    /// mai putine cifre
    int ans=0;
    if(cif==0 && k==1) {
        ans++;
    }
    for(int l=k;l<n;l++) {
        if(l==k) {
            if(cif>0) {
                ans++;
            }
            continue;
        }
        int nev;
        for(int p=1;p<=9;p++) {
            nev=k-(p==cif);
            ans+=comb[l-1][nev]*expow(10,l-1-nev);
        }
    }
    /// = cifre
    int cur=0;
    for(int p=0;p<=n;p++) {
        if(p && v[p]==cif) {
            cur++;
        }
        if(p==n) {
            if(cur>=k) {
                ans++;
            }
            break;
        }
        int st=0;
        if(p==0) {
            st=1;
        }
        for(int val=st;val<v[p+1];val++) {
            int nev=max(0,k-cur-(val==cif));
            int lft=n-p-1;
            ans+=comb[lft][nev]*expow(10,lft-nev);
        }
    }
    return ans;
}

int main() {
    for(int i=0;i<N;i++) {
        comb[i][0]=1;
        for(int j=1;j<=i;j++) {
            comb[i][j]=comb[i-1][j]+comb[i-1][j-1];
        }
    }
    int st,dr;
    fin>>st>>dr;
    int a,b;
    fin>>a>>b;
    int ans=prefix(dr,a,b)-prefix(st-1,a,b);
    int cnt=dr-st+1;
    double sol=(double)ans/cnt;
    fout<<fixed<<setprecision(6)<<sol<<"\n";
    return 0;
}