2142 - easy sum: Diferență între versiuni

De la Universitas MediaWiki
(Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/2142/easy-sum 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...)
 
Fără descriere a modificării
Linia 10: Linia 10:


== Date de ieșire ==  
== Date de ieșire ==  
Fișierul de ieșire easy_sum.out va conține pe prima linie numărul S, reprezentând suma sumelor tuturor subsecvențelor modulo 1.000.000.007.
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 c''', 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 ==
Linia 21: Linia 23:
: 1 2 3
: 1 2 3
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele sunt introduse correct.
: 20
: 20


Linia 36: Linia 40:


def solve(n, nums):
def solve(n, nums):
    # suma tuturor subsecventelor va fi data de:
    # suma(sum[i:j]) pentru i in [0, n) si j in [i+1, n+1)
    # putem rescrie asta ca:
    # suma(sum[i:n]) + suma(sum[0:j]) - suma(sum[0:i]) pentru i in [0, n) si j in [i+1, n+1)
    # (primul termen este suma tuturor subsecventelor care incep cu i,
    #  al doilea termen este suma tuturor subsecventelor care se termina cu j-1,
    #  iar al treilea termen este suma tuturor subsecventelor care incep inainte de i)
    # putem calcula aceste sume partial pentru a reduce timpul de executie
    # calculam suma tuturor numerelor din nums si suma partiala a numerelor din nums
     total_sum = sum(nums)
     total_sum = sum(nums)
     partial_sums = [0]
     partial_sums = [0]
Linia 51: Linia 45:
         partial_sums.append((partial_sums[-1] + num) % MOD)
         partial_sums.append((partial_sums[-1] + num) % MOD)


    # calculam suma tuturor subsecventelor
     subseq_sum = 0
     subseq_sum = 0
     for i in range(n):
     for i in range(n):
        # calculam sum[0:i] si sum[i:n]
         left_sum = partial_sums[i+1]
         left_sum = partial_sums[i+1]
         right_sum = (total_sum - partial_sums[i+1] + MOD) % MOD
         right_sum = (total_sum - partial_sums[i+1] + MOD) % MOD
          
          
        # adaugam la suma totala suma tuturor subsecventelor care incep cu i
         subseq_sum += (i+1) * left_sum
         subseq_sum += (i+1) * left_sum
         subseq_sum %= MOD
         subseq_sum %= MOD
          
          
        # adaugam la suma totala suma tuturor subsecventelor care se termina cu j-1
         subseq_sum += (n-i) * right_sum
         subseq_sum += (n-i) * right_sum
         subseq_sum %= MOD
         subseq_sum %= MOD
          
          
        # adaugam la suma totala suma tuturor subsecventelor care incep inainte de i
         subseq_sum += left_sum * right_sum
         subseq_sum += left_sum * right_sum
         subseq_sum %= MOD
         subseq_sum %= MOD
Linia 73: Linia 62:


def validate_output(expected_output, output):
def validate_output(expected_output, output):
     return int(expected_output) == int(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__':
if __name__ == '__main__':
Linia 79: Linia 72:
     result = solve(n, nums)
     result = solve(n, nums)
     print(result)
     print(result)
    validate_output(input(), result)





Versiunea de la data 28 aprilie 2023 14:43

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 c, 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

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

Rezolvare

Rezolvare ver. 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)

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ă