0854 - Secvente1: Diferență între versiuni
Fără descriere a modificării |
Fără descriere a modificării |
||
Linia 7: | Linia 7: | ||
== Date de ieșire == | == 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 == | == Restricţii şi precizări == | ||
Linia 17: | Linia 18: | ||
: 4 3 4 9 9 1 8 | : 4 3 4 9 9 1 8 | ||
; Ieșire | ; Ieșire | ||
: Datele nu corespund restricțiilor impuse. | |||
: 2 | : 2 | ||
Linia 24: | Linia 26: | ||
<syntaxhighlight lang="python" line> | <syntaxhighlight lang="python" line> | ||
# 0854 - Secvente1 | # 0854 - Secvente1 | ||
def citire(): | def citire(): | ||
n, k = map(int, input().split()) | n, k = map(int, input().split()) | ||
Linia 48: | Linia 51: | ||
if __name__ == '__main__': | if __name__ == '__main__': | ||
n, k, sir = citire() | n, k, sir = citire() | ||
rez = rezolvare(n, k, sir) | rez = rezolvare(n, k, sir) | ||
if rez != -1: | |||
print( | print("Datele sunt introduse corect.") | ||
print(rez) | |||
else: | |||
print("Datele nu corespund restricțiilor impuse.") | |||
</syntaxhighlight> | </syntaxhighlight> |
Versiunea de la data 27 aprilie 2023 18:21
Sursa: 0854 - Secvente1
Cerinţa
Se dă un șir cu n elemente, numere naturale și un număr k. Determinați numărul minim de secvențe disjuncte în care trebuie împărțit șirul astfel încât fiecare element al șirului să aparțină unei secvențe și fiecare secvență să conțină cel mult k elemente impare.
Date de intrare
Programul citește de la tastatură numerele n k, iar apoi cele n elemente ale șirului
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 ≤ 100.000
- cele n numere citite vor fi mai mici decât 1.000.000.000
Exemplu
- Intrare
- 7 2
- 4 3 4 9 9 1 8
- Ieșire
- Datele nu corespund restricțiilor impuse.
- 2
Rezolvare
Rezolvare ver. 1
# 0854 - Secvente1
def citire():
n, k = map(int, input().split())
sir = list(map(int, input().split()))
return n, k, sir
def rezolvare(n, k, sir):
secventa = []
secvente = 0
for i in range(n):
if sir[i] % 2 == 0:
continue # Ignoram elementele pare
if len(secventa) == 0 or len(secventa[-1]) == k:
secventa.append([sir[i]]) # Cream o secventa noua
secvente += 1
else:
secventa[-1].append(sir[i]) # Adaugam elementul la ultima secventa
return secvente
def validare(secvente, rezultat):
assert secvente == rezultat, f"Secvente: {secvente}, Rezultat asteptat: {rezultat}"
if __name__ == '__main__':
n, k, sir = citire()
rez = rezolvare(n, k, sir)
if rez != -1:
print("Datele sunt introduse corect.")
print(rez)
else:
print("Datele nu corespund restricțiilor impuse.")
Expliacatie Rezolvare
Am definit mai întâi funcția citire() care citește numerele de la tastatură și returnează cele trei valori sub forma unei tuple. Funcția rezolvare() primește cele trei valori citite și calculează numărul minim de secvențe necesare. Iterăm prin șir și construim secvențe de elemente impare care au cel mult k elemente. Pentru fiecare secvență, verificăm dacă mai putem adăuga elemente impare la ea sau trebuie să începem o secvență nouă. Incrementăm un contor de secvențe la fiecare început de secvență. Funcția validare() compară rezultatul obținut cu cel așteptat și aruncă o excepție în cazul în care nu se potrivește. În final, am adăugat un test pentru a verifica funcția rezolvare() și am afișat rezultatul.