二面体群

题目描述

考虑在一个单位圆周上的 n个点,n个点的标号为K=0,1,……n-1。初始的时候K相对于X轴的角度为:360 * k / n 度,这里的角度是相对于X轴的逆时针角度。我们将在这组点上运行2 种不同类型的操作:

1.顺时针旋转360/n度

2.相对于X轴的映射

对于给定的操作序列,如果结果相同,我们只对最短的操作序列感兴趣。结果相同是指对于不同的操作序列,最后的操作结果中每一个单一点的位置都是一样的。

操作序列以字符串的形式给出,该字符串中只含有字母“r”和“m”。 “r”代表顺时针旋转,“m”代表单独映射(到右边并且对称)。字符串中如果有多个字母连续出现要简写成<字母><数字>的形式,为了方便起见,字母如果单独出现也写成这种形式。如"rrmrrrrrrrrrrrr"可以写成"r2 m1 r12",每个操作序列一行。

输入输出格式

输入格式:

输入共两行。

第一行共一个数N,表示圆周上点的个数。

第二行为按上面的方式缩写的操作序列,所有的数字都是正整数,并且小于108 。在输入文件中没有空行,并且每一行的字符个数都小于100000。

输出格式:

输出共一行。

第一行输出最短操作序列。若无需操作则什么都不输出。

输入输出样例

输入样例#1: 复制
54
r218 m3 r1
输出样例#1: 复制
r1 m1

说明

[数据范围]

100%的数据,3 <= N <= 108

#笔试题目#
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务