2142 - easy sum: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
Fără descriere a modificării
Linia 24: Linia 24:
: 1 2 3
: 1 2 3
; Ieșire
; Ieșire
: Datele sunt introduse correct.
: easy_sum.out
: easy_sum.out
: Datele nu corespund restricțiilor impuse.
: Datele sunt introduse correct.
: 20
: 20
== Exemplu 1 ==
 
== Exemplu 2 ==
; Intrare
; Intrare
: easy_sum.in
: easy_sum.in
Linia 34: Linia 34:
: 1 2 3 4 2 7 -8
: 1 2 3 4 2 7 -8
; Ieșire
; Ieșire
: easy_sum.out
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.


Linia 45: Linia 44:
MOD = 1000000007
MOD = 1000000007


def read_input():
def validate_input(n, arr):
     n = int(input())
     if not (1 <= n <= 100000):
     nums = list(map(int, input().split()))
        return False
    return n, nums
    if len(arr) != n:
        return False
    if any(num < 1 or num > 1000000 for num in arr):
        return False
     return True
 
 
def calculate_subsequence_sum(n, arr):
    if not validate_input(n, arr):
        return "Datele nu corespund restricțiilor impuse."


def solve(n, nums):
     MOD = 1000000007
     total_sum = sum(nums)
     total_sum = 0
     partial_sums = [0]
    for num in nums:
        partial_sums.append((partial_sums[-1] + num) % MOD)


    subseq_sum = 0
     for i in range(n):
     for i in range(n):
         left_sum = partial_sums[i+1]
         total_sum = (total_sum + (arr[i] * (i + 1) * (n - i)) % MOD) % MOD
        right_sum = (total_sum - partial_sums[i+1] + MOD) % MOD
 
       
     return total_sum
        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 __name__ == "__main__":
    if int(expected_output) == int(output):
    file_name = "easy_sum.in"
        print("Datele sunt introduse corect.")
     with open(file_name, "r") as file:
     else:
         n = int(file.readline())
         print("Datele nu corespund restricțiilor impuse.")
         arr = list(map(int, file.readline().split()))
         print(output)


if __name__ == '__main__':
     result = calculate_subsequence_sum(n, arr)
    n, nums = read_input()
     result = solve(n, nums)
     print(result)
     print(result)
    validate_output(input(), result)
 




</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Funcția read_input citește datele de intrare din stdin și le returnează ca o tuplă (n, nums).
Funcția validate_input(n, arr):
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).
Această funcție primește doi parametri: n - numărul de elemente din vector și arr - lista de numere.
În if __name__ == '__main__', se citesc datele de intrare, se rezolvă
Verifică dacă valoarea n se încadrează în intervalul specificat în cerință și dacă lungimea listei arr este egală cu n.
Verifică, de asemenea, dacă există vreun număr din lista arr care este mai mic decât 1 sau mai mare decât 1000000. Dacă da, se returnează False, semnalând că datele nu corespund restricțiilor impuse.
Dacă toate verificările sunt trecute cu succes, înseamnă că datele de intrare sunt valide, astfel că se returnează True.
Funcția calculate_subsequence_sum(n, arr):
 
Această funcție primește doi parametri: n - numărul de elemente din vector și arr - lista de numere.
Verifică mai întâi validitatea datelor de intrare folosind funcția validate_input(n, arr). Dacă datele nu sunt valide, returnează un mesaj corespunzător.
Inițializează variabila total_sum cu valoarea 0, care va fi utilizată pentru a calcula suma subsecvențelor.
Parcurge lista arr și pentru fiecare element, adaugă la total_sum valoarea elementului înmulțită cu (i + 1) * (n - i). Aceasta reprezintă numărul de subsecvențe în care elementul curent apare.
Se aplică modularitatea cu MOD pentru a menține suma subsecvențelor într-un interval valid.
La final, se returnează total_sum calculat modulo MOD.
În funcția if __name__ == "__main__", se realizează citirea datelor de intrare din fișierul

Versiunea de la data 14 mai 2023 21:25

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
Datele sunt introduse correct.
easy_sum.out
20

Exemplu 2

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


Rezolvare

Rezolvare ver. 1

# 2142 - easy sum

MOD = 1000000007

def validate_input(n, arr):
    if not (1 <= n <= 100000):
        return False
    if len(arr) != n:
        return False
    if any(num < 1 or num > 1000000 for num in arr):
        return False
    return True


def calculate_subsequence_sum(n, arr):
    if not validate_input(n, arr):
        return "Datele nu corespund restricțiilor impuse."

    MOD = 1000000007
    total_sum = 0

    for i in range(n):
        total_sum = (total_sum + (arr[i] * (i + 1) * (n - i)) % MOD) % MOD

    return total_sum


if __name__ == "__main__":
    file_name = "easy_sum.in"
    with open(file_name, "r") as file:
        n = int(file.readline())
        arr = list(map(int, file.readline().split()))

    result = calculate_subsequence_sum(n, arr)
    print(result)

Explicatie Rezolvare

Funcția validate_input(n, arr):

Această funcție primește doi parametri: n - numărul de elemente din vector și arr - lista de numere. Verifică dacă valoarea n se încadrează în intervalul specificat în cerință și dacă lungimea listei arr este egală cu n. Verifică, de asemenea, dacă există vreun număr din lista arr care este mai mic decât 1 sau mai mare decât 1000000. Dacă da, se returnează False, semnalând că datele nu corespund restricțiilor impuse. Dacă toate verificările sunt trecute cu succes, înseamnă că datele de intrare sunt valide, astfel că se returnează True. Funcția calculate_subsequence_sum(n, arr):

Această funcție primește doi parametri: n - numărul de elemente din vector și arr - lista de numere. Verifică mai întâi validitatea datelor de intrare folosind funcția validate_input(n, arr). Dacă datele nu sunt valide, returnează un mesaj corespunzător. Inițializează variabila total_sum cu valoarea 0, care va fi utilizată pentru a calcula suma subsecvențelor. Parcurge lista arr și pentru fiecare element, adaugă la total_sum valoarea elementului înmulțită cu (i + 1) * (n - i). Aceasta reprezintă numărul de subsecvențe în care elementul curent apare. Se aplică modularitatea cu MOD pentru a menține suma subsecvențelor într-un interval valid. La final, se returnează total_sum calculat modulo MOD. În funcția if __name__ == "__main__", se realizează citirea datelor de intrare din fișierul