# PBinfo #4084 – pseudocmp – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Àles a primit ca temă următoarea problemă: “Fiind dat un șir A cu N numere naturale distincte, să se calculeze suma cifrelor fiecărui element al șirului”.

După ce și-a terminat tema, acesta observă că sunt mai multe perechi de indici (i, j) pentru care dacă A[i] < A[j] atunci S[i] > S[j], unde S[i] reprezintă suma cifrelor lui A[i]. El le va numi pe acestea perechi speciale de indici. 

Cerința
Terminând prea repede tema, Àles primește o temă suplimentară cu două cerințe:


Determină două numere aflate în șirul A, pentru care indicii corespunzători formează o pereche specială.
Câte perechi speciale de indici (i, j) se găsesc în şirul A?

Ajutați-l pe Àles să rezolve tema suplimentară.

Date de intrare
Pe prima linie a fișierului pseudocmp.in se găsesc două numere naturale: T și N. Pe următoarea linie se găsesc N numere naturale, separate printr-un spațiu, reprezentând valorile din șirul A. Numărul T reprezintă numărul cerinței.

Date de ieșire
Pe prima linie a fișierului pseudocmp.out:


Dacă T = 1, se găsesc două numere naturale x, y, cu x < y, separate printr-un spațiu, reprezentând răspunsul pentru cerința 1 dacă există soluție sau -1, dacă nu există soluție. Dacă există mai multe soluții, se acceptă oricare dintre acestea.
Dacă  T = 2, se găsește un singur număr natural, reprezentând răspunsul la cerința 2.

Restricții și precizări

1 ≤ N ≤ 100.000
1 ≤ A[i] ≤ 1.000.000, pentru 1 ≤ i ≤ N
Pentru 15 puncte, T = 1, N ≤ 1000
Pentru 25 puncte, T = 1, 1000 < N
Pentru 25 puncte, T = 2, N ≤ 1000
Pentru 35 puncte, T = 2, 1000 < N

Exemplul 1:
pseudocmp.in

1 6
213 123 523 51 99 92
pseudocmp.out

99 123
Explicație
99 este mai mic decât 123 iar suma cifrelor lui 99 este 18, suma cifrelor lui 123 este 6, 18 > 6.

Exemplul 2:
pseudocmp.in

2 6
213 123 523 51 99 92
pseudocmp.out

6
Explicație
Cele 6 perechi de indici sunt următoarele: (5, 1), (5, 2), (5, 3), (6, 1), (6, 2), (6, 3).

Exemplul 3:
pseudocmp.in

1 5
6 5 2 1 3
pseudocmp.out

-1

## Cod sursă C++

```cpp
/**
Autor: Bogdan-Ioan Popa, FMI Universitatea din Bucuresti
Scor: 100p
**/
#include <bits/stdc++.h>
#define N_MAX 100000
#define V_MAX 1000000
using namespace std;
ifstream fin("pseudocmp.in");
ofstream fout("pseudocmp.out");
int P, N;
int A[N_MAX + 5];
int freq[V_MAX + 5];
int dig_sum(int x) {
    int ret = 0;
    while(x) {
        ret += x % 10;
        x /= 10;
    }
    return ret;
}
int main()
{
    fin >> P >> N;
    for(int i = 1; i <= N; i++) {
        fin >> A[i];
        freq[A[i]]++;
    }
    int L = 0;
    for(int i = 1; i <= V_MAX; i++) {
        while(freq[i]--) {
            A[++L] = i;
        }
        freq[i] = 0;
    }
    if(P == 1) {
        for(int i = 2; i <= N; i++) {
            if(dig_sum(A[i - 1]) > dig_sum(A[i])) {
                fout << A[i - 1] << " " << A[i] << "\n";
                return 0;
            }
        }
        fout << "-1\n";
        return 0;
    }
    if(P == 2) {
        long long ans = 0;
        for(int i = 1; i <= N; i++) {
            int sum = dig_sum(A[i]);
            for(int j = sum + 1; j <= 54; j++) {
                ans += freq[j];
            }
            freq[sum]++;
        }
        fout << ans << "\n";
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4084)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4084/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4084/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)