当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

2937:Dihedral Groups

Special Judge 特殊评判
题目描述

Consider n points on a unit circle with numbers k = 0, 1, …, n − 1. Initially point k makes an angle of 360 · k ⁄ n degrees to the x-axis, measured in counter-clockwise direction. We are going to perform two different kind of operations on that set of points:

  • rotation by 360 ⁄ n degrees in clockwise direction
  • reflection with respect to the x-axis

The following picture shows an example of these operations:

Given a sequence of operations, we are interested in the shortest sequence of operations which gives the same result, i.e., the position of every single point is the same after performing either of those sequences of operations.

The sequence is given as a string consisting of the characters ‘r’ and ‘m’ which represent clockwise rotation and reflection respectively (“to the right” and “mirror”). Multiple consecutive occurrences of the same character are collected into the representation <character><number>, and for convenience this will also be done for single occurrences. So “rrmrrrrrrrrrrrr” will be abbreviated to “r2 m1 r12”. The representations of different operations are always separated by a single space.

输入解释

The input file consists of several test cases. Each test case starts with a line containing n (3 ≤ n ≤ 108), the number of points. The second line of each test case consists of an abbreviated sequence of operations as described above. All numbers will be positive and less than 108. There will be no empty line in the input file, and no line will contain more than 100000 characters. The last test case is followed by a line containing 0.

输出解释

For each test case print one line containing the abbreviated format of the sequence with the minimum number of operations which results in the same configuration of points as the input sequence. In case of multiple optimal solutions, print any solution.

输入样例
4
r2
100
m1 r100 m1
54
r218 m3 r1
0
输出样例
r2

r1 m1

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 Ulm Local 2006

源链接: POJ-2937

最后修改于 2020-10-29T06:48:01+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2000 65536