Flip a coin! – Épreuve régionale 2021

Énoncé¶

Un des jeux les plus connus chez les dieux grecs du concours Prologin est le "flip a coin!". Imaginez une rangée de pièces alignées, posées soit sur le côté face, soit sur le côté pile, de façon aléatoire ; le but de ce jeu est de calculer la longueur maximale d'une séquence de pièces dont le côté face est visible, en considérant qu'on peut retourner une des pièces de la rangée pour voir son côté face. Attention, on ne peut retourner qu’une pièce, il est impossible d'en retourner plus ou de changer l'ordre des pièces !

Le dieu Valonysos qui se fait toujours battre par les autres décide de se poser un jour, et de réfléchir au problème une bonne fois pour toutes, afin d'établir une méthode pour gagner rapidement et le plus souvent possible.

Aidez Valonysos à trouver un algorithme capable de résoudre son problème à tous les coups, pour qu'il soit certain de gagner la prochaine fois !

Entrée¶

L’entrée contiendra :

• Sur la première ligne, un entier : nombre_de_pieces, le nombre de pièces dans le jeu.
• Sur la ligne suivante, une liste nombre_de_pieces de caractères juxtaposés : rangee_de_pieces, description de la rangée de pièces dans le jeu.

Sortie¶

Afficher la longueur maximale de la séquence de pièces côté face que l'on puisse obtenir.

Contraintes¶

• $1 \le \text{nombre_de_pieces} \le 100$