== include(page="template/taskheader" task_id="taietura") ==
Poveste şi cerinţă...
Fiind dat un şir V format din N numere întregi V{~1~}, … , V{~N~}, definim o tăietură în poziţia pos ca fiind o subsecvenţă care conţine elementul de pe poziţia $pos$. Formal, tăieturile în poziţia pos sunt de forma V{~k~} , V{~k+1~}, ... , V{~pos~} , ... , V{~r-1~}, V{~r~} pentru orice $k, 1 ≤ k ≤ pos$ şi orice $r, pos ≤ r ≤ N$. Valoarea unei tăieturi este suma tuturor elementelor care fac parte din tăietura respectivă. Definim funcţia $MulT(pos)$ ca fiind numărul de tăieturi în poziţia pos care au valoarea $0$.
h2. Cerinţă
Ioana, fiind foarte curioasă din fire, dar şi foarte fascinată de această funcţie numită $MulT$, este foarte interesată în a afla rezultatul pentru $MulT (i)$, unde $1 ≤ i ≤ N$.
h2. Date de intrare
Fişierul de intrare $taietura.in$ ...
Fişierul de intrare $taietura.in$ conţine pe prima linie un număr natural $N$, reprezentând numărul de elemente din şirul $V$. Următoarea linie va conţine exact N valori întregi despărţite prin câte un spaţiu, şi anume elementele şirului $V$.
h2. Date de ieşire
În fişierul de ieşire $taietura.out$ ...
Fişierul de ieşire $taietura.out$ va conţine pe prima linie $N$ numere naturale separate prin câte un spaţiu, şi anume valorile funcţiei $MulT (i)$, unde $1 ≤ i ≤ N$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100 000$
* $Orice element al şirului V este mai mic sau egal în valoare absolută cu 1.000.000.000$
* $Pentru teste în valoare de 20 de puncte N ≤ 100$
* $Pentru teste în valoare de încă 20 de puncte N ≤ 1000$
h2. Exemplu
table(example). |_. taietura.in |_. taietura.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
table(example). |_. taietura.in |_. taietura.out |_. Explicaţie |
|3
0 1 0
| 1 0 1
|Rezultatul pentru MulT(1) este 1 deoarece există o singură
tăietură, şi anume (0) care are valoarea 0. Pentru MulT(2) rezultatul este 0 deoarece nu există nicio tăietură aplicată pe
poziţia 2 care să aibă valoarea 0.
Rezultatul pentru MulT(3) este 1 deoarece există o unică tăietură, si anume (0) care are valoarea 0.
|
|6
2 -2 0 0 1 -1
|4 4 6 6 4 4
|De exemplu, rezultatul pentru MulT(2) este 4 deoarece tăieturile
formate din subsecvenţele (2, -2), (2, -2, 0), (2, -2, 0, 0), (2, -2, 0, 0, 1, -1) au valoarea 0.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="taietura") ==
