Rezolvare PBinfo #4084

À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