Stonehenge – Regional event 2016

Level 2

É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

Runtime constraints

Maximum memory usage
500 kilobytes
Maximum execution time
100 milliseconds

Input/output samples

Sample input
5
DDMDM
Sample output
4
Note

Les dolmens et menhirs sont dessinés ci-dessous avec des carrés bleus et des triangles rouges respectivement.

À gauche, la disposition indiquée par le plan ; à droite, l'arrangement dans le mauvais sens par les constructeurs.

Seul le dolmen au nord ne bouge pas.

Sample input
6
MDDDMD
Sample output
2
Note

Le menhir au sud-ouest doit être échangé avec le dolmen au sud-est.

Submit your solution

You have to register or log in to be able to submit your solution.