0521 - kSecventa: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 31: Line 31:
# 0521 - kSecventa
# 0521 - kSecventa


def citire_date():
def kSecventa(n, k, v):
     n, k = map(int, input().split())
     if n % k != 0:
    x = list(map(int, input().split()))
        print("Datele nu corespund restricțiilor impuse.")
    return n, k, x
        return


def numar_secvente(n, k, x, t):
    # Impartim lista in k bucati cat mai egale
     counter = 0
    chunk_size = n // k
     for i in range(n-k+1):
    extra = n % k
         secventa = x[i:i+k]
     chunks = []
         if all(e <= t for e in secventa):
    start = 0
             counter += 1
     for i in range(k):
    return counter
         end = start + chunk_size
         if extra > 0:
             end += 1
            extra -= 1
        chunks.append(v[start:end])
        start = end


def valideaza_datele_de_intrare(n, k, x):
    # Verificam daca exista doua secvente identice
    if not (1 <= k <= n <= 100000 and all(0 < i < 1000000000 for i in x)):
    for i in range(k):
        print("Datele nu corespund restricțiilor impuse.")
        for j in range(i+1, k):
        exit()
            if chunks[i] == chunks[j]:
                print("Datele sunt introduse corect.")
                print(i+1, j+1)
                return


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("Datele sunt introduse corect.")
     print(rezultat)
     print("NU")
 
if __name__ == "__main__":
    n, k = map(int, input().split())
    v = list(map(int, input().split()))
 
    kSecventa(n, k, v)
 


</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==  
== Explicatie Rezolvare ==  
Citim datele de intrare (n, k și vectorul x).
Funcția kSecventa(n, k, v) primește ca argumente lungimea vectorului n, numărul de secvențe k și vectorul v.
Calculăm lungimea fiecărei secvențe (l), care este egală cu n/k.
Inițializăm variabila secv_len cu lungimea secvențelor, adică n // k.
Inițializăm un dicționar (seq_dict) în care vom stoca fiecare secvență și numărul de apariții a acesteia.
Folosim două bucle for pentru a itera prin toate perechile de secvențe și verificăm dacă ele sunt identice, comparând subșirurile corespunzătoare din vectorul v.
Iterăm prin fiecare secvență (de la 1 la k) și:
Dacă găsim două secvențe identice, afișăm numerele lor de ordine și opri căutarea cu return.
a. Extragem secvența corespunzătoare.
Dacă nu găsim nicio pereche de secvențe identice, afișăm "NU".
b. Dacă secvența nu există deja în dicționar, o adăugăm cu valoarea 1.
În funcția main, citim n și k de la tastatură și verificăm dacă datele introduse corespund restricțiilor impuse.
c. Dacă secvența există deja în dicționar, o incrementăm cu 1.
Dacă datele sunt introduse corect, citim vectorul v și apelăm funcția kSecventa(n, k, v) pentru a rezolva problema.
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".

Revision as of 21:15, 13 May 2023

Sursa: 0521 - kSecventa


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 a 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ă există mai multe perechi de secvențe identice se vor considera cele cu numerele de ordine minime., 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 1

Intrare
15 5
3 6 4 7 6 6 6 4 6 7 6 6 4 4 5
Ieșire
Datele sunt introduse corect.
2 4

Exemplu 2

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

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 0521 - kSecventa

def kSecventa(n, k, v):

   if n % k != 0:
       print("Datele nu corespund restricțiilor impuse.")
       return
   # Impartim lista in k bucati cat mai egale
   chunk_size = n // k
   extra = n % k
   chunks = []
   start = 0
   for i in range(k):
       end = start + chunk_size
       if extra > 0:
           end += 1
           extra -= 1
       chunks.append(v[start:end])
       start = end
   # Verificam daca exista doua secvente identice
   for i in range(k):
       for j in range(i+1, k):
           if chunks[i] == chunks[j]:
               print("Datele sunt introduse corect.")
               print(i+1, j+1)
               return
   print("Datele sunt introduse corect.")
   print("NU")

if __name__ == "__main__":

   n, k = map(int, input().split())
   v = list(map(int, input().split()))
   kSecventa(n, k, v)


</syntaxhighlight>

Explicatie Rezolvare

Funcția kSecventa(n, k, v) primește ca argumente lungimea vectorului n, numărul de secvențe k și vectorul v. Inițializăm variabila secv_len cu lungimea secvențelor, adică n // k. Folosim două bucle for pentru a itera prin toate perechile de secvențe și verificăm dacă ele sunt identice, comparând subșirurile corespunzătoare din vectorul v. Dacă găsim două secvențe identice, afișăm numerele lor de ordine și opri căutarea cu return. Dacă nu găsim nicio pereche de secvențe identice, afișăm "NU". În funcția main, citim n și k de la tastatură și verificăm dacă datele introduse corespund restricțiilor impuse. Dacă datele sunt introduse corect, citim vectorul v și apelăm funcția kSecventa(n, k, v) pentru a rezolva problema.