0304 - Secvente: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 8: Line 8:


== Date de ieșire ==  
== Date de ieșire ==  
Fişierul de ieşire secvente.out va conţine pe prima linie numărul C, reprezentând numărul de secvenţe cu elementele ordonate crescător din şirul dat.
Fişierul de ieşire secvente.out va conţine 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 ==
== Restricţii şi precizări ==
* 1 ≤ n ≤ 1000
* 1 ≤ n ≤ 1000
Line 19: Line 21:
: 10 12 14
: 10 12 14
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele sunt introduse correct.
: 3
: 3


Line 26: Line 30:
# 0304 - Secvente
# 0304 - Secvente


def citeste_date_intrare():
def citire_date():
     n = int(input())
     n = int(input())
     sir = []
     v = list(map(int, input().split()))
    for i in range(n):
     return n, v
        sir.append(int(input()))
     return sir


def numara_secvente_crescatoare(sir):
def secvente_crescatoare(n, v):
     numar_secvente = 0
     numar_secvente = 0
    lungime_maxima = 1
     for i in range(n):
    lungime_curenta = 1
         j = i + 1
     for i in range(1, len(sir)):
        while j < n and v[j] > v[j-1]:
         if sir[i] >= sir[i-1]:
             j += 1
             lungime_curenta += 1
         numar_secvente += j - i
         else:
         i = j - 1
            if lungime_curenta > lungime_maxima:
                lungime_maxima = lungime_curenta
                numar_secvente = 1
            elif lungime_curenta == lungime_maxima:
                numar_secvente += 1
            lungime_curenta = 1
    if lungime_curenta > lungime_maxima:
         lungime_maxima = lungime_curenta
        numar_secvente = 1
    elif lungime_curenta == lungime_maxima:
        numar_secvente += 1
     return numar_secvente
     return numar_secvente


def valideaza(sir, numar_secvente):
def validare(n, v):
     assert len(sir) > 0
     if len(v) != n:
     assert numar_secvente >= 0
        return False
    for x in v:
        if x < 0 or x > 9999:
            return False
    return True
 
if __name__ == '__main__':
     n, v = citire_date()
    if validare(n, v):
        print("Datele sunt introduse corect.")
        print(secvente_crescatoare(n, v))
    else:
        print("Datele nu corespund restricțiilor impuse.")


if __name__ == "__main__":
    sir = citeste_date_intrare()
    numar_secvente = numara_secvente_crescatoare(sir)
    valideaza(sir, numar_secvente)
    print(numar_secvente)


</syntaxhighlight>
</syntaxhighlight>

Revision as of 18:40, 27 April 2023

Sursa: 0304 - Secvente


Cerinţa

Se dă un şir format din n elemente, numere naturale. Determinaţi câte secvenţe maximale cu elementele ordonate crescător conţine şirul.

Date de intrare

Fişierul de intrare secvente.in conţine pe prima linie numărul n; urmează cele n elemente ale vectorului, dispuse pe mai multe linii şi separate prin spaţii.

Date de ieșire

Fişierul de ieşire secvente.out va conţine 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 ≤ n ≤ 1000
  • elementele şirului vor avea cel mult 4 cifre
  • o secvență cu elemente ordonate crescător este maximală dacă adăugând la secvență încă un element ea nu mai are elementele ordonate crescător

Exemplu

Intrare
8:
12 10 15 17 17
10 12 14
Ieșire
Datele nu corespund restricțiilor impuse.
Datele sunt introduse correct.
3

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 0304 - Secvente

def citire_date():

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

def secvente_crescatoare(n, v):

   numar_secvente = 0
   for i in range(n):
       j = i + 1
       while j < n and v[j] > v[j-1]:
           j += 1
       numar_secvente += j - i
       i = j - 1
   return numar_secvente

def validare(n, v):

   if len(v) != n:
       return False
   for x in v:
       if x < 0 or x > 9999:
           return False
   return True

if __name__ == '__main__':

   n, v = citire_date()
   if validare(n, v):
       print("Datele sunt introduse corect.")
       print(secvente_crescatoare(n, v))
   else:
       print("Datele nu corespund restricțiilor impuse.")


</syntaxhighlight>

Explicatie Rezolvare

Funcția citeste_date_intrare primește datele de intrare de la tastatură și le returnează sub forma unei liste.

Funcția numara_secvente_crescatoare primește lista de numere și numără secvențele maximale cu elemente ordonate crescător din șirul dat. Algoritmul este simplu: parcurgem lista și ținem minte lungimea maximă a unei secvențe cu elemente ordonate crescător și numărul de astfel de secvențe găsite până în acel moment. Când întâlnim un element mai mic decât cel precedent, înseamnă că secvența curentă s-a încheiat, verificăm dacă are lungimea maximă și actualizăm numărul de secvențe dacă e cazul. La final mai facem o verificare dacă ultima secvență a fost maximă.

Funcția valideaza verifică dacă datele de ieșire sunt valide.

În blocul if __name__ == "__main__": citim datele de intrare, apelăm funcția numara_secvente_crescatoare și afișăm rezultatul.