- // Problem: Removing Digits
- // Contest: CSES - CSES Problem Set
- // URL: https://cses.fi/problemset/task/1637
- // Memory Limit: 512 MB
- // Time Limit: 1000 ms
- //
- // Author: anshupriya
- // Created: 2024-05-05 15:59:34
- #include <bits/stdc++.h>
- using namespace std;
- #define pfi(a) printf("%d", a);
- #define pfl(a) printf("%lld", a);
- #define pfin(a) printf("%d\n", a);
- #define pfln(a) printf("%lld\n", a);
- #define pfis(a) printf("%d ", a);
- #define pfls(a) printf("%lld ", a);
- #define sfi(a) scanf("%d", &a);
- #define sfl(a) scanf("%lld", &a);
- #define fast \
- ios_base::sync_with_stdio(false); \
- cin.tie(NULL); \
- cout.tie(NULL)
- #define f(i, a, b) for (int i = a; i < b; i++)
- #define pb(a) push_back(a);
- #define mp(a, b) make_pair(a, b)
- #define ll long long
- #define F first
- #define S second
- int solve(int x, vector<int>& dp) {
- vector<int> digits;
- int temp = x;
- while (temp != 0) {
- digits.pb(temp % 10);
- temp = temp / 10;
- }
- if (x == 0) {
- return 0;
- }
- if (x < 0) {
- return -1;
- }
- if (dp[x] != -2) {
- return dp[x];
- }
- int ans = 1e9;
- for (int i = 0; i < digits.size(); i++) {
- if (digits[i] == 0) {
- continue;
- }
- int val = solve(x - digits[i], dp);
- if (ans != -1) {
- ans = min(ans, val + 1);
- }
- }
- if (ans == 1e9) {
- return -1;
- dp[x] = -1;
- }
- dp[x] = ans;
- return ans;
- }
- int main() {
- int n;
- cin >> n;
- vector<int> dp(n + 1, -2);
- int answer = solve(n, dp);
- cout << answer << endl;
- return 0;
- }
[text] maddyy
Viewer
*** This page was generated with the meta tag "noindex, nofollow". This happened because you selected this option before saving or the system detected it as spam. This means that this page will never get into the search engines and the search bot will not crawl it. There is nothing to worry about, you can still share it with anyone.
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:
Latest Code Pastes