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

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