Advertisement
Guest User

Untitled

a guest
Jun 29th, 2017
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.22 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int nmax = 10;
  8. const long long inf = 1LL << 40;
  9. long long d[nmax + 1][nmax + 1];
  10. long long pref[nmax + 1], p[nmax + 1];
  11. vector< int > c;
  12.  
  13. int main() {
  14.     int k, pare = 0;
  15.     cin >> k;
  16.  
  17.     int aux = k;
  18.     while (aux > 0) {
  19.         c.push_back(aux % 10);
  20.         if (aux % 2 == 0) ++ pare;
  21.         aux /= 10;
  22.     }
  23.     reverse(c.begin(), c.end());
  24.  
  25.     if (pare == 0) {
  26.         cout << "-1\n"; return 0;
  27.     }
  28.  
  29.     pref[ 0 ] = 0;
  30.     for (int i = 1; i <= (int)c.size(); ++ i) {
  31.         pref[ i ] = pref[i - 1] * 10 + c[i - 1];
  32.         p[ i ] = p[i - 1] + (c[i - 1] % 2 == 0);
  33.     }
  34.  
  35.     /// cel mai mare <= k cu mai putin de px cif pare
  36.     d[ 0 ][ 0 ] = 0;
  37.     for (int i = 1; i <= (int)c.size(); ++ i) {
  38.         for (int j = 0; j < pare; ++ j) {
  39.             d[ i ][ j ] = 0;
  40.  
  41.             for (int x = 0; x <= 9; ++ x) {
  42.                 if (x % 2 == 0 && j > 0) {
  43.                     if (d[i - 1][j - 1] * 10 + x < pref[ i ])
  44.                         d[ i ][ j ] = max(d[ i ][ j ], d[i - 1][j - 1] * 10 + x);
  45.  
  46.                     if (x < c[i - 1] && p[i - 1] == j - 1) {
  47.                         d[ i ][ j ] = max(d[ i ][ j ], pref[i - 1] * 10 + x);
  48.                     }
  49.                 } else if (x % 2 == 1) {
  50.                     if (d[i - 1][ j ] * 10 + x < pref[ i ])
  51.                         d[ i ][ j ] = max(d[ i ][ j ], d[i - 1][ j ] * 10 + x);
  52.  
  53.                     if (x < c[i - 1] && p[i - 1] == j) {
  54.                         d[ i ][ j ] = max(d[ i ][ j ], pref[i - 1] * 10 + x);
  55.                     }
  56.                 }
  57.             }
  58.         }
  59.     }
  60.  
  61.     int A = 0;
  62.     for (int i = 0; i < pare; ++ i) {
  63.         A = max(1LL * A, d[ (int)c.size() ][ i ]);
  64.     }
  65.  
  66.     /// cel mai mic >= k cu mai putin de px cif pare
  67.     d[ 0 ][ 0 ] = 0;
  68.     for (int i = 1; i <= pare; ++ i) d[ 0 ][ i ] = inf;
  69.  
  70.     for (int i = 1; i <= (int)c.size(); ++ i) {
  71.         for (int j = 0; j < pare; ++ j) {
  72.             d[ i ][ j ] = inf;
  73.  
  74.             for (int x = 0; x <= 9; ++ x) {
  75.                 if (x % 2 == 0 && j > 0) {
  76.                     if (d[i - 1][j - 1] * 10 + x > pref[ i ]) {
  77.                         d[ i ][ j ] = min(d[ i ][ j ], d[i - 1][j - 1] * 10 + x);
  78.                     }
  79.  
  80.                     if (x > c[i - 1] && p[i - 1] == j - 1) {
  81.                         d[ i ][ j ] = min(d[ i ][ j ], pref[i - 1] * 10 + x);
  82.                     }
  83.                 } else if (x % 2 == 1) {
  84.                     if (d[i - 1][ j ] * 10 + x > pref[ i ]) {
  85.                         d[ i ][ j ] = min(d[ i ][ j ], d[i - 1][ j ] * 10 + x);
  86.                     }
  87.  
  88.                     if (x > c[i - 1] && p[i - 1] == j) {
  89.                         d[ i ][ j ] = min(d[ i ][ j ], pref[i - 1] * 10 + x);
  90.                     }
  91.                 }
  92.             }
  93.         }
  94.     }
  95.  
  96.     long long B = inf;
  97.     for (int i = 0; i < pare; ++ i) {
  98.         B = min(B, d[ (int)c.size() ][ i ]);
  99.     }
  100.  
  101.     if (B == inf) {
  102.         B = 1;
  103.         for (int i = 0; i < pare - 1; ++ i) B *= 10;
  104.         for (int i = 0; i < (int)c.size() - pare + 1; ++ i) B = B * 10 + 1;
  105.     }
  106.  
  107.     cout << 1LL * (k - A) * (B - k) << "\n";
  108.     return 0;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement