Question

Cerința
Se dau n întrebări de forma: Câte palindroame 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

Answer 1

#include <stdio.h>

#include <stdlib.h>

static int numPalindrome(int num);

static int constructPalindrome(int palPrefix, int numLength);

int main(void)

{

   FILE* fin = fopen("nr_pal.in", "r");

   FILE* fout = fopen("nr_pal.out", "w");

   int a = 0;

   int b = 0;

   int n = 0;

   fscanf(fin, "%d", &n);

   while (n-- > 0) {

       fscanf(fin, "%d %d", &a, &b);

       fprintf(fout, "%d\n", numPalindrome(b) - numPalindrome(a-1));

   }

   fclose(fin);

   fclose(fout);

   return 0;

}

static int numPalindrome(int num)

{

   int numLength  = 0;

   int palLength  = 0;

   int palPrefix  = 0;

   int temp       = 0;

   register int i = 0;

   for (numLength=0, temp = num; temp != 0; temp /= 10)

       numLength++;

   

   palLength = (numLength+1) / 2;

   palPrefix = num;

   for (i=0; i < numLength - palLength; i++)

       palPrefix /= 10;

   

   if (constructPalindrome(palPrefix, numLength) > num)

       palPrefix--;

   

   palPrefix *= 2;

   if (numLength & 1) {

       int adjustment = 1;

       for (i=1;i<palLength;i++)

           adjustment *= 10;

       palPrefix -= (palPrefix/2 - adjustment + 1);

   } else {

       int adjustment = 1;

       for (i=0;i<palLength;i++)

           adjustment *= 10;

       palPrefix += (adjustment - 1 - palPrefix/2);

   }

   return palPrefix;

}

static int constructPalindrome(int palPrefix, int numLength)

{

   int front = palPrefix;

   int back  = 0;

   if (numLength & 1)

       palPrefix /= 10;

   while (palPrefix != 0) {

       int digit = palPrefix % 10;

       palPrefix /= 10;

       back       = back * 10 + digit;

       front     *= 10;

   }

   return front + back;

}