0300 - SumaInSecv: Diferență între versiuni

De la Universitas MediaWiki
(Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/4148/secv10 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...)
 
Fără descriere a modificării
 
(Nu s-au afișat 6 versiuni intermediare efectuate de alți 2 utilizatori)
Linia 10: Linia 10:


== Date de ieșire ==  
== Date de ieșire ==  
Fişierul de ieşire sumainsecv.out va conţine pe prima linie numerele p şi u, separate printr-un spaţiu, reprezentând indicele de început şi de sfârşit al secvenţei determinate.
 
Dacă datele sunt introduse corect, pe ecran se va afișa:
'''"Datele sunt introduse corect."''și fișierul 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 ==
== Restricţii şi precizări ==
Linia 17: Linia 19:
* dacă vectorul nu conţine nici o secvenţă cu suma elementelor S, se va afişa 0 0
* 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
* dacă şirul conţine mai multe secvenţe cu suma elementelor egală cu S, se va determina cea mai din stânga
== Exemplu ==
== Exemplu 1 ==
; Intrare
; Intrare
: secv10.in
: 8 32   
: 8 32   
: 12 10 15 7 17 13 19 14
: 12 10 15 7 17 13 19 14
; Ieșire
; Ieșire
: Datele sunt introduse correct
: secv10.out
: 2 4  
: 2 4  
== Exemplu 2 ==
; Intrare
: secv10.in
: 0 32
:
; Ieșire
: Datele nu corespund restricțiilor impuse.


== Rezolvare ==  
== Rezolvare ==  
Linia 29: Linia 41:
# 0300 - SumaInSecv
# 0300 - SumaInSecv


n, S = map(int, input().split())
def secv_suma(n, S, v):
v = [int(input()) for i in range(n)]
    dp = [[0 for j in range(n)] for i in range(n)]
 
    for i in range(n):
        dp[i][i] = v[i]
        for j in range(i+1, n):
            dp[i][j] = dp[i][j-1] + v[j]
 
    lmax = c = 0
 
    for i in range(n):
        for j in range(i, n):
            if dp[i][j] == S:
                l = j-i+1
                if l > lmax:
                    lmax = l
                    c = 1
                elif l == lmax:
                    c += 1


sum_window = 0
    if lmax == 0:
start_index = 0
        return 0, 0
max_len = 0
    else:
max_start_index = 0
        return lmax, c


for end_index in range(n):
def validate_input(n, S, v):
    sum_window += v[end_index]
    if not (1 <= n <= 100):
      
        return False
     while sum_window > S:
    if len(v) != n:
         sum_window -= v[start_index]
        return False
        start_index += 1
    for i in range(n):
   
        if not (1 <= v[i] <= 9999):
    if sum_window == S:
            return False
         window_len = end_index - start_index + 1
     return True
         if window_len > max_len:
 
             max_len = window_len
if __name__ == "__main__":
            max_start_index = start_index
     try:
         with open("sumainsecv.in") as f:
            n, S = map(int, f.readline().split())
            v = []
            for i in range(n):
                row = f.readline().split()
                if len(row) != 1:
                    raise ValueError("Datele nu corespund restricțiilor impuse.")
                v.append(int(row[0]))
            if not validate_input(n, S, v):
                raise ValueError("Datele nu corespund restricțiilor impuse.")
         print("Datele sunt introduse corect.")
        lmax, c = secv_suma(n, S, v)
         with open("secv10.out", "w") as f:
             f.write(f"{lmax} {c}")
    except Exception as e:
        print("Datele nu corespund restricțiilor impuse.")
        print(e)


if max_len == 0:
    print("0 0")
else:
    max_end_index = max_start_index + max_len - 1
    print(max_start_index + 1, max_end_index + 1)


</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
`secv_suma(n, S, v)`: Această funcție primește trei argumente: `n` - lungimea listei `v`, `S` - suma căutată și `v` - lista de numere întregi. Scopul funcției este să găsească cea mai lungă subsecvență continuă a listei `v` a cărei sumă este egală cu `S`. Funcția utilizează o abordare dinamică pentru a calcula matricea `dp` care stochează sumele parțiale ale subsecvențelor. Apoi, se verifică fiecare subsecvență pentru a determina cea mai lungă subsecvență cu suma `S`. Funcția returnează un tuplu `(lmax, c)` unde `lmax` este lungimea celei mai lungi subsecvențe și `c` este numărul de subsecvențe cu aceeași lungime maximă.
`validate_input(n, S, v)`: Această funcție primește trei argumente: `n` - lungimea listei `v`, `S` - suma căutată și `v` - lista de numere întregi. Scopul funcției este să valideze datele de intrare conform restricțiilor impuse. Verifică dacă lungimea listei `v` este `n`, dacă `n` se încadrează în intervalul permis și dacă fiecare element din `v` se încadrează în intervalul permis. Returnează `True` dacă datele sunt valide și `False` în caz contrar.
Funcția principală `if __name__ == "__main__"` citeste datele de intrare din fișierul "sumainsecv.in", validează datele folosind funcția `validate_input()`, apoi apelează funcția `secv_suma()` pentru a obține rezultatul dorit. Rezultatul este scris în fișierul "secv10.out". Dacă apar erori în citirea sau validarea datelor, se afișează un mesaj corespunzător pe ecran.

Versiunea curentă din 14 mai 2023 21:37

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

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect."și fișierul 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
Datele sunt introduse correct
secv10.out
2 4

Exemplu 2

Intrare
secv10.in
0 32
Ieșire
Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

# 0300 - SumaInSecv

def secv_suma(n, S, v):
    dp = [[0 for j in range(n)] for i in range(n)]

    for i in range(n):
        dp[i][i] = v[i]
        for j in range(i+1, n):
            dp[i][j] = dp[i][j-1] + v[j]

    lmax = c = 0

    for i in range(n):
        for j in range(i, n):
            if dp[i][j] == S:
                l = j-i+1
                if l > lmax:
                    lmax = l
                    c = 1
                elif l == lmax:
                    c += 1

    if lmax == 0:
        return 0, 0
    else:
        return lmax, c

def validate_input(n, S, v):
    if not (1 <= n <= 100):
        return False
    if len(v) != n:
        return False
    for i in range(n):
        if not (1 <= v[i] <= 9999):
            return False
    return True

if __name__ == "__main__":
    try:
        with open("sumainsecv.in") as f:
            n, S = map(int, f.readline().split())
            v = []
            for i in range(n):
                row = f.readline().split()
                if len(row) != 1:
                    raise ValueError("Datele nu corespund restricțiilor impuse.")
                v.append(int(row[0]))
            if not validate_input(n, S, v):
                raise ValueError("Datele nu corespund restricțiilor impuse.")
        print("Datele sunt introduse corect.")
        lmax, c = secv_suma(n, S, v)
        with open("secv10.out", "w") as f:
            f.write(f"{lmax} {c}")
    except Exception as e:
        print("Datele nu corespund restricțiilor impuse.")
        print(e)

Explicatie Rezolvare

`secv_suma(n, S, v)`: Această funcție primește trei argumente: `n` - lungimea listei `v`, `S` - suma căutată și `v` - lista de numere întregi. Scopul funcției este să găsească cea mai lungă subsecvență continuă a listei `v` a cărei sumă este egală cu `S`. Funcția utilizează o abordare dinamică pentru a calcula matricea `dp` care stochează sumele parțiale ale subsecvențelor. Apoi, se verifică fiecare subsecvență pentru a determina cea mai lungă subsecvență cu suma `S`. Funcția returnează un tuplu `(lmax, c)` unde `lmax` este lungimea celei mai lungi subsecvențe și `c` este numărul de subsecvențe cu aceeași lungime maximă.

`validate_input(n, S, v)`: Această funcție primește trei argumente: `n` - lungimea listei `v`, `S` - suma căutată și `v` - lista de numere întregi. Scopul funcției este să valideze datele de intrare conform restricțiilor impuse. Verifică dacă lungimea listei `v` este `n`, dacă `n` se încadrează în intervalul permis și dacă fiecare element din `v` se încadrează în intervalul permis. Returnează `True` dacă datele sunt valide și `False` în caz contrar.

Funcția principală `if __name__ == "__main__"` citeste datele de intrare din fișierul "sumainsecv.in", validează datele folosind funcția `validate_input()`, apoi apelează funcția `secv_suma()` pentru a obține rezultatul dorit. Rezultatul este scris în fișierul "secv10.out". Dacă apar erori în citirea sau validarea datelor, se afișează un mesaj corespunzător pe ecran.