Stonehenge – Épreuve régionale 2016

Énoncé¶

Les Prolosaures construisent Stonehenge, un monument formé de dolmens et de menhirs disposés en cercle suivant un motif très précis, et régulièrement espacés.

La veille de l'inauguration, le chef architecte Prolosaure se rend compte que les constructeurs ont lu les plans à l'envers ! En effet, ceux-ci donnent les dolmens et menhirs à placer dans le sens horaire, en commençant par celui le plus au nord, mais les constructeurs les ont posés dans le sens antihoraire.

Le chef architecte appelle donc tous les travailleurs à rectifier cette erreur au plus vite. Heureusement, il y a des emplacements où les rochers sont déjà correctement posés, et ce n'est donc pas la peine d'y toucher.

Votre tâche est de déterminer le nombre de dolmens et de menhirs à déplacer.

Entrée¶

L'entrée comprendra :

• sur la première ligne, le nombre total n de dolmens et de menhirs composant Stonehenge ;
• sur la deuxième ligne, le plan de Stonehenge sous forme d'une chaîne de n caractères qui sont soit des dolmens D, soit des menhirs M. Le premier se situe au point le plus au nord du cercle de pierres. Les suivants sont donnés dans le sens horaire.

Sortie¶

Vous afficherez en sortie le nombre de dolmens et de menhirs qui doivent être déplacés.

Contraintes¶

• 3 ≤ n ≤ 10 000