[text] maddyy

Viewer

  1. // Problem: Removing Digits
  2. // Contest: CSES - CSES Problem Set
  3. // URL: https://cses.fi/problemset/task/1637
  4. // Memory Limit: 512 MB
  5. // Time Limit: 1000 ms
  6. //
  7. // Author: anshupriya
  8. // Created: 2024-05-05 15:59:34
  9.  
  10. #include <bits/stdc++.h>
  11. using namespace std;
  12.  
  13. #define pfi(a) printf("%d", a);
  14. #define pfl(a) printf("%lld", a);
  15. #define pfin(a) printf("%d\n", a);
  16. #define pfln(a) printf("%lld\n", a);
  17. #define pfis(a) printf("%d ", a);
  18. #define pfls(a) printf("%lld ", a);
  19. #define sfi(a) scanf("%d", &a);
  20. #define sfl(a) scanf("%lld", &a);
  21. #define fast                        \
  22.   ios_base::sync_with_stdio(false); \
  23.   cin.tie(NULL);                    \
  24.   cout.tie(NULL)
  25. #define f(i, a, b) for (int i = a; i < b; i++)
  26. #define pb(a) push_back(a);
  27. #define mp(a, b) make_pair(a, b)
  28. #define ll long long
  29. #define F first
  30. #define S second
  31.  
  32. int solve(int x, vector<int>& dp) {
  33.   vector<int> digits;
  34.   int temp = x;
  35.   while (temp != 0) {
  36.     digits.pb(temp % 10);
  37.     temp = temp / 10;
  38.   }
  39.   if (x == 0) {
  40.     return 0;
  41.   }
  42.   if (x < 0) {
  43.     return -1;
  44.   }
  45.   if (dp[x] != -2) {
  46.     return dp[x];
  47.   }
  48.   int ans = 1e9;
  49.   for (int i = 0; i < digits.size(); i++) {
  50.     if (digits[i] == 0) {
  51.       continue;
  52.     }
  53.     int val = solve(x - digits[i], dp);
  54.     if (ans != -1) {
  55.       ans = min(ans, val + 1);
  56.     }
  57.   }
  58.   if (ans == 1e9) {
  59.     return -1;
  60.     dp[x] = -1;
  61.   }
  62.   dp[x] = ans;
  63.   return ans;
  64. }
  65.  
  66. int main() {
  67.   int n;
  68.   cin >> n;
  69.   vector<int> dp(n + 1, -2);
  70.   int answer = solve(n, dp);
  71.   cout << answer << endl;
  72.   return 0;
  73. }

Editor

You can edit this paste and save as new:


File Description
  • maddyy
  • Paste Code
  • 05 May-2024
  • 1.55 Kb
You can Share it: