À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).
Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Sperăm că informațiile prezentate v-au fost utile. Dacă aveți întrebări suplimentare sau nevoie de ajutor, vă rugăm să ne contactați cu încredere. Așteptăm cu drag să reveniți și nu uitați să ne salvați în lista dumneavoastră de favorite!