#P2250. 二面体群
二面体群
题目描述
考虑在一个单位圆周上的 个点, 个点的标号为 。初始的时候 相对于 X 轴的角度为 度,这里的角度是相对于 X 轴的逆时针角度。我们将在这组点上运行 2 种不同类型的操作:
- 顺时针旋转 度
- 相对于 X 轴的映射
对于给定的操作序列,如果结果相同,我们只对最短的操作序列感兴趣。结果相同是指对于不同的操作序列,最后的操作结果中每一个单一点的位置都是一样的。
操作序列以字符串的形式给出,该字符串中只含有字母 r
和 m
。r
代表顺时针旋转,m
代表单独映射(到右边并且对称)。字符串中如果有多个字母连续出现要简写成 <字母><数字>
的形式,为了方便起见,字母如果单独出现也写成这种形式。如 rrmrrrrrrrrrrrr
可以写成 r2 m1 r12
,每个操作序列一行。
输入格式
输入共两行。
第一行一个数 ,表示圆周上点的个数。
第二行为按上面的方式缩写的操作序列,所有的数字都是正整数,并且小于 。在输入文件中没有空行,并且每一行的字符个数都小于 。
输出格式
输出最短操作序列。若无需操作则什么都不输出。
54
r218 m3 r1
r1 m1
提示
的数据满足 。