#include <iostream>
#include <cmath>
#include <time.h>
using namespace std;
int nr_cifre(int n){
int nr=0;
while(n>0){
nr++;
n=n/10;
}
return nr;
}
double s=0;
double suma_cifre(int n){
int i,d,p,c,k=0;
if(n<10){
return n*(n+1)/2;
}
//numarul d reprezinta nr cifre-1, adica intervalul acela 1-999
d=nr_cifre(n)-1;
int a[12];
a[0]=0;
a[1]=45;
for(i=2;i<=d;i++){
a[i]=a[i-1]*10+45*ceil(pow(10,i-1));
}
p=ceil(pow(10,d));
//c este prima cifra din sir
c=n/p;
return c*a[d]+p*(c-1)*c/2+c*(1+n%p)+suma_cifre(n%p);
}
//-----------------------------------------------
int suma_cifre_nr(int n){
double s=0;
while(n>0){
s=s+n%10;
n=n/10;
}
return s;
}
//metoda de calcul brut clasica
double suma_cifre_calc_brut(int n){
int i;
double suma=0;
for(i=1;i<=n;i++){
suma=suma+suma_cifre_nr(i);
}
return suma;
}
int main(){
int n;
double time1,time2;
cin>>n;
clock_t start=clock();
cout<<"Suma cifre: "<<suma_cifre(n)<<endl;
clock_t end=clock();
time1=((double)(end-start)/CLOCKS_PER_SEC)*100000;
start=clock();
cout<<"Suma cifre brut: "<<suma_cifre_calc_brut(n)<<endl;
end=clock();
time2=((double)(end-start)/CLOCKS_PER_SEC)*100000;
cout<<"Timp 1: "<<time1<<" Time 2: "<<time2<<endl;
cout<<"Algoritmul 1 este de "<<time2/time1<<" mai rapid decat algoritm brut";
return 0;
}
