Question

Numerele naturale nenule se scriu într-un şir astfel: 12345678910111213141516.... Fiind date n perechi de poziţii din şir de forma (p,q), cu p≤q, să se calculeze suma cifrelor din şir situate pe poziţiile de la p la q.

Date de intrare
Fișierul de intrare sumo.in conține pe prima linie numărul n, iar pe următoarele n linii câte o pereche de numere naturale (p,q), numere naturale separate prin spații.

Date de ieșire
Fișierul de ieșire sumo.out va conține pe fiecare linie de la 1 la n câte un număr reprezentând suma cifrelor din şir corespunzătoare fiecărei perechi (p,q) din fişierul de intrare.

Restricții și precizări
1 ≤ n ≤ 100.000
1 ≤ p ≤ q ≤ 2.000.000.000



Exemplu
sumo.in

3
1 5
7 18
22 26
sumo.out

15
35
16
Explicație
De la poziţia 1 la 5 avem cifrele 12345 iar suma lor este 15, de la poziţia 7 la 18 avem cifrele 789101112131 iar suma lor este 35, iar de la poziţia 22 la 26 avem cifrele 16171 iar suma lor este 16.
Exemplul 2
sumo.in
20
26 79
50 150
44 77
46 94
44 71
43 98
7 130
37 141
21 89
49 151
8 95
36 138
23 71
49 63
32 105
14 138
35 101
28 75
34 118
21 86

sumo.out
189
483
127
197
109
227
511
471
264
492
315
457
177
51
291
518
263
165
351
243

Answer 1

#include <iostream>
#include <fstream>
using namespace std;

struct numar_prop{
int numar_curent;
int pozitie_curenta;
int nr_cifre;
};


struct numar_prop cifra_curenta(int n){
struct numar_prop np;
int rez=0,nr_cifre=1,nr_numere=9;
while(n>=nr_numere*nr_cifre){
n=n-nr_numere*nr_cifre;
rez=rez+nr_numere;
nr_numere=nr_numere*10;
nr_cifre++;
}
np.numar_curent=n/nr_cifre;
np.pozitie_curenta=n%nr_cifre;
if(np.pozitie_curenta==0){
np.pozitie_curenta=nr_cifre;
}
else{
np.numar_curent++;
}
np.numar_curent=np.numar_curent+rez;
np.nr_cifre=nr_cifre;
return np;

}

int obtine_nr_cifre(int n){
int nr_cifre=0;;
while(n>0){
n=n/10;
nr_cifre++;
}
return nr_cifre;
}
//poz este pozitia de la care incepe suma de cifre
//este numerotata de la 1 la nr_cifre
//dir da directia de adunare a cifrelor: dir=0, dreapta stanga, dir=1, stanga dreapta
int suma_cifre(int n,int nr_cifre,int poz,int dir){
int s=0,poz_ocupate=0;
if(dir==0){
while(poz_ocupate<nr_cifre-poz+1){
s=s+n%10;
n=n/10;
poz_ocupate++;
}
}
else{
while(n>0){
if(poz_ocupate>nr_cifre-poz-1){
s=s+n%10;
}
n=n/10;
poz_ocupate++;
}
}

return s;
}
int suma_cifre_interval(int p,int q){
struct numar_prop np_p,np_q;
int i,s=0;
np_p=cifra_curenta(p);
np_q=cifra_curenta(q);
s=s+suma_cifre(np_p.numar_curent,np_p.nr_cifre,np_p.pozitie_curenta,0);

for(i=np_p.numar_curent+1;i<np_q.numar_curent;i++){
s=s+suma_cifre(i,obtine_nr_cifre(i),1,0);
}
s=s+suma_cifre(np_q.numar_curent,np_q.nr_cifre,np_q.pozitie_curenta,1);
return s;
}
int main(){    
    int n,i; 
    ifstream fis("sumo.in");
    ofstream fos("sumo.out");
fis>>n;
    int p[n],q[n];
for(i=0;i<n;i++){
     fis>>p[i]>>q[i];
     fos<<suma_cifre_interval(p[i],q[i])<<endl;
}
 
return 0;
}