Considérons un polygone $P$ ayant des côtés horizontaux et verticaux et $N$ sommets. Ses côtés ne peuvent se rencontrer qu’à leurs extrémités, et exactement deux extrémités de côtés se rejoignent en chaque sommet. En parcourant les côtés de $P$ dans le sens inverse des aiguilles d’une montre, on tourne à gauche ou à droite à chaque sommet. Notons un virage à gauche par $L$ et à droite par $R$. Une chaîne de $L$ et de $R$ représente alors le polygone. Par exemple, le polygone de la figure 1 est représenté par

$LLRLLRRLLRLLRLLRRLLR$

Pour représenter un polygone par une chaîne, on commence toujours à l’extrémité supérieure de son côté le plus à gauche. Ce caractère est toujours $L$.

Figures 1 et 2

Un polygone représenté par la chaîne donnée doit respecter la condition suivante : pour toute droite verticale $V$, il existe au plus deux intersections de $V$ avec l’intérieur des côtés horizontaux du polygone (sans leurs extrémités).

Pour un polygone $P$, notons $B(P)$ le plus petit rectangle à côtés horizontaux et verticaux contenant $P$. Il est déterminé par les droites verticales et horizontales coïncidant avec les côtés les plus à gauche, à droite, en haut et en bas de $P$ (figure 2).

Étant donnée une chaîne de longueur $N$ composée de $L$ et de $R$, on dessine un polygone $P$ représenté par cette chaîne et respectant la condition ci-dessus. La longueur de chaque côté de $P$ doit être entière. Écrivez un programme minimisant l’aire de $B(P)$ et affichant ce minimum.

Vous devez implémenter la fonction suivante pour le programme d’évaluation.

int polygon(string S);

La fonction reçoit une chaîne $S$ de longueur $N$, dont chaque caractère est $L$ ou $R$. Parmi les polygones $P$ représentés par $S$, trouvez-en un minimisant l’aire de $B(P)$ et renvoyez cette aire.

Détails d'implémentation

Soumettez exactement un fichier nommé polygon.c ou polygon.cpp. Il doit implémenter la fonction suivante.

int polygon(string S);

La fonction doit se comporter comme décrit ci-dessus. Vous pouvez créer d’autres fonctions pour un usage interne. Le code soumis ne doit pas effectuer d’entrées/sorties ni accéder à d’autres fichiers.

Programme d’évaluation d’exemple

Le programme d’évaluation fourni lit l’entrée au format suivant.

• Ligne 1 : $N$ (la longueur de la chaîne).

• Ligne 2 : une chaîne $c_1c_2\cdots c_N$ de longueur $N$ ($c_1=L$, et $c_i=L$ ou $R$ pour $2\le i\le N$).

Le programme d’évaluation fourni affiche la valeur renvoyée par polygon.

Contraintes

• La chaîne d’entrée est composée de $L$ et de $R$.

• Il existe toujours au moins un polygone représenté par la chaîne d’entrée qui respecte les conditions ci-dessus.

• $4 \le N \le 800$.

Sous-tâches

1 (20 points)

• $N \le 10$.

2 (36 points)

• $N \le 40$.

3 (21 points)

• $N \le 100$.

4 (73 points)

• Aucune contrainte supplémentaire.

Exemples

Entrée 1

8
LLLRRLLL

Sortie 1

6

Entrée 2

20
LLRLLRRLLRLLRLLRRLLR

Sortie 2

15