Fişierul intrare/ieşire:taietura.in, taietura.outSursăONI 2017, clasa a 10-a
AutorAdrian Budau, Patrick SavaAdăugată deBLz0rDospra Cristian BLz0r
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Taietura

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 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 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

Exemplu

taietura.intaietura.outExplicaţie
3
0 1 0
1 0 1
Rezultatul pentru MulT este 1 deoarece există o singură
tăietură, şi anume (0) care are valoarea 0. Pentru MulT rezultatul este 0 deoarece nu există nicio tăietură aplicată pe
poziţia 2 care să aibă valoarea 0.
Rezultatul pentru MulT 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 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 sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?