Bitstring - Državno (2020)

Submit solution
Points: 40 (partial)
Time limit: 1.0s
Memory limit: 64M
Author:
admin
Problem type
Allowed languages
Assembly, Awk, C, C++, Java, Perl, Python

Državno natjecanje 2020. godine za 1. i 2. razred Srednje Škole - 2. zadatak

Zadan je niz od n znakova iz skupa {0, 1}. Zadan je i prirodan broj k. Potrebno je promijeniti što manje znakova zadanog niza (iz 0 u 1 ili obrnuto) tako da se dobiveni niz može rastaviti na k ili manje blokova (intervala) od kojih svaki sadrži samo znakove 0 ili samo znakove 1.

ULAZNI PODACI

U prvom su retku prirodni brojevi n i k (1 ≤ k ≤ n ≤ 200 000). U drugom je retku zadani niz od n znakova.

IZLAZNI PODACI

U jedini redak ispišite traženi minimalan broj promjena.

PRIMJERI TEST PODATAKA

ulaz
10 1
1000100011
izlaz
4
ulaz
6 2
010110
izlaz
2

Pojašnjenje: u prvom primjeru treba promijeniti četiri jedinice i dobiti niz 0000000000. U drugom primjeru možemo promijeniti dva znaka na više načina, npr. tako da dobijemo niz 000111 ili 111110 ili 011111.

Comments


  • 0
    guess  commented on Jan. 28, 2025, 8:04 a.m.

    how is this for 1. and 2. grade


  • 0
    guess  commented on Jan. 28, 2025, 8:00 a.m.

    bruh