0519 - Secventa1

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

<syntaxhighlight lang="python" line>

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()

</syntaxhighlight>

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.