0519 - Secventa1: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
Fără descriere a modificării
Linia 37: Linia 37:
# 0519 - Secventa1
# 0519 - Secventa1


def validate_input(n, x, m, y):
def gaseste_secventa_maxima(x, y):
     if not (1 <= n <= 100000 and 1 <= m <= 100000):
     for i in range(len(x) - len(y) + 1):
        print("Datele nu corespund restricțiilor impuse.")
         if x[i:i+len(y)] == y:
        return False
             return i + 1  # indexam de la 1
    if not all(1 <= xi <= 1000000 for xi in x) or not all(1 <= yi <= 1000000 for yi in y):
        print("Datele nu corespund restricțiilor impuse.")
        return False
    return True
 
def is_subsequence(n, x, m, y):
    for i in range(n - m + 1):
         if x[i:i + m] == y:
             return i + 1
     return -1
     return -1


def read_input():
def main():
     try:
     n = int(input())
        n = int(input("Introduceti numarul de elemente al vectorului x: "))
    x = input().split()
        x = list(map(int, input("Introduceti elementele vectorului x, separate prin spatiu: ").split()))
    m = int(input())
        m = int(input("Introduceti numarul de elemente al vectorului y: "))
    y = input().split()
        y = list(map(int, input("Introduceti elementele vectorului y, separate prin spatiu: ").split()))
        if not validate_input(n, x, m, y):
            print("Datele nu corespund restricțiilor impuse.")
            return None, None, None, None
        print("Datele sunt introduse corect.")
        return n, x, m, y
    except ValueError:
        print("Datele introduse trebuie sa fie numere intregi.")
        return None, None, None, None
 


def validate_output(result):
    # validare date de intrare
     if result != -1:
     if n <= 0 or n > 1000 or m <= 0 or m > n or len(x) != n or len(y) != m:
         print(result)
         print("Datele nu corespund restricțiilor impuse.")
     else:
     else:
         print("NU")
         try:
            x = [int(elem) for elem in x]
            y = [int(elem) for elem in y]
        except ValueError:
            print("Datele nu corespund restricțiilor impuse.")
            exit(0)


        if max(x) >= 1000 or max(y) >= 1000:
            print("Datele nu corespund restricțiilor impuse.")
        else:
            pozitie_start = gaseste_secventa_maxima(x, y)
            if pozitie_start != -1:
                print("Datele sunt introduse corect.")
                print(pozitie_start)
            else:
                print("Datele nu corespund restrictiilor impuse ")


if __name__ == "__main__":
if __name__ == "__main__":
     n, x, m, y = read_input()
     main()
    if n is not None and x is not None and m is not None and y is not None:
        result = is_subsequence(n, x, m, y)
        validate_output(result)




Linia 91: Linia 83:
Funcția `is_subsequence(n, x, m, y)` primește 4 argumente, primele două fiind lungimea și elementele listei `x`, iar ultimele două fiind lungimea și elementele listei `y`. Funcția verifică dacă lista `y` este o subsecvență a listei `x` și returnează indexul primului element al primei apariții a listei `y` în lista `x` dacă da, sau `-1` în caz contrar.
Funcția `is_subsequence(n, x, m, y)` primește 4 argumente, primele două fiind lungimea și elementele listei `x`, iar ultimele două fiind lungimea și elementele listei `y`. Funcția verifică dacă lista `y` este o subsecvență a listei `x` și returnează indexul primului element al primei apariții a listei `y` în lista `x` dacă da, sau `-1` în caz contrar.


Funcția `validate_output(result)` primește rezultatul obținut de la `is_subsequence()` și îl afișează în funcție de cerințele problemei, adică afișează indexul primului element al primei apariții a listei `y` în lista `x`, dacă aceasta este o subsecvență a listei `x`, sau afișează "NU" în caz contrar.
Funcția `validate_output(result)` primește rezultatul obținut de la `is_subsequence()` și îl afișează în funcție de cerințele problemei, adică afișează indexul primului element al primei apariții a listei `y` în lista `x`, dacă aceasta este o subsecvență a listei `x`, sau afișează "Datele nu corespund restrictiilor impuse" în caz contrar.

Versiunea de la data 13 mai 2023 21:07

Sursa: 0519 - Secventa1

Cerinţa

Se dă un vector x cu n elemente, numere naturale și un vector y cu m elemente, numere naturale. Să se verifice dacă vectorul y este secvență în vectorul x.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, elementele vectorului x, apoi numărul m, iar apoi m numere naturale, elementele vectorului y.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou va afișa pe ecran numărul p, reprezentând poziția din vectorul x de unde începe secvența y, dacă y este secvență în x, respectiv mesajul NU dacă y nu este secvență în x, 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 ≤ m ≤ n ≤ 1000
  • elementele celor doi vectori vor fi indexate de la 1
  • dacă vectorul y este de mai multe ori secvență în x se va afișa poziția de început a primei apariții

Exemplu 1

Intrare
10
8 5 8 5 2 3 10 7 1 6
6
8 5 2 3 10 7
Ieșire
Datele sunt introduse corect.
3

Exemplu 2

Intrare
1
2 3 4 5 6 7 8 3 1 11 2
4
1 2 3 4 5 6
Ieșire
Datele nu corespund restricțiilor impuse.
6

Rezolvare

Rezolvare ver. 1

# 0519 - Secventa1

def gaseste_secventa_maxima(x, y):
    for i in range(len(x) - len(y) + 1):
        if x[i:i+len(y)] == y:
            return i + 1  # indexam de la 1
    return -1

def main():
    n = int(input())
    x = input().split()
    m = int(input())
    y = input().split()

    # validare date de intrare
    if n <= 0 or n > 1000 or m <= 0 or m > n or len(x) != n or len(y) != m:
        print("Datele nu corespund restricțiilor impuse.")
    else:
        try:
            x = [int(elem) for elem in x]
            y = [int(elem) for elem in y]
        except ValueError:
            print("Datele nu corespund restricțiilor impuse.")
            exit(0)

        if max(x) >= 1000 or max(y) >= 1000:
            print("Datele nu corespund restricțiilor impuse.")
        else:
            pozitie_start = gaseste_secventa_maxima(x, y)
            if pozitie_start != -1:
                print("Datele sunt introduse corect.")
                print(pozitie_start)
            else:
                print("Datele nu corespund restrictiilor impuse ")

if __name__ == "__main__":
    main()

Explicatie Rezolvare

În acest cod, funcția `read_input()` citeste valorile de intrare de la utilizator și le returnează într-o tuplă, în ordinea în care au fost citite.

Funcția `is_subsequence(n, x, m, y)` primește 4 argumente, primele două fiind lungimea și elementele listei `x`, iar ultimele două fiind lungimea și elementele listei `y`. Funcția verifică dacă lista `y` este o subsecvență a listei `x` și returnează indexul primului element al primei apariții a listei `y` în lista `x` dacă da, sau `-1` în caz contrar.

Funcția `validate_output(result)` primește rezultatul obținut de la `is_subsequence()` și îl afișează în funcție de cerințele problemei, adică afișează indexul primului element al primei apariții a listei `y` în lista `x`, dacă aceasta este o subsecvență a listei `x`, sau afișează "Datele nu corespund restrictiilor impuse" în caz contrar.

Adus de la „http://wiki.universitas.ro/index.php?title=0519_-_Secventa1&oldid=6326”