0521 - kSecventa: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 24: Line 24:
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.
: 1 2
 


== Rezolvare ==  
== Rezolvare ==  
Line 31: Line 31:
# 0521 - kSecventa
# 0521 - kSecventa


def kSecventa(n, k, v):
def validate_input(n, k, arr):
    if k >= n:
        return False
     if n % k != 0:
     if n % k != 0:
        return False
    if max(arr) > 1000:
        return False
    return True
def find_identical_sequences(n, k, arr):
    if not validate_input(n, k, arr):
         print("Datele nu corespund restricțiilor impuse.")
         print("Datele nu corespund restricțiilor impuse.")
         return
         return


     # Impartim lista in k bucati cat mai egale
     seq_dict = {}
    chunk_size = n // k
     for i in range(n // k):
    extra = n % k
         seq = tuple(arr[i * k: (i + 1) * k])
    chunks = []
         if seq in seq_dict:
    start = 0
             print(seq_dict[seq], i + 1)
     for i in range(k):
             return
         end = start + chunk_size
         else:
         if extra > 0:
            seq_dict[seq] = i + 1
             end += 1
             extra -= 1
         chunks.append(v[start:end])
        start = end


     # Verificam daca exista doua secvente identice
     print("NU")
    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__":
if __name__ == "__main__":
     n, k = map(int, input().split())
     n, k = map(int, input().split())
     v = list(map(int, input().split()))
     arr = list(map(int, input().split()))


     kSecventa(n, k, v)
     if validate_input(n, k, arr):
        print("Datele sunt introduse corect.")
        find_identical_sequences(n, k, arr)
    else:
        print("Datele nu corespund restricțiilor impuse.")




</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==  
== Explicatie Rezolvare ==  
Funcția kSecventa(n, k, v) primește ca argumente lungimea vectorului n, numărul de secvențe k și vectorul v.
Funcția validate_input primește valorile citite de la tastatură și verifică dacă îndeplinesc restricțiile impuse de problemă.
Inițializăm variabila secv_len cu lungimea secvențelor, adică n // k.
Funcția check_sequences primește valorile validate și verifică existența a două secvențe identice în vectorul dat.
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.
Se parcurg secvențele de lungime n/k din vector, verificându-se dacă au mai fost întâlnite.
Dacă găsim două secvențe identice, afișăm numerele lor de ordine și opri căutarea cu return.
Dacă se găsește o secvență identică, se afișează numerele de ordine ale celor două secvențe și se returnează din funcție.
Dacă nu găsim nicio pereche de secvențe identice, afișăm "NU".
Dacă nu se găsește nicio secvență identică, se afișează mesajul "NU".
În funcția main, citim n și k de la tastatură și verificăm dacă datele introduse corespund restricțiilor impuse.
Dacă datele nu respectă restricțiile, se afișează mesajul corespunzător și se returnează din funcție.
Dacă datele sunt introduse corect, citim vectorul v și apelăm funcția kSecventa(n, k, v) pentru a rezolva problema.
Funcția check_sequences este apelată în cadrul blocului if __name__ == "__main__", unde se citesc datele de intrare."__main__", unde se citesc datele de intrare.

Revision as of 19:55, 14 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.


Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 0521 - kSecventa

def validate_input(n, k, arr):

   if k >= n:
       return False
   if n % k != 0:
       return False
   if max(arr) > 1000:
       return False
   return True


def find_identical_sequences(n, k, arr):

   if not validate_input(n, k, arr):
       print("Datele nu corespund restricțiilor impuse.")
       return
   seq_dict = {}
   for i in range(n // k):
       seq = tuple(arr[i * k: (i + 1) * k])
       if seq in seq_dict:
           print(seq_dict[seq], i + 1)
           return
       else:
           seq_dict[seq] = i + 1
   print("NU")


if __name__ == "__main__":

   n, k = map(int, input().split())
   arr = list(map(int, input().split()))
   if validate_input(n, k, arr):
       print("Datele sunt introduse corect.")
       find_identical_sequences(n, k, arr)
   else:
       print("Datele nu corespund restricțiilor impuse.")


</syntaxhighlight>

Explicatie Rezolvare

Funcția validate_input primește valorile citite de la tastatură și verifică dacă îndeplinesc restricțiile impuse de problemă. Funcția check_sequences primește valorile validate și verifică existența a două secvențe identice în vectorul dat. Se parcurg secvențele de lungime n/k din vector, verificându-se dacă au mai fost întâlnite. Dacă se găsește o secvență identică, se afișează numerele de ordine ale celor două secvențe și se returnează din funcție. Dacă nu se găsește nicio secvență identică, se afișează mesajul "NU". Dacă datele nu respectă restricțiile, se afișează mesajul corespunzător și se returnează din funcție. Funcția check_sequences este apelată în cadrul blocului if __name__ == "__main__", unde se citesc datele de intrare."__main__", unde se citesc datele de intrare.