# Problem Statement

Hero has an infinite periodic string t. You are given the string s that is the period of Hero's string. For example, if s = "abc", Hero's actual string is t = "abcabcabcabc…" Let n be the length of string s. Hero is now going to use the infinite string t to generate a new n-character string by doing the following steps: He will choose an offset: a non-negative integer x. He will choose the length of a step: a prime number p that is less than n. The new string will consists of the first n characters we can read in the string t if we start at the index x and after each character we move p positions to the right. Formally, Hero's new string will consist of the following characters, in order: t[x], t[x + p], t[x + 2p], …, t[x + (n-1)p]. Find and return the lexicographically smallest string Hero can produce.

# Definition

Class: RingLex Method: getmin Parameters: string Returns: string Method signature: string getmin(string s) (be sure your method is public)

# Limits

Time limit (s): 2.000 Memory limit (MB): 256 Stack limit (MB): 256

# Notes

• Given two distinct strings of the same length, the lexicographically smaller one is the one that has a smaller character at the first position where they differ.
• A positive integer p is a prime if it has exactly two distinct divisors: 1 and p. Note that the number 1 is not a prime.

# Constraints

• s will contain between 3 and 50 characters, inclusive.
• Each character in s will be between 'a' and 'z', inclusive.

# Examples

```0)
"cba"
Returns: "abc"
Hero should choose the offset x=2 and the step p=2. The resulting string is t[2]+t[4]+t[6] = 'a'+'b'+'c' = "abc".
1)
"acb"
Returns: "abc"
Here, Hero should choose x=0 and p=2.
2)
"abacaba"
Returns: "aaaabcb"
3)
"aaabb"
Returns: "aabab"
4)
"azzzabbb"
Returns: "abazabaz"
Note that Hero cannot choose x=0 and p=4, because 4 is not a prime number.
5)
"abbaac"
Returns: "aaaaaa"
6)
"fsdifyhsoe"
Returns: "dehifsfsoy"```

# 代码

```#include <iostream>
#include <set>
using namespace std;
bool is_prime(int val)
{
for(int i = 2; i < val; i++)
{
if(0 == val % i)
{
return false;
}
}
return true;
}
class RingLex
{
public:
string getmin(string s)
{
int len = s.length();
set<string> res_set;
for(int x = 0; x < len; x++)
{
for(int p = 1; p < len; p++)
{
if(is_prime(p))
{
string newstr = "";
for(int step = 0; step < len; step++)
{
newstr += s[(step * p + x) % len];
}
res_set.insert(newstr);
}
}
}
return (*final_set.begin());
}
};
int main()
{
RingLex r;
cout << r.getmin("cba");
return 0;
```

Codeforces & TopCoder QQ交流群：648202993 更多内容请关注微信公众号

243 篇文章47 人订阅

0 条评论

## 相关文章

36550

17510

25630

9920

### 3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家

3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家 Time Limit: 1 Sec  Memory...

379110

### java开发_数字转换汉语中人民币的大写_完整版

======================================================

46630

### BZOJ 3098: Hash Killer II(新生必做的水题)

3098: Hash Killer II Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge S...

28970

### Typescript 查缺补漏

Types Casting: let input = xxx as HTMLInputElement; let input = <HTMLElement>xxx...

23030

11320

8830