1428 - Sume1

Cerința

Se dă un număr natural N. Să se calculeze expresia:

E=(20+21+22+23+…+2N)%1000000007 unde x % y reprezintă restul împărţirii lui x la y.

Date de intrare

Fișierul de intrare sume1.in conține pe prima linie numărul N.

Date de ieșire

Fișierul de ieșire sume1.out va conține pe prima linie rezultatul expresiei E.

Restricții și precizări

• 1 ≤ N ≤ 1017
• 1000000007 este număr prim.
• Pentru 30% din teste, N ≤ 106

Exemplu

Exemplu1

Intrare:

sume1.in

4

Iesire:

sume1.out

Datele introduse sunt corecte!

31

Rezolvare

 
def validare(N):
    if N < 1 or N > 10 ** 17:
        return False
    return True


def rezolvare(N):
    mod = 1000000007
    S = 0
    for i in range(N+1):
        S += 2**i
    E = S % mod
    return E




def main():
    with open("sume1.in", "r") as f:
        N = int(f.readline().strip())

    if not validare(N):
        print("Datele introduse sunt incorecte!")
        return

    S = rezolvare(N)

    with open("sume1.out", "w") as f:
        f.write("Datele introduse sunt corecte!\n")
        f.write(str(S))


if __name__ == "__main__":
    main()

Explicații

Codul se descompune în următoarele etape:

1. Se deschide fișierul "sume1.in" și se citeste valoarea lui N de pe prima linie.
2. Se validează valoarea lui N: trebuie să fie un număr întreg pozitiv și mai mic sau egal cu 10^17. Dacă N nu respectă aceste condiții, se afișează mesajul "Datele introduse sunt incorecte!" și se oprește executarea programului. Altfel, se continuă executarea programului.
3. Se calculează valoarea lui S, care reprezintă suma primei progresii geometrice cu raportul 2 și cu primul termen 2 la puterea N+1. Formula utilizată este (2^(N+1))-2.
4. Se calculează valoarea lui E, care reprezintă suma primei progresii aritmetice cu primul termen S și cu diferența 20. Formula utilizată este S+20.
5. Se deschide fișierul "sume1.out" și se scrie mesajul "Datele introduse sunt corecte!" pe prima linie, urmat de valoarea lui E pe a doua linie.
6. Executia programului se termină.