Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- const int nmax = 10;
- const long long inf = 1LL << 40;
- long long d[nmax + 1][nmax + 1];
- long long pref[nmax + 1], p[nmax + 1];
- vector< int > c;
- int main() {
- int k, pare = 0;
- cin >> k;
- int aux = k;
- while (aux > 0) {
- c.push_back(aux % 10);
- if (aux % 2 == 0) ++ pare;
- aux /= 10;
- }
- reverse(c.begin(), c.end());
- if (pare == 0) {
- cout << "-1\n"; return 0;
- }
- pref[ 0 ] = 0;
- for (int i = 1; i <= (int)c.size(); ++ i) {
- pref[ i ] = pref[i - 1] * 10 + c[i - 1];
- p[ i ] = p[i - 1] + (c[i - 1] % 2 == 0);
- }
- /// cel mai mare <= k cu mai putin de px cif pare
- d[ 0 ][ 0 ] = 0;
- for (int i = 1; i <= (int)c.size(); ++ i) {
- for (int j = 0; j < pare; ++ j) {
- d[ i ][ j ] = 0;
- for (int x = 0; x <= 9; ++ x) {
- if (x % 2 == 0 && j > 0) {
- if (d[i - 1][j - 1] * 10 + x < pref[ i ])
- d[ i ][ j ] = max(d[ i ][ j ], d[i - 1][j - 1] * 10 + x);
- if (x < c[i - 1] && p[i - 1] == j - 1) {
- d[ i ][ j ] = max(d[ i ][ j ], pref[i - 1] * 10 + x);
- }
- } else if (x % 2 == 1) {
- if (d[i - 1][ j ] * 10 + x < pref[ i ])
- d[ i ][ j ] = max(d[ i ][ j ], d[i - 1][ j ] * 10 + x);
- if (x < c[i - 1] && p[i - 1] == j) {
- d[ i ][ j ] = max(d[ i ][ j ], pref[i - 1] * 10 + x);
- }
- }
- }
- }
- }
- int A = 0;
- for (int i = 0; i < pare; ++ i) {
- A = max(1LL * A, d[ (int)c.size() ][ i ]);
- }
- /// cel mai mic >= k cu mai putin de px cif pare
- d[ 0 ][ 0 ] = 0;
- for (int i = 1; i <= pare; ++ i) d[ 0 ][ i ] = inf;
- for (int i = 1; i <= (int)c.size(); ++ i) {
- for (int j = 0; j < pare; ++ j) {
- d[ i ][ j ] = inf;
- for (int x = 0; x <= 9; ++ x) {
- if (x % 2 == 0 && j > 0) {
- if (d[i - 1][j - 1] * 10 + x > pref[ i ]) {
- d[ i ][ j ] = min(d[ i ][ j ], d[i - 1][j - 1] * 10 + x);
- }
- if (x > c[i - 1] && p[i - 1] == j - 1) {
- d[ i ][ j ] = min(d[ i ][ j ], pref[i - 1] * 10 + x);
- }
- } else if (x % 2 == 1) {
- if (d[i - 1][ j ] * 10 + x > pref[ i ]) {
- d[ i ][ j ] = min(d[ i ][ j ], d[i - 1][ j ] * 10 + x);
- }
- if (x > c[i - 1] && p[i - 1] == j) {
- d[ i ][ j ] = min(d[ i ][ j ], pref[i - 1] * 10 + x);
- }
- }
- }
- }
- }
- long long B = inf;
- for (int i = 0; i < pare; ++ i) {
- B = min(B, d[ (int)c.size() ][ i ]);
- }
- if (B == inf) {
- B = 1;
- for (int i = 0; i < pare - 1; ++ i) B *= 10;
- for (int i = 0; i < (int)c.size() - pare + 1; ++ i) B = B * 10 + 1;
- }
- cout << 1LL * (k - A) * (B - k) << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement