== include(page="template/taskheader" task_id="pseudocmp") ==
Poveste și cerință...
À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.
h2. Cerințe
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ă.
h2. Date de intrare
Fișierul de intrare $pseudocmp.in$ ...
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.
h2. Date de ieșire
În fișierul de ieșire $pseudocmp.out$ ...
Pe prima linie a fișierului $pseudocmp.out$:
h2. Restricții
# 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.
* $... ≤ ... ≤ ...$
h2. Restricții
h2. Exemplu
* 1 ≤ *N* ≤ 100 000
* 1 ≤ *A[~i~]* ≤ 1 000 000, pentru 1 ≤ i ≤ *N*
table(example).
|_. pseudocmp.in |_. pseudocmp.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|_. # |_. Punctaj |_. Restricții |
| 1
| 15
| *T* = 1, *N* ≤ 1000
|
| 2
| 25
| *T* = 1, 1000 < *N*
|
| 3
| 25
| *T* = 2, *N* ≤ 1000
|
| 4
| 35
| *T* = 2, 1000 < *N*
|
h3. Explicație
h2. Exemplu
...
table(example).
|_. pseudocmp.in |_. pseudocmp.out |_. Explicații |
| 1 6
213 123 523 51 99 92
| 99 123
| 99 este mai mic decât 123 iar suma
cifrelor lui 99 este 18, suma
cifrelor lui 123 este 6, 18 > 6
|
| 2 6
213 123 523 51 99 92
| 6
| Cele 6 perechi de indici sunt
următoarele:
(5, 1)
(5, 2)
(5, 3)
(6, 1)
(6, 2)
(6, 3)
|
| 1 5
6 5 2 1 3
| -1
|
|
== include(page="template/taskfooter" task_id="pseudocmp") ==
