Cod sursa(job #88369)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 1 octombrie 2007 21:15:20
Problema Cifre Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <stdio.h>

long A,B,C,K,i;
long aux,mm,l,p,q,sol,sol2;
long v[11],nrc,next,cont,x[11];

int main(){
    freopen("cifre.in","r",stdin);
    freopen("cifre.out","w",stdout);
    
    scanf ("%ld %ld %ld %ld",&A,&B,&C,&K);
    A--;
    //calculam pt sirul 1......A-1;
    l=1;
    i=10;
    while (A>i){
          l++;
          i*=10;
    }
    aux=A;
    q=0;
    while (aux){
        q++;
        v[q]=aux%10;
        aux/=10;
    }
    
    while (cont<(1<<l)){
          nrc=0;mm=0;p=0;
          for (i=0;i<l;i++)
              if ((long)cont&(1<<i))nrc++;
          if (nrc>=K){
             next=0;
             for (i=l;i>0;i--){
                 if (cont&(1<<(i-1))){
                    if (mm==0){
                       if (C>v[i])
                          if (p==0){next=1;break;}
                          else {x[p]--;mm=-1;}
                    }
                    if (C<v[i])mm=-1;
                 }
                 else{
                      if(mm==0){p++;x[p]=v[i];}
                      else{p++;v[p]=9;}
                 }
             }
             if (next){cont++;continue;}
             if (p)x[0]=1;
             else x[0]=0;
             for (i=p;i>0;i--){
                 if (x[i]>=C)x[i]--;
                 x[0]*=(x[i]+1);
             }
            // printf("%ld\n",x[0]);
             sol+=x[0];
          }
          cont++;
    }
    x[0]=C;
    for (i=1;i<l;i++)
        x[0]=x[0]*10+C;
    if (x[0]<=A)sol++;
    
    //calculam pentru sirul 1........B
    l=1;
    i=10;
    cont=0;
    while (B>i){
          l++;
          i*=10;
    }
    aux=B;
    q=0;
    while (aux){
        q++;
        v[q]=aux%10;
        aux/=10;
    }
    
    while (cont<(1<<l)){
          nrc=0;mm=0;p=0;
          for (i=0;i<l;i++)
              if ((long)cont&(1<<i))nrc++;
          if (nrc>=K){
             next=0;
             for (i=l;i>0;i--){
                 if (cont&(1<<(i-1))){
                    if (mm==0){
                       if (C>v[i])
                          if (p==0){next=1;break;}
                          else {x[p]--;mm=-1;}
                       if (C<v[i])mm=-1;
                    }
                 }
                 else{
                      if(mm==0){p++;x[p]=v[i];}
                      else{p++;x[p]=9;}
                 }
             }
             if (next){cont++;continue;}
             if (p)x[0]=1;
             else x[0]=0;
             for (i=p;i>0;i--){
                 if (x[i]>=C)x[i]--;
                 x[0]*=(x[i]+1);
             }
             //printf("%ld\n",x[0]);
             sol2+=x[0];
          }
          cont++;
    }
    x[0]=C;
    for (i=1;i<l;i++)
        x[0]=x[0]*10+C;
    if (x[0]<=B)sol2++;
    //printf("%ld\n",sol2-sol);
    printf("%.4lf\n",(double)(sol2-sol)/(B-A));

return 0;
}