Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Dihedral Groups
Description Consider - 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. Input The input file consists of several test cases. Each test case starts with a line containing Output 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. Sample Input 4 r2 100 m1 r100 m1 54 r218 m3 r1 0 Sample Output r2 r1 m1 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator