0300 - SumaInSecv

Sursa: 0300 - SumaInSecv

---

Cerinţa

Se dă un vector format din n elemente, numere naturale nenule, şi un număr natural S. Determinaţi, dacă există o secvenţă de elemente din şir cu suma elementelor egală cu S.

Date de intrare

Fişierul de intrare sumainsecv.in conţine pe prima linie numerele n şi S; urmează cele n elemente ale vectorului, dispuse pe mai multe linii şi separate prin spaţii.

Date de ieșire

Fişierul de ieşire sumainsecv.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 secv10.out va conține pe prima linie numerele lmax și c, reprezentând lungimea maximă a unei secvențe de elemente divizibile cu 10, respectiv numărul de secvențe de lungime maximă cu elemente divizibile cu 10, 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
• elementele vectorului vor avea cel mult 4 cifre şi sunt numerotate de la 1 la n
• dacă vectorul nu conţine nici o secvenţă cu suma elementelor S, se va afişa 0 0
• dacă şirul conţine mai multe secvenţe cu suma elementelor egală cu S, se va determina cea mai din stânga

Exemplu 1

Intrare

secv10.in

8 32

12 10 15 7 17 13 19 14

Ieșire

secv10.out

Datele sunt introduse correct

2 4

Exemplu 2

Intrare

secv10.in

8 32

12 10 15 7 17 13 19 14

Ieșire

secv10.out

Datele nu corespund restricțiilor impuse.

5 1

Rezolvare

Rezolvare ver. 1

# 0300 - SumaInSecv

def citire_date():
    n, s = map(int, input().split())
    v = []
    for i in range(n):
        v.extend(map(int, input().split()))
    return n, s, v

def suma_in_secventa(n, s, v):
    suma = 0
    st = 0
    dr = 0
    for i in range(n):
        suma += v[i]
        dr += 1
        while suma > s:
            suma -= v[st]
            st += 1
        if suma == s:
            return st + 1, dr
    return 0, 0

def validare(n, s, v):
    if len(v) != n:
        return False
    for x in v:
        if x < 1 or x > 9999:
            return False
    return True

if __name__ == '__main__':
    n, s, v = citire_date()
    if validare(n, s, v):
        print("Datele sunt introduse corect.")
        st, dr = suma_in_secventa(n, s, v)
        if st == 0 and dr == 0:
            print("0 0")
        else:
            print(st, dr)
    else:
        print("Datele nu corespund restricțiilor impuse.")

Explicatie Rezolvare

citire_date() primeste de la input n si s, urmate de n numerele ale vectorului v. Folosind extend, toate numerele vectorului sunt citite intr-o singura lista. suma_in_secventa() cauta o secventa a vectorului v cu suma elementelor egala cu s, folosind un algoritm de tip sliding window, care tine minte in st si dr indecsii de start si sfarsit ai secventei. Daca gaseste o astfel de secventa, returneaza indecsii acesteia. Daca nu exista o astfel de secventa, returneaza 0 0. validare() verifica daca datele de intrare sunt corecte, adica vectorul sa aiba n elemente si toate elementele sa fie intre 1 si 9999. In functia principala, mai intai se verifica daca datele de intrare sunt corecte folosind validare(). Daca da, se afiseaza un mesaj de confirmare si se apeleaza suma_in_secventa() pentru a determina indecsii secventei cu suma egala cu s. Daca nu exista o astfel de secventa, se afiseaza "0 0". Daca exista, se afiseaza indecsii acesteia. Daca datele de intrare nu sunt corecte, se afiseaza un mesaj corespunzator.