fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <fstream>
  5. #include <sstream>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <map>
  9. #define LOCAL
  10. #ifdef LOCAL
  11. #define cin in
  12. #endif
  13.  
  14. #define FOREACH(i, n) for (typeof(n.begin()) i = n.begin(); i != n.end(); ++i)
  15. #define MEMSET(p, c) memset(p, c, sizeof(p))
  16.  
  17. using namespace std;
  18.  
  19. template < class T,class T2 >
  20. T2 fac(T n)
  21. {
  22.     return n<2?1:fac<T,T2>(n-1)*n;
  23. }
  24.  
  25. template <class T>
  26. T nb_combinaisons(T k,T n)
  27. {
  28.     if(n<k)
  29.         return nb_combinaisons<T>(n,k);
  30.     return fac<T,long long int>(n)/(fac<T,long long int>(n-k)*fac<T,long long int>(k));
  31. }
  32.  
  33. string itoa_2(long long int n)
  34. {
  35.     string s;
  36.     stringstream ss;
  37.     ss<<n;
  38.     ss>>s;
  39.     while(s.size()!=9)
  40.         s='0'+s;
  41.     return s;
  42. }
  43.  
  44.  
  45. int main()
  46. {
  47.     #ifdef LOCAL
  48.         ifstream in("input.txt");
  49.     #endif
  50.    int n,k;
  51.    cin>>n>>k;
  52.    string s;
  53.    cin>>s;
  54.    string s3=s;
  55.    sort(s.begin(),s.end());
  56.    int mini_global=10000000;
  57.    string resultat_mini;
  58.    for(int c=0;c<10;c++)
  59.    {
  60.        string s2=s3;
  61.     int c2;
  62.     for(c2=0;c2<s.size()&&s[c2]<c+'0';c2++);
  63.     int total=abs(s[c2]-'0'-c);
  64.     for(int c3=0;c3<s2.size();c3++)
  65.         if(s2[c3]==s[c2])
  66.         {
  67.             s2[c3]=c+'0';
  68.             break;
  69.         }
  70.  
  71.     int bas=c2-1,haut=c2+1;
  72.     for(c2=0;c2<k-1;c2++)
  73.     {
  74.         if(haut>=s.size()||(bas>=0&&abs(s[bas]-'0'-c)<=abs(s[haut]-'0'-c)))
  75.         {for(int c3=0;c3<s2.size();c3++)if(s2[c3]==s[bas]){
  76.                     s2[c3]=c+'0';break;}
  77.             total+=abs(s[bas]-'0'-c);
  78.             bas--;
  79.         }
  80.         else
  81.         {
  82.             for(int c3=0;c3<s2.size();c3++)
  83.                 if(s2[c3]==s[haut]){
  84.                     s2[c3]=c+'0';break;}
  85.             total+=abs(s[haut]-'0'-c);
  86.             haut++;
  87.         }
  88.     }
  89.     if(mini_global>total)
  90.     {
  91.         mini_global=total;
  92.         resultat_mini=s2;
  93.     }
  94.    }
  95.    cout<<mini_global<<endl<<resultat_mini;
  96. }
  97.  
  98.  
  99.  
  100.  
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘int main()’:
prog.cpp:62: warning: comparison between signed and unsigned integer expressions
prog.cpp:64: warning: comparison between signed and unsigned integer expressions
prog.cpp:74: warning: comparison between signed and unsigned integer expressions
prog.cpp:75: warning: comparison between signed and unsigned integer expressions
prog.cpp:82: warning: comparison between signed and unsigned integer expressions
stdout
copy 
Standard output is empty
https://ideone.com/noArf
language:
C++ (gcc 8.3)
created:
13 years 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!