1428 - Sume1

From Bitnami MediaWiki
Revision as of 21:08, 14 May 2023 by Catalin Moje (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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:

  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ă.