== include(page="template/taskheader" task_id="sir7") ==
Poveste și cerință...
Se dă un șir format din *n* numere naturale nenule. Elementele șirului sunt numerotate de la stânga la dreapta începând cu poziția 1.
h2. Cerință
Scrieți un program care să determine răspunsul pentru întrebări de următoarele tipuri:
# Care este cea mai din stânga poziție care conține o valoare strict mai mare decât toate cele din dreapta sa? - întrebare de tipul 1
# Care sunt pozițiile care conțin valori strict mai mari decât toate cele din stânga lor? - întrebare de tipul 2
# Dacă fiecărui element aflat între prima și ultima apariție a maximului i-am mări valoarea pentru a ajunge egal cu maximul, care este suma totală a valorilor adăugate? - întrebare de tipul 3
h2. Date de intrare
Fișierul de intrare $sir7.in$ ...
Fișierul de intrare $sir7.in$ conține pe prima linie un număr *C* (care poate fi 1, 2 sau 3), indicând tipul
întrebării. Pe linia a doua se află un număr natural *N*, reprezentând numărul de elemente din șir. Pe a
treia linie a fișierului de intrare se află *N* numere naturale, reprezentând elementele șirului, date de la
stânga la dreapta (cel mai din stânga are poziția 1 și cel mai din dreapta are poziția *N*). Numerele de
pe această linie sunt separate prin câte un spațiu.
h2. Date de ieșire
În fișierul de ieșire $sir7.out$ ...
Dacă *C* = 1, fișierul de ieșire $sir7.out$ trebuie să conțină un număr natural ce reprezintă răspunsul la o întrebare de tipul 1.
h2. Restricții
Dacă *C* = 2, fișierul de ieșire trebuie să conțină, separați prin câte un spațiu și în ordine crescătoare, indicii determinați ca răspuns la o întrebare de tipul 2.
* $... ≤ ... ≤ ...$
Dacă *C* = 3, fișierul de ieșire trebuie să conțină un număr ce reprezintă răspunsul la o întrebare de tipul 3.
h2. Exemplu
h2. Restricții și precizări
table(example).
|_. sir7.in |_. sir7.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
* 1 ≤ *C* ≤ 3.
* 1 ≤ *N* ≤ 100 000.
* Numerele din șirul dat sunt cuprinse între 1 și 10 000, inclusiv.
* Pentru teste în valoare de 24 de puncte avem *C* = 1.
* Pentru teste în valoare de 32 de puncte avem *C* = 2.
* Pentru teste în valoare de 44 de puncte avem *C* = 3.
h3. Explicație
h2. Exemple
...
table(example).
|_. sir7.in |_. sir7.out |_. Explicații |
| 1
7
3 2 2 5 3 5 4
| 6
| Cea mai din stânga poziție a unei valori care este mai mare decât toate cele din
dreapta sa este 6 (acolo unde se află valoarea 5)
|
| 2
7
3 2 2 5 3 5 4
| 1 4
| 1 și 4 sunt pozițiile unde se află valori mai mari decât toate cele din stânga lor.
|
| 3
8
3 2 2 5 3 1 5 4
| 6
| Maximul fiind 5, conform explicației de la întrebarea de tipul 3, trebuie mărite
două elemente pentru a ajunge egale cu 5. Acestea sunt cel aflat pe poziția 5 (de mărit cu 2)
precum și cel de pe poziția 6 (de mărit cu 4). Suma valorilor cu care avem de mărit este 2 + 4 = 6.
|
| 3
5
3 2 7 5 3
| 0
| maximul este 7 și apare o singură dată, deci nu se mai mărește nicio valoare.
|
== include(page="template/taskfooter" task_id="sir7") ==
