0854 - Secvente1: Diferență între versiuni
De la Universitas MediaWiki
(Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/71/reducere 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 ș...) |
Fără descriere a modificării |
||
Linia 1: | Linia 1: | ||
Sursa: [https://www.pbinfo.ro/probleme/ | Sursa: [https://www.pbinfo.ro/probleme/854/secvente1 0854 - Secvente1] | ||
---- | ---- | ||
== Cerinţa == | == Cerinţa == |
Versiunea de la data 21 martie 2023 21:35
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
Programul va afișa pe ecran numărul minim de secvențe C.
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
- 2
Rezolvare
Rezolvare ver. 1
# 0854 - Secvente1
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_secvente = 0
num_impares_curent = 0
for i in range(n):
if a[i] % 2 == 1 and num_impares_curent < k:
num_impares_curent += 1
else:
num_secvente += 1
num_impares_curent = 1 if a[i] % 2 == 1 else 0
print(num_secvente + (num_impares_curent > 0))