0521 - kSecventa: Difference between revisions

Revision as of 18:04, 27 April 2023

Cerinţa

Se dă un vector cu n elemente, numere naturale, și un număr k, divizor al lui n. Se împarte vectorul în k secvențe disjuncte, numerotate de la 1 la k. Să se stabilească dacă există două secvențe identice.

Date de intrare

Programul citește de la tastatură numerele n și k, iar apoi n numere naturale, reprezentând elementele vectorului.

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 numărul c, 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 ≤ k < n ≤ 1000, k este divizor al lui n
cele n numere citite vor fi mai mici decât 1000

Exemplu

Intrare: 15 5; 3 6 4 7 6 6 6 4 6 7 6 6 4 4 5
Ieșire: Datele nu corespund restricțiilor impuse.; 2 4

Rezolvare

Rezolvare ver. 1

0521 - kSecventa

def citire_date():

   n, k = map(int, input().split())
   x = list(map(int, input().split()))
   return n, k, x

def numar_secvente(n, k, x, t):

   counter = 0
   for i in range(n-k+1):
       secventa = x[i:i+k]
       if all(e <= t for e in secventa):
           counter += 1
   return counter

def valideaza_datele_de_intrare(n, k, x):

   if not (1 <= k <= n <= 100000 and all(0 < i < 1000000000 for i in x)):
       print("Datele nu corespund restricțiilor impuse.")
       exit()

if __name__ == '__main__':

   n, k, x = citire_date()
   t = int(input())
   valideaza_datele_de_intrare(n, k, x)
   rezultat = numar_secvente(n, k, x, t)
   print("Datele sunt introduse corect.")
   print(rezultat)

</syntaxhighlight>

Explicatie Rezolvare

Citim datele de intrare (n, k și vectorul x). Calculăm lungimea fiecărei secvențe (l), care este egală cu n/k. Inițializăm un dicționar (seq_dict) în care vom stoca fiecare secvență și numărul de apariții a acesteia. Iterăm prin fiecare secvență (de la 1 la k) și: a. Extragem secvența corespunzătoare. b. Dacă secvența nu există deja în dicționar, o adăugăm cu valoarea 1. c. Dacă secvența există deja în dicționar, o incrementăm cu 1. d. Verificăm dacă secvența a fost întâlnită de două ori și, dacă da, afișăm index-urile secvențelor identice și ieșim din program. Dacă nu am găsit două secvențe identice, afișăm "NU".

@@ Line 6: / Line 6: @@
 Programul citește de la tastatură numerele n și k, iar apoi n numere naturale, reprezentând elementele vectorului.
 == Date de ieșire ==
-Programul va afișa pe ecran numerele i j, i < j reprezentând numerele de ordine a două secvențe identice, dacă există două astfel de secvențe, sau mesajul NU, dacă nu există două astfel de secvențe.
+Dacă datele sunt introduse corect, pe ecran se va afișa:
-Dacă există mai multe perechi de secvențe identice se vor considera cele cu numerele de ordine minime.
+'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul c''', 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 ==
 * 1 ≤ k < n ≤ 1000, k este divizor al lui n
 * cele n numere citite vor fi mai mici decât 1000
@@ Line 16: / Line 15: @@
 : 3 6 4 7 6 6 6 4 6 7 6 6 4 4 5
 ; Ieșire
+: Datele nu corespund restricțiilor impuse.
 : 2 4
@@ Line 23: / Line 23: @@
 # 0521 - kSecventa
-def citeste_date_intrare():
+def citire_date():
      n, k = map(int, input().split())
      x = list(map(int, input().split()))
      return n, k, x
-def gaseste_secvente_identice(n, k, x):
+def numar_secvente(n, k, x, t):
-     l = n // k
+     counter = 0
-    seq_dict = {}
+     for i in range(n-k+1):
-     for i in range(1, k+1):
+         secventa = x[i:i+k]
-         seq = tuple(x[(i-1)*l:i*l])
+         if all(e <= t for e in secventa):
-         if seq not in seq_dict:
+            counter += 1
-            seq_dict[seq] = 1
+     return counter
-        else:
-            seq_dict[seq] += 1
-        if seq_dict[seq] == 2:
-            for j in range(1, i):
-                if seq == tuple(x[(j-1)*l:j*l]):
-                    return j, i
-     return "NU"
 def valideaza_datele_de_intrare(n, k, x):
-     assert 1 <= k < n <= 1000 and n % k == 0, "Datele de intrare sunt incorecte!"
+     if not (1 <= k <= n <= 100000 and all(0 < i < 1000000000 for i in x)):
-    assert max(x) < 1000, "Datele de intrare sunt incorecte!"
+        print("Datele nu corespund restricțiilor impuse.")
+        exit()
 if __name__ == '__main__':
-     n, k, x = citeste_date_intrare()
+     n, k, x = citire_date()
+    t = int(input())
      valideaza_datele_de_intrare(n, k, x)
-     rezultat = gaseste_secvente_identice(n, k, x)
+     rezultat = numar_secvente(n, k, x, t)
+    print("Datele sunt introduse corect.")
      print(rezultat)
 </syntaxhighlight>