[UVA][數學] 11051 - Dihedral groups
University of Ulm Local Contest
Dihedral groups
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.
Input Specification
The input 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, and no line will contain more than 100000 characters. The last test case is followed by a line containing 0.
Output Specification
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
Note that the second line of the sample output is a blank line
題目描述：
有 n 個點平均分布在圓上，操作有兩種
1) 順時針轉動 360/n 度
2) 對著 x 軸做翻轉(反射)
給一些操作指定進行移動，將這些指定重新表示成最短的操作指令
題目解法：
追蹤一個點，並且記錄現在的操作 2 的次數，因為這會造成當下指定在實際不考慮 2 是順逆時針的操作。
而在求最短操作指令的時候，用 mod 運算，再討論先翻後翻的情況哪個比較短。
#include <stdio.h>
#include <iostream>
#include <sstream>
using namespace std;
int main() {
int n, x;
char s[100005];
string token;
while(scanf("%d", &n) == 1 && n) {
while(getchar() != '\n');
gets(s);
stringstream sin(s);
int rotate = 0, reflect = 1;
while(sin >> token) {
if(token[0] == 'r') {
sscanf(token.c_str(), "r%d", &x);
x = x%n;
rotate = (rotate + (reflect == -1 ? -x : x) + n)%n;
} else {
sscanf(token.c_str(), "m%d", &x);
reflect = x%2 ? -reflect : reflect;
}
}
//printf("%d %d\n", rotate, reflect);
if(rotate == 0) {
if(reflect == -1)
puts("m1");
else
puts("");
} else {
if(reflect == 1) {
if(rotate < n - rotate + 2)
printf("r%d\n", rotate);
else
printf("m1 r%d m1\n", n - rotate);
} else {
if(rotate < n - rotate + 1)
printf("r%d m1\n", rotate);
else
printf("m1 r%d\n", n - rotate);
}
}
}
return 0;
}