Guest User

Untitled

a guest
Mar 29th, 2023
209
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. string s = to_string(r);
  2. int n = s.size();
  3. for (int i = 0; i <= n; i++)
  4.     for (int j = 0; j < 10; j++)
  5.         for (int k = 0; k < 10; k++)
  6.             for (int l = 0; l < 2; l++) dp[i][j][k][l] = -1;
  7. dp[0][0][9][1] = 0;
  8. for (int i = 1; i <= n; i++){
  9.     int dg = s[i-1] - '0';
  10.     for (int j = 0; j <= dg; j++){
  11.         for (int mx = 0; mx <= 9; mx++){
  12.             for (int mn = 0; mn <= 9; mn++){
  13.                 if (dp[i-1][mx][mn][1] == -1) continue;
  14.                 dp[i][max(mx, j)][min(mn, j)][dg == j] = max(dp[i-1][mx][mn][1] * 10 + j, dp[i][max(mx, j)][min(mn, j)][dg == j]);
  15.             }
  16.         }
  17.     }
  18.     for (int j = 0; j <= 9; j++){
  19.         for (int mx = 0; mx <= 9; mx++){
  20.             for (int mn = 0; mn <= 9; mn++){
  21.                 if (dp[i-1][mx][mn][0] == -1) continue;
  22.                 dp[i][max(mx, j)][min(mn, j)][0] = max(dp[i-1][mx][mn][0] * 10 + j, dp[i][max(mx, j)][min(mn, j)][0]);
  23.             }
  24.         }
  25.     }
  26. }
  27. vector <pair <int, int64> > v;
  28. for (int i = 0; i < 10; i++){
  29.     for (int j = 0; j <= i; j++){
  30.         for (int t = 0; t < 2; t++){
  31.             if (dp[n][i][j][t] != -1) {
  32.                 v.push_back({i-j, dp[n][i][j][t]});
  33.             }
  34.         }
  35.     }
  36. }
  37. sort(v.begin(), v.end());
  38. for (auto i: v) {
  39.     if (i.second >= l) {
  40.         cout << i.second << "\n";
  41.         return;
  42.     }
  43. }
Add Comment
Please, Sign In to add comment