👤
ANAMARIAANY45P9YA3WID
a fost răspuns

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

Răspuns :

CINEVAFARANUMEID

#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;

}

Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Sperăm că informațiile oferite v-au fost de ajutor. Nu ezitați să ne contactați pentru orice întrebare sau dacă aveți nevoie de asistență suplimentară. Vă așteptăm cu drag data viitoare și nu uitați să ne adăugați la favorite!


ID Learners: Alte intrebari