2197 - taietura

Enunt

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.

Cerința

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 și precizări

• 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

Exemplul 1

taieturain.txt

3

0 1 0

taieturaout.txt

Datele introduse corespund restrictiilor impuse.

1 0 1

Exemplul 2

taietrurain.txt

50

taieturaout.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python3" line="1">

def calculate_MulT(N, V):

   prefix_sum = [0] * (N + 1)
   result = 0

   # Construim vectorul prefix_sum
   for i in range(1, N + 1):
       prefix_sum[i] = prefix_sum[i - 1] + V[i - 1]

   # Calculăm funcția MulT pentru fiecare poziție
   for i in range(1, N + 1):
       for j in range(i, N + 1):
           if prefix_sum[j] - prefix_sum[i - 1] == 0:
               result += 1

   return result

def main():

   N = int(input("Introduceți lungimea șirului V: "))
   V = list(map(int, input("Introduceți elementele șirului V, separate prin spațiu: ").split()))

   rezultat = calculate_MulT(N, V)
   print(f"Rezultatul pentru funcția MulT este: {rezultat}")

if __name__ == "__main__":

   main()

</syntaxhighlight>