Joseph Marmotte – Épreuve régionale 2025

Niveau 3 ⋅ Validation weight: 20%

Énoncé

Arrivé au point de rencontre indiqué par la lettre, il rencontre alors enfin son auteur. Quelle surprise ! Il s'agit du dirigeant de la ville lui-même, Joseph Martial !

Le dirigeant explique alors qu'il est lui aussi au courant des manigances qui se produisent dans la ville, et compte bien nous aider à les faire cesser. Notre objectif est maintenant de trouver la salle de contrôle où les dispositifs doivent sûrement se trouver.

Le dirigeant suspecte un garde de la ville, Joseph Marmotte, d'être affilié à ce complot. Après l'avoir convoqué, Joseph Marmotte indique bien vouloir nous donner des informations sur la position de la tour de contrôle en échange d'un peu d'aide.

Joseph Marmotte a un emploi du temps bien chargé. Chaque heure, pour les $N$ prochaines heures, il est soit prévu que Joseph travaille (A), soit qu'il se repose (B).

Heureusement, Joseph Marmotte s'est récemment vu attribuer $K$ heures de repos supplémentaires ! Alors, au plus $K$ fois, Joseph peut soit :

  • Remplacer l'heure de travail (A) prévue le plus tard dans son emploi du temps par une heure de repos (B);
  • Remplacer l'heure de travail (A) prévue le plus tôt dans son emploi du temps par une heure de repos (B).

Cependant, s'il y a bien une chose que Joseph Marmotte déteste, c'est de devoir constamment changer entre période de repos et période de travail.

Aidez Joseph Marmotte à trouver une stratégie pour minimiser le nombre de changements, c'est-à-dire, d'heures avec une activité prévue différente de l'heure précédente.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre d'heures dans l'emploi du temps de Joseph.
  • Sur la ligne suivante, un entier : K, le nombre d'heures de repos supplémentaires attribuées à Joseph.
  • Sur la ligne suivante, une liste de N caractères juxtaposés : L, l'emploi du temps actuel de Joseph.

Sortie

Afficher, sur une ligne, le nombre minimum de changements possible à obtenir après avoir effectué jusqu'à $K$ opérations autorisées.

Contraintes

  • $1 \le N \le 50$
  • $0 \le K \le 20$

Contraintes de performance

  • $1 \le N \le 1\,000\,000$
  • $1 \le K \le 10\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
10
1
AABBBBBBAB
Exemple de sortie
1
Commentaire

Ici, Joseph Marmotte a un emploi du temps prévu sur 10 heures, et peut effectuer une modification entre changer la dernière heure de travail en heure de repos, ou changer la première heure de travail en heure de repos.

En changeant la dernière heure de travail en heure de repos, son emploi du temps devient AABBBBBBBB, qui ne contient plus qu'un seul changement. Il n'est pas possible d'obtenir moins de changements, la réponse est donc 1.

Exemple d'entrée
16
3
ABAAABABABAAABAA
Exemple de sortie
8
Commentaire

Ici, Joseph Marmotte a un emploi du temps prévu sur 16 heures, et peut, jusqu'à trois fois, changer le dernier A en B, ou changer le premier A en B.

En changeant une fois la première heure de travail en heure de repos, et en changeant deux fois la dernière heure de travail en heure de repos, Joseph Marmotte peut parvenir à obtenir l'emploi du temps suivant : BBAAABABABAAABBB, qui ne comporte que 8 changements.

Il n'est pas possible d'obtenir moins de changements, la solution attendue est donc 8.