CF708A Letters Cyclic Shift 模拟-白红宇

CF708A Letters Cyclic Shift 模拟

阅读量：6469 次

发布时间：2019-06-23

本文共 3075 字，大约阅读时间需要 10 分钟。

You are given a non-empty string s consisting of lowercase English letters. You have to pick exactly one non-empty substring of s and shift all its letters 'z' $\text{[math]}$ 'y' $\text{[math]}$ 'x' $\text{[math]}$ 'b' $\text{[math]}$ 'a' $\text{[math]}$ 'z'. In other words, each character is replaced with the previous character of English alphabet and 'a' is replaced with 'z'.

What is the lexicographically minimum string that can be obtained from s by performing this shift exactly once?

Input

The only line of the input contains the string s (1 ≤ |s| ≤ 100 000) consisting of lowercase English letters.

Output

Print the lexicographically minimum string that can be obtained from s by shifting letters of exactly one non-empty substring.

Examples

Input

Copy

codeforces

Output

Copy

bncdenqbdr

Input

Copy

abacaba

Output

Copy

aaacaba

Note

String s is lexicographically smaller than some other string t of the same length if there exists some 1 ≤ i ≤ |s|, such that s₁ = t₁, s₂ = t₂, ..., s_i - 1 = t_i - 1, and s_i < t_i.

唯一的坑点就是aaaaaa...时，最后一个要该为z；

因为题目说明不能为空子串；

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      //#include
                      
                       //#pragma GCC optimize(2)using namespace std;#define maxn 1000005#define inf 0x3f3f3f3f//#define INF 1e18#define rdint(x) scanf("%d",&x)#define rdllt(x) scanf("%lld",&x)#define rdult(x) scanf("%lu",&x)#define rdlf(x) scanf("%lf",&x)#define rdstr(x) scanf("%s",x)typedef long long ll;typedef unsigned long long ull;typedef unsigned int U;#define ms(x) memset((x),0,sizeof(x))const long long int mod = 1e9 + 7;#define Mod 1000000000#define sq(x) (x)*(x)#define eps 1e-3typedef pair
                       
                         pii;#define pi acos(-1.0)const int N = 1005;#define REP(i,n) for(int i=0;i<(n);i++)typedef pair
                        
                          pii;inline ll rd() { ll x = 0; char c = getchar(); bool f = false; while (!isdigit(c)) { if (c == '-') f = true; c = getchar(); } while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return f ? -x : x;}ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b);}ll sqr(ll x) { return x * x; }/*ll ans;ll exgcd(ll a, ll b, ll &x, ll &y) { if (!b) { x = 1; y = 0; return a; } ans = exgcd(b, a%b, x, y); ll t = x; x = y; y = t - a / b * y; return ans;}*/char ch[30];map
                         
                          Map;int main(){ //ios::sync_with_stdio(0); for (int i = 1; i <= 26; i++)ch[i] = 'a' + i - 1; ch[0] = 'z'; for (int i = 1; i <= 26; i++)Map[ch[i]] = ch[i - 1]; string s; cin >> s; int i; int len = s.length(); int pos = 0; int fg = 0; int cnt = 0; for (int i = 0; i < len; i++) { if (s[i] == 'a')continue; else { fg = 1; break; } } if (fg == 0) { for (int i = 0; i < len - 1; i++)cout << s[i]; cout << 'z' << endl; return 0; } fg = 0; for (i = 0; i < len; i++) { if (Map[s[i]] < s[i]) { cout << Map[s[i]]; fg = 1; cnt++; } else { if (fg == 0) { cout << s[i]; continue; } else if (fg) { pos = i; break; } } } if (i < len) { if (fg)for (int i = pos; i < len; i++)cout << s[i]; } cout << endl; return 0;}

转载于:https://www.cnblogs.com/zxyqzy/p/10127187.html

你可能感兴趣的文章