Cerința

Se dau n întrebări de forma: Câte palindromuri există în intervalul [a, b]?, unde a și b sunt numere naturale date, cu a ≤ b.

Date de intrare

Fișierul de intrare nr_pal.in conține pe prima linie numărul natural nenul n, iar pe următoarele n linii, n perechii de forma a b ce reprezintă capetele intervalelor.

Date de ieșire

Fișierul de ieșire nr_pal.out va conține răspunsurile la cele n întrebări, fiecare pe câte un rând.

Restricții și precizări

0 < n ≤ 100.000
0 ≤ a ≤ b ≤ 1.000.000.000

Exemplu

nr_pal.in

2
5 23
1 255

nr_pal.out

7
34

Explicație

La prima întrebare în intervalul [5,23] exista 7 palindromuri: 5,6,7,8,9,11,22.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema nr_pal:

/// Vlad Tir, Colegiul National "Tudor Vladimirescu", Targu-Jiu
#include <cstdio>
/// Functie ce returneaza numarul de cifre ale lui x
int nr_cifre(int x){
    int ct=0;
    if(x==0) return 1;
    while(x>0){
        ++ct;
        x/=10;
    }
    return ct;
}
/// Functie ce returneaza a^b
int pow(int a,int b){
    int P=1;
    for(int i=1;i<=b;++i)
        P*=a;
    return P;
}
/// Functie ce returneaza oglinditul lui x
int rev(int x){
    int ans=0;
    while(x>0){
        ans=ans*10+(x%10);
        x/=10;
    }
    return ans;
}
int nr_pal(int n){
    if(n==-1) return 0;
    int cif=nr_cifre(n),ans=1;
    /// Daca n are numar impar de cifre
    if(cif%2==1){
        ans+=2*(pow(10,cif/2)-1);
        /// Palindromul de cif cifre format din primele cif/2+1 cifre ale lui n
        int pal=n/pow(10,cif/2)*pow(10,cif/2)+rev(n/pow(10,cif/2+1));
        /// Daca n este mai mare decat pal,avem o solutie in plus
        if(n>=pal) ans+=n/pow(10,cif/2)-pow(10,cif/2)+1;
        else ans+=n/pow(10,cif/2)-pow(10,cif/2);
    }
    /// Daca n are numar par de cifre
    else{
        ans+=2*(pow(10,(cif-1)/2)-1)+9*pow(10,(cif-1)/2);
        /// Palindromul de cif cifre format din primele cif/2 cifre ale lui n
        int pal=n/pow(10,cif/2)*pow(10,cif/2)+rev(n/pow(10,cif/2));
        /// Daca n este mai mare decat pal,avem o solutie in plus
        if(n>=pal) ans+=n/pow(10,cif/2)-pow(10,cif/2-1)+1;
        else ans+=n/pow(10,cif/2)-pow(10,cif/2-1);
    }
    return ans;
}
int main(){
    int n;
    freopen("nr_pal.in","r",stdin);
    freopen("nr_pal.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int a,b;
        scanf("%d %d",&a,&b);
        printf("%d\n",nr_pal(b)-nr_pal(a-1) );
    }
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2415 nr_pal

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2415 nr_pal de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2415 nr_pal