0521 - kSecventa: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
Fără descriere a modificării
Linia 6: Linia 6:
Programul citește de la tastatură numerele n și k, iar apoi n numere naturale, reprezentând elementele vectorului.
Programul citește de la tastatură numerele n și k, iar apoi n numere naturale, reprezentând elementele vectorului.
== Date de ieșire ==  
== 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
* 1 ≤ k < n ≤ 1000, k este divizor al lui n
* cele n numere citite vor fi mai mici decât 1000
* cele n numere citite vor fi mai mici decât 1000
Linia 16: Linia 15:
: 3 6 4 7 6 6 6 4 6 7 6 6 4 4 5  
: 3 6 4 7 6 6 6 4 6 7 6 6 4 4 5  
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: 2 4
: 2 4


Linia 23: Linia 23:
# 0521 - kSecventa
# 0521 - kSecventa


def citeste_date_intrare():
def citire_date():
     n, k = map(int, input().split())
     n, k = map(int, input().split())
     x = list(map(int, input().split()))
     x = list(map(int, input().split()))
     return n, k, x
     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):
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__':
if __name__ == '__main__':
     n, k, x = citeste_date_intrare()
     n, k, x = citire_date()
    t = int(input())
     valideaza_datele_de_intrare(n, k, x)
     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)
     print(rezultat)


</syntaxhighlight>
</syntaxhighlight>

Versiunea de la data 27 aprilie 2023 18:04

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

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".

Adus de la „http://wiki.universitas.ro/index.php?title=0521_-_kSecventa&oldid=5032”