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
<syntaxhighlight lang="python" line="1">
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()
</syntaxhighlight>
Explicații
Codul se descompune în următoarele etape:
- Se deschide fișierul "sume1.in" și se citeste valoarea lui N de pe prima linie.
- 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.
- 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.
- 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.
- 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.
- Executia programului se termină.