Fișierul intrare/ieșire taietura.in, taietura.out Sursă ONI 2017, clasa a 10-a
Autor Adrian Budău | Patrick Sava Adăugată de avatar TincaMatei Tinca Matei TincaMatei
Timp de execuție pe test 0.4 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate N/A

Taietura( Clasa a 10-a )

Fiind dat un șir V format din N numere întregi V1, … , VN, 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 Vk , Vk+1, ... , Vpos , ... , Vr-1, Vr 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.

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.

Date de intrare

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.

Date de ieșire

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.

Restricții

  • 1 ≤ N ≤ 100 000
  • Orice element al șirului V este mai mic sau egal în valoare absolută cu 109.
  • Pentru teste în valoare de 20 de puncte N ≤ 100
  • Pentru teste în valoare de încă 20 de puncte N ≤ 1000

Exemplu

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii