2142 - easy sum: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 12: Line 12:
Fișierul de ieșire easy_sum.out va conține:
Fișierul de ieșire easy_sum.out va conține:
Dacă datele sunt introduse corect, pe ecran se va afișa:  
Dacă datele sunt introduse corect, pe ecran se va afișa:  
'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.
'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul S, reprezentând suma sumelor tuturor subsecvențelor modulo 1.000.000.007''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.


== Restricţii şi precizări ==
== Restricţii şi precizări ==
Line 18: Line 18:
* numerele de pe a doua linie a fișierului de intrare vor fi cuprinse în intervalul [1,1.000.000]
* numerele de pe a doua linie a fișierului de intrare vor fi cuprinse în intervalul [1,1.000.000]
* prin subsecvență înțelegem orice înșiruire de elemente din vector aflate pe poziții consecutive.
* prin subsecvență înțelegem orice înșiruire de elemente din vector aflate pe poziții consecutive.
== Exemplu ==
== Exemplu 1 ==
; Intrare
; Intrare
: easy_sum.in
: 3
: 3
: 1 2 3
: 1 2 3
; Ieșire
; Ieșire
: easy_sum.out
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.
: Datele sunt introduse correct.
: Datele sunt introduse correct.
: 20
: 20
== Exemplu 1 ==
; Intrare
: easy_sum.in
: 21
: 1 2 3 4 2 7 -8
; Ieșire
: easy_sum.out
: Datele nu corespund restricțiilor impuse.


== Rezolvare ==  
== Rezolvare ==  

Revision as of 07:59, 3 May 2023

Sursa: 2142 - easy sum


Cerinţa

Se consideră un vector cu n elemente numere naturale. Calculați suma sumelor tuturor subsecvențelor ce se pot forma cu elementele vectorului. Pentru că suma poate fi foarte mare, afișați suma modulo 1.000.000.007.


Date de intrare

Fișierul de intrare easy_sum.in 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 easy_sum.out va conține: Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou numărul S, reprezentând suma sumelor tuturor subsecvențelor modulo 1.000.000.007, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

  • 1 ≤ n ≤ 100.000
  • numerele de pe a doua linie a fișierului de intrare vor fi cuprinse în intervalul [1,1.000.000]
  • prin subsecvență înțelegem orice înșiruire de elemente din vector aflate pe poziții consecutive.

Exemplu 1

Intrare
easy_sum.in
3
1 2 3
Ieșire
easy_sum.out
Datele nu corespund restricțiilor impuse.
Datele sunt introduse correct.
20

Exemplu 1

Intrare
easy_sum.in
21
1 2 3 4 2 7 -8
Ieșire
easy_sum.out
Datele nu corespund restricțiilor impuse.


Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 2142 - easy sum

MOD = 1000000007

def read_input():

   n = int(input())
   nums = list(map(int, input().split()))
   return n, nums

def solve(n, nums):

   total_sum = sum(nums)
   partial_sums = [0]
   for num in nums:
       partial_sums.append((partial_sums[-1] + num) % MOD)
   subseq_sum = 0
   for i in range(n):
       left_sum = partial_sums[i+1]
       right_sum = (total_sum - partial_sums[i+1] + MOD) % MOD
       
       subseq_sum += (i+1) * left_sum
       subseq_sum %= MOD
       
       subseq_sum += (n-i) * right_sum
       subseq_sum %= MOD
       
       subseq_sum += left_sum * right_sum
       subseq_sum %= MOD
       
   return subseq_sum

def validate_output(expected_output, output):

   if int(expected_output) == int(output):
       print("Datele sunt introduse corect.")
   else:
       print("Datele nu corespund restricțiilor impuse.")
       print(output)

if __name__ == '__main__':

   n, nums = read_input()
   result = solve(n, nums)
   print(result)
   validate_output(input(), result)


</syntaxhighlight>

Explicatie Rezolvare

Funcția read_input citește datele de intrare din stdin și le returnează ca o tuplă (n, nums). Funcția solve primește n și nums și calculează suma tuturor subsecvențelor ca descris în comentarii. În loc să calculeze suma tuturor subsecvențelor direct, calculează sume parțiale și le combină ulterior. Funcția validate_output primește ieșirea așteptată și ieșirea obținută și returnează True dacă acestea sunt egale (ignorând spațiile suplimentare). În if __name__ == '__main__', se citesc datele de intrare, se rezolvă