fork download
copy 
  1. //UID : 833568244 _ Icy _ 
  2. //----------------------------------------------------------------------------------------------------------------------------
  3. //Now, let's write a different kind of poem together ♪
  4. //-----------------------------------------------------------------------------------------------------------------------------
  5. #include<bits/stdc++.h>
  6.  
  7. #define ll long long
  8. #define el cout<<"\n"
  9.  
  10. #define task "letters"
  11.  
  12. using namespace std;
  13. const int N = 2e5 + 7;
  14. const int MOD = 1e9 + 7;
  15. const int LOG = 20;
  16. const int INF = 1e9;
  17. struct cmp{
  18.     bool operator()(const int& a , const int& b){
  19.         return a<b; 
  20.     }
  21. };
  22.  
  23. bool minimize(int &x , int y){
  24.     if(x>y){
  25.         x = y;
  26.         return true;
  27.     }
  28.     return false;
  29. }
  30. int f[N][3][26] , best[N];
  31. pair<int,int> trace[N][3][26];
  32. string s;
  33. void solve(){
  34.     cin>>s;
  35.     int n = s.size();
  36.     for(int i=0;i<N;i++){
  37.         for(int j=0;j<=1;j++){
  38.             for(int c=0;c<26;c++){
  39.                 f[i][j][c] = INF;
  40.             }
  41.         }
  42.     }
  43.     s = ")" + s;
  44.     for(int c=0;c<26;c++){
  45.         f[1][0][c] = abs(c+'A'-s[1]);
  46.     }
  47.     for(int i=1;i<n;i++){
  48.         for(int c=0;c<26;c++){
  49.             if(f[i][0][c] != INF){
  50.                 if(minimize(f[i+1][1][c] , f[i][0][c] + abs(c+'A'-s[i+1]))){
  51.                     trace[i+1][1][c] = {0,c};
  52.                 }
  53.             }
  54.             if(f[i][1][c] != INF){
  55.                 for(int t=0;t<26;t++){
  56.                     if(minimize(f[i+1][t==c][t] , f[i][1][c] + abs(t+'A'-s[i+1]))){
  57.                         trace[i+1][t == c][t] = {1,c};
  58.                     }
  59.                 }
  60.             }
  61.         }
  62.     }
  63.     int res = INF;
  64.     int c = -1 , j = 1;
  65.     for(int i=0;i<26;i++){
  66.         if(minimize(res , f[n][1][i])) c = i;
  67.     }
  68.     for(int i=n;i>=1;i--){
  69.         best[i] = c;
  70.         auto x = trace[i][j][c];
  71.         j = x.first;
  72.         c = x.second;
  73.     }
  74.     cout<<res;
  75.     el;
  76.     for(int i=1;i<=n;i++){
  77.         cout<<char(best[i] + 'A');
  78.     }
  79. }
  80.  
  81. int main(){
  82.     ios_base::sync_with_stdio(0);
  83.     cin.tie(0);
  84.     cout.tie(0);
  85.     if (fopen (task".inp", "r")) {
  86.         freopen (task".inp", "r", stdin);
  87.         freopen (task".out", "w", stdout);
  88.     }
  89.     int T = 1;
  90. //  cin>>T;
  91.     while(T--)
  92.     solve();
  93.     return 0;
  94. }  
  95. //One of us stays in the past, and the other walks toward the future... 
  96. //but our hearts have never been apart ♪
  97.  
Success #stdin #stdout 0.02s 66476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000
https://ideone.com/nEGXv5
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!