VREAU REZOLVAREA DE 100P,O AM DE 60P PE LIMITA DE TIMP DEPASITA
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
Răspunsuri la întrebare
Răspuns:
#include <iostream>
using namespace std;
int n,i,v[100], num, sc, perechi;
int main()
{
cin >> n;
for (i=1; i<=n; ++i)
{
cin >>num;
sc=0;
while (num)
{
sc=sc+num%10;
num/=10;
}
++v[sc];
}
for (i=0; i<82; ++i)
{
for (int j=1; j<v[i]; ++j)
{
for (int t=j+1; t<=v[i]; ++t)
++perechi;
}
}
cout << perechi;
}
Explicație:
e de 100. ultimele cicluri numără perechile. De exemplu în vectorul frecvenţă avem v[5]=4, adică sunt 4 numere în şir cu suma cifrelor egală cu 5. Pentru a număra perechile considerăm că acele 4 numere sunt a,b,c,d.
Atunci perechile sunt (a,b), (a,c), (a,d), (b,c), (b.d), (c,d). Am putea calcula perechile ;i ca combinari din 4 luate c\te 2, dar eu am preferat ciclurile.. succese!