CSES - Datatähti 2022 loppu - Peli
  • Language:
  • Time limit: 2.00 s
  • Memory limit: 512 MB
Pelaat peliä, joka muodostuu $n$ huoneesta. Kuljet huoneiden läpi vasemmalta oikealle. Jokaisessa huoneessa on kirjain A, B tai C.

Sinulla on pussi, johon mahtuu enintään $k$ kirjainta. Jokaisessa huoneessa voit laittaa kirjaimen pussiin, jos pussissa on tilaa. Jos pussissa on samaan aikaan kirjaimet A, B ja C, nämä kirjaimet katoavat ja saat yhden pisteen.

Montako pistettä voit saada, jos pelaat optimaalisesti?

Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $k$: huoneiden määrä ja pussin koko.

Seuraavalla rivillä on merkkijono, jossa on $n$ merkkiä: huoneiden kirjaimet vasemmalta oikealle.

Tuloste

Tulosta yksi kokonaisluku: suurin mahdollinen pistemäärä.

Esimerkki

Syöte:
8 4
ABABCAAC


Tuloste:
2

Osatehtävä 1 (11 pistettä)
  • $1 \le n \le 10^5$
  • $1 \le k \le 3$
Osatehtävä 2 (31 pistettä)
  • $1 \le n \le 10^5$
  • $1 \le k \le 10$
Osatehtävä 3 (58 pistettä)
  • $1 \le n \le 10^5$
  • $1 \le k \le 50$