| Fişierul intrare/ieşire: | taietura.in, taietura.out | Sursă | ONI 2017, clasa a 10-a |
| Autor | Adrian Budau, Patrick Sava | Adăugată de |  Dospra Cristian •BLz0r |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | taietura.out | Explicaţ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. |
