1865 - Summit

Cerința

Se dă un şir x format din n numere naturale nenule. Pentru fiecare element xi din şir să se verifice dacă există un număr k astfel încât elementul xi să fie egal cu suma primelor k elemente din şir.

Date de intrare

Fișierul de intrare summitIN.txt conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire summitOUT.txt va conține pe linia i valoarea k dacă elementul xi este egal cu suma primelor k elemente din şir, sau 0 în caz contrar, pentru fiecare i de la 1 la n.

Restricții și precizări

• 2 ≤ n ≤ 1.000.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 2.000.000.000

Exemplul 1

summitIN.txt

3
1 2 3

summitOUT.txt

1
0
2

Exemplul 2

summitIN.txt

1
1

Numerele introduse nu respectă restricțiile.

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verifica_restrictii(n, nums):

   return 2 <= n <= 1000000 and all(0 < x < 2000000000 for x in nums)

def verifica_summit(n, nums):

   suma_partiala = [0]  # Lista pentru suma parțială, începând cu 0

   for i in range(n):
       suma_partiala.append(suma_partiala[-1] + nums[i])

   rezultate = []
   for i in range(n):
       k = 0
       while k < n and suma_partiala[k] < nums[i]:
           k += 1

       if k < n and suma_partiala[k] == nums[i]:
           rezultate.append(k)
       else:
           rezultate.append(0)

   return rezultate

def main():

   with open("summitIN.txt", "r") as f:
       n = int(f.readline())
       nums = list(map(int, f.readline().split()))

   if verifica_restrictii(n, nums):
       rezultate = verifica_summit(n, nums)

       with open("summitOUT.txt", "w") as f:
           for rez in rezultate:
               f.write(str(rez) + "\n")
   else:
       print("Numerele introduse nu respectă restricțiile.")

if __name__ == "__main__":

   main()

</syntaxhighlight>