Task: | Deleting digits |
Sender: | aalto2024e_008 |
Submission time: | 2024-09-30 16:21:27 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.00 s | details |
#7 | ACCEPTED | 0.00 s | details |
#8 | ACCEPTED | 0.01 s | details |
#9 | ACCEPTED | 0.01 s | details |
#10 | ACCEPTED | 0.02 s | details |
#11 | ACCEPTED | 0.02 s | details |
#12 | ACCEPTED | 0.02 s | details |
#13 | ACCEPTED | 0.00 s | details |
Code
#include <bits/stdc++.h> using namespace std; int n; /* map<int, int> store; int solve(int x) { if (store.count(x)) return store[x]; int y = x; int minimum = INT_MAX; while (y > 0) { int d = y % 10; y /= 10; if (d > 0 && x - d >= 0) minimum = min(minimum, 1 + solve(x - d)); } store[x] = minimum; return minimum; } */ int iterative() { if (n <= 9) return 1; vector<int> store(n+1); store[0] = 0; for (int i = 1; i <= 9; i++) store[i] = 1; for (int k = 10; k <= n; k++) { int minimum = INT_MAX; int y = k; while (y > 0) { int d = y % 10; y /= 10; if (d > 0) minimum = min(minimum, 1 + store[k - d]); } store[k] = minimum; } return store[n]; } int main() { // store[0] = 0; cin >> n; cout << iterative() << endl; return 0; }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
4 |
correct output |
---|
1 |
user output |
---|
1 |
Test 2
Verdict: ACCEPTED
input |
---|
17 |
correct output |
---|
3 |
user output |
---|
3 |
Test 3
Verdict: ACCEPTED
input |
---|
35 |
correct output |
---|
7 |
user output |
---|
7 |
Test 4
Verdict: ACCEPTED
input |
---|
167 |
correct output |
---|
29 |
user output |
---|
29 |
Test 5
Verdict: ACCEPTED
input |
---|
4434 |
correct output |
---|
687 |
user output |
---|
687 |
Test 6
Verdict: ACCEPTED
input |
---|
9722 |
correct output |
---|
1381 |
user output |
---|
1381 |
Test 7
Verdict: ACCEPTED
input |
---|
37882 |
correct output |
---|
5406 |
user output |
---|
5406 |
Test 8
Verdict: ACCEPTED
input |
---|
103330 |
correct output |
---|
13867 |
user output |
---|
13867 |
Test 9
Verdict: ACCEPTED
input |
---|
562167 |
correct output |
---|
75527 |
user output |
---|
75527 |
Test 10
Verdict: ACCEPTED
input |
---|
991919 |
correct output |
---|
127308 |
user output |
---|
127308 |
Test 11
Verdict: ACCEPTED
input |
---|
999993 |
correct output |
---|
128206 |
user output |
---|
128206 |
Test 12
Verdict: ACCEPTED
input |
---|
999999 |
correct output |
---|
128206 |
user output |
---|
128206 |
Test 13
Verdict: ACCEPTED
input |
---|
23456 |
correct output |
---|
3364 |
user output |
---|
3364 |