Question

PROBLEMA 2669 PBINFO - >
Imi puteti zice de ce nu functioneaza programul care l-am scris?Imi afiseaza 0 cand il rulez.

Cerința:
Se dă un vector cu n numere naturale. Să se determine câte dintre perechile de elemente din vector sunt formate din valori cu aceeași sumă a cifrelor.

Date de intrare:
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spaţii, reprezentând elementele vectorului.

Date de ieșire:
Programul afișează pe ecran numărul C, reprezentând valoarea cerută.

Restricții și precizări:
1 ≤ n ≤ 100.000
cele n numere citite vor fi mai mici decât 1.000.000.000

Exemplu:
Intrare:
6
51 842 15 28 77 132
Ieșire:
4

Explicație:
Perechile de elemente cu aceeaşi sumă cifrelor sunt:
51 15
51 132
842 77
15 132



Program:
#include

using namespace std;

int main()
{
int n;
cin>>n;
int a[n],fr[1001]={0},cifs=0,maxx=-1,b;
for(int i=1;i<=n;i++)
{
cin>>a[i];
while(a[i]=0)
{
cifs=a[i]%10+cifs;
a[i]=a[i]/10;
}
fr[cifs]++;
if(cifs>maxx)
maxx=cifs;
}
int t=0;
for(int i=1;i<=maxx;i++)
{
if(fr[i]>1)
t++;
}
cout< return 0;
}

Answer 1

Răspuns:

#include<iostream>

using namespace std;

int main()

{

   int n;

   cin >> n;

   int a[n], fr[1001] = {0}, cifs = 0, maxx = -1;

   for(int i = 1; i <= n; i++)

   {

       cin >> a[i];

       cifs = 0;

      while(a[i] != 0)

       {

           cifs = a[i] % 10 + cifs;

           a[i] = a[i] / 10;

       }

       fr[cifs]++;

 if(cifs > maxx)

  maxx = cifs;

   }

   int t = 0;

   for(int i = 1; i <= maxx; i++)

   {

       if(fr[i] > 1)

           t = t + fr[i] * (fr[i] - 1) / 2;

   }

   cout << t;

   return 0;

}

Explicație:

Ti-am ingrosat corecturile facute asupra codului tau. Le voi lua pe rand:

1. Dupa verificarea fiecarui numar, variabila cifs trebuie resetata la 0, altfel va continua sa adauge la suma de unde a ramas la precedentul, ceea ce este gresit pentru problema noastra.

2. while(a[i] = 0) ⇒ while(a[i] != 0). Cat timp elementul este diferit de 0, ii calculam suma cifrelor. Daca elementul este deja 0, nu avem ce suma a cifrelor sa calculam.

3. Cea mai importanta modificare adusa programului.
t++ ⇒ t = t + fr[i] * (fr[i] - 1) / 2
Aceasta se refera la numarul de perechi posibile de elemente din vectorul dat care au aceeasi suma a cifrelor.

Pentru a înțelege acest lucru, să presupunem că avem un anumit număr de elemente în vector care au aceeași sumă a cifrelor. Dacă avem, de exemplu, 3 elemente cu aceeași sumă a cifrelor, atunci există 3 combinații posibile de a alege o pereche din aceste elemente, și anume: prima cu a doua, prima cu a treia și a doua cu a treia.

Generalizand aceasta idee, daca avem x elemente in vector cu aceeasi suma a cifrelor, numarul de combinatii posibile de a alege o pereche este combinari de x luate cate 2, adica $\frac{x(x-1)}{2}$.

Prin urmare,  t = t + fr[i] * (fr[i] - 1) / 2 calculeaza numarul total de perechi posibile pentru fiecare suma de cifre care apare de cel putin doua ori in vector.

Programul dat este de 100 de puncte pe PBINFO.