Question

Buna ziua. Eu am rezolvat o problema de pe campion.edu.ro se numeste palindromuri. Cei care nau accoun aici este continutul problemei.... Eu am rezolvat-o dar problema e ca algoritmul folsit de mine este prea incet, am nevoie de unul mai bun, care lucreaza mai repede.


Gigel, un băiat foarte pasionat de puzzle-uri, a primit de ziua lui o cutie cu cifru, în interiorul căreia se află un cadou secret. Fiind curios din fire, el a tot încercat să descopere cifrul folosind fel de fel de combinaţii, însă niciuna nu s-a soldat cu succes. Aşadar s-a decis să citească cu atenţie instrucţiunile.
Astfel, Gigel a aflat că este o oarecare legătura între parola secretă şi palindromuri. El ştie că un palindrom este un număr ce se citeşte la fel, atât de la stânga la dreapta, cât şi de la dreapta la stânga. Gigel şi-a propus să încerce diverse strategii, însă a dedus că ar fi util mai întâi să afle câte palindroame se află într-un anumit interval [a, b] . Nefiind foarte bun la algoritmică, vă roagă pe voi să îl ajutaţi să răspundă eficient la această întrebare.

Cerinţă

Să se determine numărul de numere din intervalul [a, b] care au proprietatea de palindrom.

Date de intrare

Fişierul de intrare palindromuri.in conţine pe prima linie cele două numere naturale a şi respectiv b, reprezentând capetele intervalului de care este interesat Gigel.

Date de ieşire

Fişierul de ieşire palindromuri.out va trebui să conţină o singura linie pe care va fi scris numărul palindromurilor din intervalul [a, b].

Restricţii

1 <= a <= b <= 1018
20% dintre teste vor avea b-a < 106
30% dintre teste vor avea b-a < 1012

Exemple
palindromuri.in palindromuri.out
0 100 19

Explicatie
Palindromurile din intervalul dat sunt : 0 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99

Acesta este codul meu:

#include
#include
using namespace std;
unsigned long long int a,b,i,temp,r,sum,j=0;
int main()
{
ifstream fin("palindromuri.in");
ofstream fout("palindromuri.out");
fin>>a>>b;
for(i=a;i<=b;i++)
{
temp=i;
sum=0;
while(temp)
{
r=temp%10;
temp/=10;
sum=sum*10+r;
}
if(i==sum)j++;
}
fout< return 0;
}

Pueti folosi c++ sau c , de dorit c++ mersi mult!

Answer 1

Salut! Cunosc problema si am sa te ajut cu solutia oficiala. Succes!

#include <cstdlib>
#include <fstream>

using namespace std;

long long COUNT_FIXED_LEN[19];


void preprocess()
{
COUNT_FIXED_LEN[0] = 1;
COUNT_FIXED_LEN[1] = 9;
COUNT_FIXED_LEN[2] = 9;
for (int i = 3; i < 19; i++)
COUNT_FIXED_LEN[i] = 10 * COUNT_FIXED_LEN[i - 2];
}


long countLessThan(long long n)
{
long long p = 100000000000000000;
long long len = 18;
long long count = 0;
long long first, last, half, step;

if (n < 0)  return 0;
if (n == 0) return 1;

while (p > n)
{
p /= 10;
len--;
}

if (len == 1) return (n + 1);

first = n / p;
last  = n % 10;
if (first > last)
{
n -= (last + 1);
if (p > n)
{
p /= 10;
len--;
}
}

half = 0;
step = 0;
while (len >= 1)
{
first = n / p;
last  = n % 10;
if (first > last)
{
n    -= (last + 1);
first  = n / p;
}

half = (step == 0) ? (first - 1) : (half*10 + first);
n   = (n - first*p) / 10;
p   /= 100;
len -= 2;
step++;
}

len   = (len != 0) ? 2*(step - 1) : 2*step - 1;
count = half + 1;
for (int i = 0; i <= len; i++)
count += COUNT_FIXED_LEN[i];

return count;
}


int main()
{
fstream  f, g;
long long a, b;

f.open("palindromuri.in",  ios::in);
g.open("palindromuri.out", ios::out);

preprocess();

f >> a >> b;
g << countLessThan(b) - countLessThan(a - 1);

f.close();
g.close();

    return 0;
}