CSES - Removing Digits II | Loại bỏ chữ số II

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
nhphucqt
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, Output, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Scala, Scratch
Điểm: 2500 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một số nguyên \(n\). Mỗi bước, bạn có thể trừ bất kỳ số có một chữ số nào xuất hiện trong đó.

Cần thực hiện mấy bước để số đó bằng \(0\)?

Input

  • Một dòng duy nhất chứa số nguyên \(n\).

Output

  • Một dòng duy nhất chứa số bước thực hiện ít nhất.

Constraints

  • \(1\leq n \leq 10^{18}\)

Example

Sample input

27

Sample output

5

Note

  • Giải thích: Cách làm tối ưu là \(27 \rightarrow 20 \rightarrow 18 \rightarrow 10 \rightarrow 9 \rightarrow 0\).

Bình luận


  • 0
    iMafool    8:20 p.m. 31 Tháng 10, 2024

    code c++03:
    //cop code

    pragma GCC optimize("Ofast")

    include <bits/stdc++.h>

    define hutao_my_wife ios_base::sync_with_stdio(0);

    define forcalors_so_cute cin.tie(0);

    define ll long long

    define int ll //這個int單純是因為debug時懶得找溢位的程式碼

    define pii pair<int,int>

    define ff first

    define ss second

    define pb push_back

    define eb emplace_back

    define bug(A) cout<<A<<" hi\n";

    using namespace std;

    const int M = 200005;
    ll dp[20][10][10];
    ll to[20][10][10];
    int maxdigital(ll x){
    ll ans = 0;
    while(x){
    ans = max(ans,x%10);
    x/=10;
    }
    return ans;
    }
    int numi(ll x){
    x/=10;
    int ans = 0;
    while(x%10 == 9){
    ans++;
    x/=10;
    }
    return ans;
    }
    void solve(){
    ll n;
    cin>>n;
    ll ans = 0;
    while(n>0){
    int i = numi(n);
    int k = maxdigital(n - n%(ll)pow(10,i+1));
    int j = n%10;
    ans += dp[i][j][k];
    n -= (ll)pow(10,i+1);
    n = n - n%10 + to[i][j][k];
    }
    cout<<ans<<'\n';

    }
    signed main()
    {
    hutao_my_wife forcalors_so_cute

    int t = 1;
memset(dp,0,sizeof(dp));
for(int i = 0; i <= 18; i++){
    for(int k = 0; k < 10; k++){
        for(int j = 0; j < 10; j++){
            if(i+j+k == 0){
                to[i][j][k] = 0;
                continue;
            }
            if(i+k == 0){
                    dp[i][j][k]=1,to[i][j][k]=0;continue;
            }
            if(i == 0){
                if(j < k)dp[i][j][k] = 1,to[i][j][k]=(10+j-k)%10;
                else dp[i][j][k] = 2,to[i][j][k] = (10-k)%10;
                continue;
            }
            int last = j;
            for(int l = 9; l >= 0; l--){
                dp[i][j][k] += dp[i-1][last][max(k,l)];
                last = to[i-1][last][max(k,l)];
            }
            to[i][j][k] = last;
        }
    }
}
while(t--){
    solve();
}

    }

      • 12 bình luận nữa