À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 că ați ales să vizitați platforma noastră dedicată Informatică. Sperăm că informațiile disponibile v-au fost utile. Dacă aveți întrebări suplimentare sau aveți nevoie de sprijin, nu ezitați să ne contactați. Vă așteptăm cu drag și data viitoare! Nu uitați să adăugați site-ul nostru la favorite pentru acces rapid.