Facebook
From Chartreuse Stork, 3 Days ago, written in C++.
Embed
Download Paste or View Raw
Hits: 75
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. inline int toInt ( char c ) { return c - '0'; }
  4. inline char toChar ( int i ) { return i + '0'; }
  5.  
  6. string rlz ( const string& s ) {
  7.         int i = 0;
  8.         while ( i < s.size() && s[i] == '0' ) i++;
  9.         if ( i == s.size() ) return "0";
  10.         return s.substr ( i, s.size() - i );
  11. }
  12.  
  13. int compare ( const string& a, const string& b ) {
  14.         if ( a.size() != b.size() )
  15.                 return ( a.size() < b.size() ? -1 : 1 );
  16.         for ( int i = 0; i < int(a.size()); ++i )
  17.                 if ( a[i] != b[i] )
  18.                         return ( a[i] < b[i] ? -1 : 1 );
  19.         return 0;
  20. }
  21.  
  22. string subtract ( const string& a, const string& _b ) {
  23.         assert ( compare(a, _b) >= 0 );
  24.         const int n = a.size();
  25.         string b = string(n - _b.size(), '0') + _b;
  26.         string c ( n, '0' );
  27.         int carry = 0;
  28.         for ( int i = n - 1; i >= 0; --i ) {
  29.                 int dgt = toInt(a[i]) - toInt(b[i]) - carry;
  30.                 carry = 0;
  31.                 if ( dgt < 0 ) { dgt += 10; carry++; }
  32.                 c[i] = toChar(dgt);
  33.         }
  34.         assert ( carry == 0 );
  35.         return rlz ( c );
  36. }
  37.  
  38. string s;
  39. string r;
  40. int n;
  41.  
  42. bool goUpper ( int i, bool eq ) {
  43.         if ( i == n ) {
  44.                 if ( eq ) return false;
  45.                 return true;
  46.         }
  47.         for ( char c = ( eq ? s[i] : '0'); c <= '9'; ++c ) {
  48.                 if ( i > 0 )
  49.                         if ( (toInt(c) - toInt(r[i - 1])) % 2 == 0 )
  50.                                 continue;
  51.                 r[i] = c;
  52.                 if (goUpper(i + 1, (eq && c == s[i]))) {
  53.                         return true;
  54.                 }
  55.         }
  56.  
  57.         return false;
  58. }
  59.  
  60. bool goLower ( int i, bool eq ) {
  61.         if ( i == n ) {
  62.                 if ( eq ) return false;
  63.                 return true;
  64.         }
  65.         for ( char c = ( eq ? s[i] : '9'); c >= '0'; --c ) {
  66.                 if ( i > 0 )
  67.                         if ( (toInt(c) - toInt(r[i - 1])) % 2 == 0 )
  68.                                 continue;
  69.                 r[i] = c;
  70.                 if ( goLower(i + 1, (eq && c == s[i])) )
  71.                         return true;
  72.         }
  73.  
  74.         return false;
  75. }
  76.  
  77. string getUpper ( )
  78. {
  79.         string maxS = "";
  80.         for ( int i = 0; i < n; ++i )
  81.                 maxS += '9' - (i % 2);
  82.         if ( compare(maxS, s) <= 0 ) {
  83.                 string r = "";
  84.                 for ( int i = 0; i < n + 1; ++i )
  85.                         r += toChar(1 - (i % 2));
  86.                 return r;
  87.         }
  88.         assert ( goUpper(0, 1) );
  89.         return r;
  90. }
  91.  
  92. string getLower ( ) {
  93.         assert ( goLower(0, 1) );
  94.         return r;
  95. }
  96.  
  97. int main ( )
  98. {
  99.         cin >> s;
  100.         s = rlz(s);
  101.         r = s;
  102.         n = s.size();
  103.         if ( s == "0" ) cout << getUpper() << endl;
  104.         else {
  105.                 string hi = getUpper();
  106.                 string lo = getLower();
  107.                 int diff = compare ( subtract(hi, s), subtract(s, lo) );
  108.                 if ( diff == 0 ) cout << lo << " " << hi << endl;
  109.                 else if ( diff == -1 ) cout << hi << endl;
  110.                 else cout << lo << endl;
  111.         }
  112.         return 0;
  113. }
  114.